white papers

"Traveling Salesman" Program

This program solves a form of the traditional "traveling salesman" problem. A list of cities with distances to each other is used as reference, and the user selects a number of cities to visit. The program calculates the optimum sequence of cities, minimizing total distance traveled.

The program was compiled on a Gateway Solo laptop under Windows 98, using Green Hills Optimizing C++/EC++ Compilers and MULTI®. The target is a PowerPC 860. The program sizes are specific to this PPC configuration, but are representative of the relative sizes of programs compiled with EC++ vs. standard C++ and C. Note that the use of EC++ achieved a 74% reduction in code size compared to C++!

===============================================
Total Code Size Reduction:
===============================================
Standard C++, with EH:  329,184 bytes
Standard C++, no EH:    218,775
EC++, with EH:          87,647
EC++, no EH:            58,422
C:                      25,688

EH = Exception Handling

ec++ graph
These results show dramatic code size reduction through the use of Embedded C++. In addition, significant execution time reduction also is achieved. EC++ can make C++ Object Oriented Programming practical for use in embedded application development, with nearly the code-size efficiency of C.



#include "tsp.h"

void FindRoute (int, int, int, City *);
City FinalRoute[NUM_CITIES];

int main () {
	int temp;
	NumToVisit = 0;
	extern int Entries;

	/*Initialize from the table.*/
	for (int i=0;i<NUM_CITIES;i++) {
		Cities[i] = City(i, Names[i]);
	}

	/*Un-comment this block to print out the distance table.*/
/* 
	for (int i=0;i<;NUM_CITIES;i++)
		for (int j=0;j<NUM_CITIES;j++)
			cout << "The distance from " << Cities[i] << " to "Cities[j] << " is " << Distances[i][j] << endl;
*/

	/*Get the cities to visit from the user.*/
	cout << "Enter the numbers of the cities you need to visit" << endl;
	cout << "separated by spaces and terminated with a period." << endl;
	for (int i=0;i<NUM_CITIES;i++)
		cout << Cities[i].Id() << '\t' << Cities[i].Name() << endl;
	while (cin >> temp){
		Cities[temp].AddToItin();
		NumToVisit ++;
	}

	/*Un-comment this block to echo the user's choices.*/
/*	cout << "You have entered the following cities:" << endl;
		for (int i=0;i<NUM_CITIES;i++)
			if (Cities[i].NeedToVisit())
			cout << Cities[i] << endl;
*/

	/*Find a starting point.*/
	for (StartingPoint=0;StartingPoint<NUM_CITIES;StartingPoint++) {
		if (Cities[StartingPoint].NeedToVisit())
			break;
	}
	Cities[StartingPoint].TakeOffItin();
	Cities[StartingPoint].SetVisited(0);

	/*The function FindRoute will find the best possible route.*/
	FindRoute (StartingPoint, 0, NumToVisit-1, Cities);
	cout << "The best route is:" << endl;
	for (int i=0;i<NumToVisit;i++)
		for (int j=0;j<NUM_CITIES;j++)
			if (FinalRoute[j].OrderVisited() == i)
				cout << Cities[j] << endl; cout << "Distance is: " << BestDistance << endl;
 cout << "Entered FindRoute " << Entries << " times." << endl;
 return 0;
}

void FindRoute (int StartHere, int SoFar, int CitiesLeft, City *RouteSoFar) {
extern int Entries;

	Entries++;
	/*If we've visited all the cities then let's see if this was the best route.*/
	if (CitiesLeft == 0) {
/*		cout << "Testing:" << endl;
		for (int i=0;i<NumToVisit;i++)
			for (int j=0;j<NUM_CITIES;j++)
				if (RouteSoFar[j].OrderVisited() == i)
					cout << Cities[j] << endl;
*/
		SoFar = SoFar + Cities[StartHere].DistanceTo(StartingPoint);
		cout << "Distance is: " << SoFar << endl << endl;
		if (SoFar < BestDistance || BestDistance == -1) {
			BestDistance = SoFar; 
			for (int i=0;i<NUM_CITIES;i++)
				FinalRoute[i] = RouteSoFar[i];
		}
		return;
	}

	/*Otherwise let's try all the possible next cities.*/
	for (int i=0;i<NUM_CITIES;i++) {
		if (RouteSoFar[i].NeedToVisit()) {
			SoFar = SoFar + Cities[StartHere].DistanceTo(i);
			RouteSoFar[i].SetVisited(NumToVisit - CitiesLeft);
			RouteSoFar[i].TakeOffItin();

			/*Draw Line*/
			FindRoute (i, SoFar, CitiesLeft - 1, RouteSoFar);
			RouteSoFar[i].SetVisited(-1);
			RouteSoFar[i].AddToItin();

			/*Erase Line*/
			SoFar = SoFar - Cities[StartHere].DistanceTo(i);
		}
	}
}

------------------------------------------------------------------------
tsp.h:

#include <stdio.h>
#include <string.h>
#include <iostream.h>

/*The table of cities and distances constant.*/
/*If the user wants to add a city, (s)he'll have to */
/* add it to the code and rebuild.*/
/*Reading the table "on the fly" would not be difficult,*/
/*but IO is not the focus of this program.*/

/*NUM_CITIES is the total number of cities we could possibly*/
/*want to visit.*/
#define NUM_CITIES 18

/*Here's the table of distances.*/
const int Distances[NUM_CITIES][NUM_CITIES] = {

	/*  Al  At  Bo  Ch  Cl  Da  Dn  Dt  LA  Mm  Mn  NO  NY  SL   SC   SF   Se  DC */
	/*Al*/
	{ 0,  1410,  2270,  1347, 1627, 654, 457, 1569, 804, 2071, 1228, 1160, 2178, 1039, 625, 1081, 1443, 1892},
	/*At*/
	{ 1410, 0,  1115, 717, 780, 788, 1425, 743, 2362, 653, 1131, 475, 887, 559, 1943, 2482, 2723, 634  },
	/*Bo*/
	{ 2270,  1115,  0,  1013, 667, 1845, 2015, 714, 3028, 1541, 1459, 1619, 197, 1196, 2405, 3139, 3126, 471},
	/*Ch*/
	{ 1347, 717, 1013, 0,  345, 937, 1026, 288,  2086, 1237, 410, 926, 818, 302, 1420, 2151, 2108, 712  },
	/*Cl*/
	{ 1627, 780, 667, 345, 0,  1185, 1359, 173, 2388, 1274, 765, 1060, 481, 578, 1753, 2484, 2463, 375  },
	/*Da*/
	{ 654, 788, 1845, 937, 1185, 0,  794, 1249, 1486, 1325, 963, 509, 1620, 629, 1329, 1734, 2112, 1367 },
	/*Dn*/
	{ 457, 1425, 2015, 1026, 1359, 794, 0,  1285, 1062, 2065, 928, 1344, 1807, 879, 527, 1268, 1314, 1705 },
	 /*Dt*/
	{ 1569, 743, 714, 288, 173, 1249, 1285, 0,  2311, 1432, 671, 1068, 646, 543, 1656, 2390, 2396, 525  },
	 /*LA*/
	{ 804, 2362, 3028, 2086, 2388, 1486, 1062, 2311, 0,  2785, 1993, 2009, 2797, 1844, 703, 384, 1143, 2727 },
	/*Mm*/
	{ 2071, 653, 1541, 1237, 1274, 1325, 2065, 1432, 2785, 0,  1802, 857, 1347, 1197, 2594, 3083, 3419, 1070 },
	/*Mn*/
	{ 1228, 1131, 1459, 410, 765, 963, 928, 671, 1993, 1802, 0,  1328, 1234, 625, 1321, 2052, 1661, 1128 },
	/*NO*/
	{ 1160, 475, 1619, 926, 1060, 509, 1344, 1068, 2009, 857, 1328, 0,  1401, 677, 1859, 2313, 2642, 1159 },
	/*NY*/
	{ 2178, 887, 197, 818, 481, 1620, 1807, 646, 2797, 1347, 1234, 1401, 0,  1004, 2214, 2945, 2924, 235  },
	 /*SL*/
	{ 1039, 559, 1196, 302, 578, 629, 879, 543, 1844, 1197, 625, 677, 1004, 0,  1400, 2134, 2140, 835  },
	/*SC*/
	{ 625, 1943, 2405, 1420, 1753, 1329, 537, 1656, 703, 2594, 1321, 1859, 2214, 1400, 0,  736, 821, 2229 },
	/*SF*/
	{ 1082, 2482, 3139, 2151, 2484, 1734, 1268, 2390, 384, 3083, 2052, 2313, 2945, 2134, 736, 0,  808, 2960 },
	/*Se*/
	{ 1443, 2723, 3126, 2108, 2463, 2112, 1314, 2396, 1143, 3419, 1661, 2642, 2924, 2140, 821, 808, 0,  2690 },
	/*DC*/
	{ 1892, 634, 471, 712, 375, 1367, 1705, 525, 2727, 1070, 1128, 1149, 235, 835, 2229, 2960, 2818, 0    }
};

/*Here's a character * version of the city names.*/
const char *Names[NUM_CITIES] = {
	"Albuquerque",
	"Atlanta",
	"Boston",
	"Chicago",
	"Cleveland",
	"Dallas",
	"Denver",
	"Detroit",
	"Los Angeles",
	"Miami",
	"Minneapolis",
	"New Orleans",
	"New York City",
	"St. Louis",
	"Salt Lake City",
	"San Francisco",
	"Seattle",
	"Washington D.C."
};
 
/*City is a bona fide C++ class that we use to store the information about*/
/*a given city.*/
class City {
	int id;
	char name[30];
	int need_to_visit;
	int order_visited;

	public:
		int DistanceTo(int);
		int NeedToVisit() {return need_to_visit;}
		City* operator&();
		City (int, const char *);
		City () {};
		int Id() {return id;};
		int OrderVisited() {return order_visited;}
		char *Name() {return name;};
		void AddToItin() {need_to_visit = 1;};
		void TakeOffItin() {need_to_visit = 0;};
		void SetVisited(int When) {order_visited = When;};
		int FindClosest(int *);
};

City Cities[NUM_CITIES]; //the list of cities
	int StartingPoint;
	int BestDistance = -1;
	int NumToVisit;
	int Entries = 0;
 
/*This constructor is called each time that we put a new city on our list.*/
City::City(int new_id, const char *new_name) {
	id = new_id;
	strcpy (name, new_name);
	need_to_visit = 0;
	order_visited = -1;
}

/*This function finds the closest city that we still need to visit.*/
int City::FindClosest(int *BestDistance) {
	int Best;
	*BestDistance = -1;
	for (int i=0;i<NUM_CITIES;i++)
		if (((DistanceTo(i) < *BestDistance) || (*BestDistance == -1)) && Cities[i].NeedToVisit()) { 
			Best = i;
			*BestDistance = DistanceTo(i);
		}
	return Best;
}
 
/*This function gives us the distance to a city given its index.*/
int City::DistanceTo(int GoHere) {
	return Distances[GoHere][Id()];
}

/*This function prints the name of the city.*/
ostream& operator<< (ostream&s, City PrintMe) {
	return s << PrintMe.Name();
}

-----------------------------------------------------------------------------------------



© 1996-2014 Green Hills Software Trademark & Patent Notice