Solving TSP using backtracking

Question

I have been trying to figure out how to solve TSP using backtracking. How do you calculate the "cost"?

Matrix:

∞   20  30  10  11
15  ∞   16  4   2
3   5   ∞   2   4
19  6   18  ∞   3
16  4   7   16  ∞

Cost:

3 -> 1 -> 2 -> 4 -> 5 -> 3 cost = 37
3 -> 1 -> 2 -> 5 -> 4 -> 3 cost = 59
3 -> 1 -> 5 -> 2 -> 4 -> 3 cost = 50
3 -> 1 -> 5 -> 4 -> 2 -> 3 cost = 62
3 -> 1 -> 4 -> 2 -> 5 -> 3 cost = 28
3 -> 1 -> 4 -> 5 -> 2 -> 3 cost = 36

I found out that it's calculated using Bellmans equation, I just don't know the way to do it.

Any help would be highly appreciated!

Answer 1

In order to calculate the costs, you just need to sum up all the edge costs. For example for the route 3 -> 1 -> 2 -> 4 -> 5 -> 3, this yields

(3,1) => 3
(1,2) => 20
(2,4) => 4
(4,5) => 3
(5,3) => 7
------------
sum      37

So, essentially you have to generate a first sample route and calculate its cost. As soon as you did this, you know that the resulting cost might be an optimum solution.

If you do backtracking now and you come into a situation where you already have a higher cost, you know that this won't lead to a better route and thus, you can stop exploring routes and backtrack one step back.

Example: You discovered in your first run that the route 1 2 3 4 5 6 7 8 9 1 yields cost of 40. Now, at some backtracking step, you have the beginning of a route: 1 2 4 5 6 ... and see that up to this point, the cost is already 41. This means, if you explore any route beginning with these numbers, you will have a route having cost more than 40 and thus, not optimal! Now, you can simply discard all routes beginning with 1 2 4 5 6.

(Note that the above considerations work only if using nonnegative edge costs!)