Write a program to solve the
travelling salesman problem
(for a smallish map size)
Example run of a desirable program:
$ CC tsp.cpp
–o tsp
$ tcp
5
0
2 4 3 5
5 0
-1 1
3
2 -1
0 4 1
5
4 1 0 5
2
4 1 3 0
Best travelling
salesman path, cost=7
A - B - D - C - E –
A
The inputs are a single number (let's call it N) which indicates how many cities there are, followed by N2 numbers representing the cost of travel between any pair of cities. The number in row r, column c indicates the cost of travelling from city r to city c. A cost equal to -1 means that travel is impossible at any price. We would normally expect the main diagonal of that matrix to contain zeros, because it costs nothing to stay where you are.
The names of cities are single letters, the first is called A, the second B, the third C, and so on. It is assumed that the salesman lives in city A. You have to find a path that starts and ends at city A, and visits every other city exactly once, with the minimum possible cost.
The matrix in the example shows that it costs $2 to travel directly from A to B, but $5 to travel from B to A. There is no reason why costs should be symmetric. It is impossible to travel directly between B and C. The least expensive tour of all cities is as indicated, starting at A, go first to B (cost $2), then from B to D (cost $1), then from D to C (cost $1), then from C to E (cost $1), and finally back from E to A (cost $2), for a total cost of $7, as the program said.
You can get an idea of how processor intensive the problem is, by verifying that answer for yourself. You won't be able to find a cheaper path, but it takes quite a while to make sure, and that's just for a trivial map with 5 cities. Do not limit your program to a mere 5 cities, but there isn't much point in trying to cover more than 30 or so.
Note that it doesn't matter which city you start at (so long as you end at the same one), because you are finding a circular path. If your salesman lived in city C, this same solution could be rotated to C-E-A-B-D-C.