|
"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++! |
|
=============================================== |
|
#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();
}
-----------------------------------------------------------------------------------------
|
