The Travelling Salesman Problem, also known by abbreviation TSP has a very simple statement:
There is a Merchant (or Salesman) who wants to visit
N cities (buying and selling goods there). The cities are
connected by the network of roads of the known length. We want to find the path consisting of
N-1 roads and visiting all
N cities, which have minimum possible length.
Though the statement is short, the solution could be not that easy to find and implement. To demonstrate this, we'll
try to create program solving the TSP on a small network of
You should start from city
0 and finish anywhere you like, but all
20 cities should be visited, path should be
the chain of
19 roads and its length should be minimal. All roads would be bi-directional, i.e. graph is "undirected".
Input data contains
20 lines, each describing roads from the given city.
Every line will start with the number of the city it is describing (just for convenience).
Then several pairs of numbers will follow in the form
T is the target city of the given road and
Answer should contain
20 values describing the path - simply the numbers of the cities visited in proper order.
Example (for simplicity with only
data: 0 1:90 2:42 3:90 5:29 1 0:90 3:98 2:70 4:65 2 0:42 1:70 5:30 3:36 4:97 6:46 3 1:98 2:36 0:90 5:77 4 1:65 2:97 6:68 5 2:30 3:77 0:29 6:90 6 5:90 2:46 4:68 answer: 0 5 3 2 6 4 1
The path length in this example is
Don't miss the similar problem with larger data-set and a challenge: Travelling Salesman Inverted!