Jan 93 Challenge

Volume Number: 9

Issue Number: 1

Column Tag: Challenge

Programmers' Challenge

By Mike Scanlin, MacTech Magazine Regular Contributing Author

Note: Source code files accompanying this article are located on MacTech CD-ROM

or source code disks.

Challenge of the Month: Travelling Salesman

Recent discussions with friends about fuel efficiency reminded me of a problem I once

had in a linear algebra class: A travelling salesman needs to visit a set of cities. He can

go from any city to any other city and must visit each city exactly once. The question is,

what is the optimal order of visitation that minimizes total distance travelled?

The prototype of the function you write is:

void OptimalPath(numCities,

startCityIndex, citiesPtr,

optimalPathPtr)

unsigned short numCities;

unsigned short startCityIndex;

Point *citiesPtr;

Point *optimalPathPtr;

Example:

Input:

numCities = 6

startCityIndex = 2

*citiesPtr = {1,4}, {2,2}, {2,1}, {5,7}, {4,6}, {2,6}
Output:
*optimalPathPtr = {2,1}, {2,2}, {1,4}, {2,6}, {4,6}, {5,7}

numCities is a 1-based count of the number of cities to be visited (between 3 and

20, inclusive); startCityIndex is a zero-based index of the city in which the salesman

starts ((2,1) in this example); citiesPtr is a pointer to an array of city locations (x

and y locations are positive integers from 0 to 32767; each entry in the array is

unique - no duplicate cities); optimalPathPtr points to an array (allocated by the

caller) that OptimalPath fills in with the coordinates of the cities that the salesman

should visit, in the order he should visit them (the first entry will always be

citiesPtr[startCityIndex]).

October Challenge winner!

The winner of the October “Name no one man” palindrome challenge is Stepan

Riha (location unknown). His superb solution is overflowing with neat optimization

Referenced by (2):