Dynamic Programming for TSP

What is the meaning of a shortest path? Ahsan ponders...

A shortest path that starts from A and ends at A, through B and C and D and E and F and G.

But sequence between A and A doesn't have to be B to C to D to E to F to G. 

Does it really have to end in G, before coming back to A?

No.

Maybe, it ends in B or C or D or E or F, before coming back to A.

It depends on which would lead to the shortest distance.

Let's think again: what are we looking for?

Aside from A, we have a set of cities S = {B,C,D,E,F,G}

We are looking for the overall cost of a path that starts at A and visits each village in the set {B,C,D,E,F,G} before coming back to A.

Let cost(S) be the cost of traveling from A to the cities in S, before coming to A.

If B is the last city to be visited before coming back to A, then

cost(S) = cost(S - B) + dist(B, A) 

Here, cost(S-B) is the cost of traveling from A to the cities in S-B, before coming to B.

If C is the last city to be visited before coming back to A, then

cost(S) = cost(S - C) + dist(C, A) 

And so on..

The question is which city should be the last before coming back to A.

I can write it all as follows, the sequence of cities to be visited, Ahsan thinks... 

The blanks are to be decided..

I need to think the best path that ends in G before coming to A.

The best path that ends in F before coming to A.

ends in E before coming to A.

and so on.

Surely we need to pick the one that will result in with the minimum cost, he strains his head.

In other words, 

cost(S) = minimum among the following:

•                          cost(S - B) + dist(B, A) 
•                          cost(S - C) + dist(C, A)
•                          cost(S - D) + dist(D, A) 
•                          cost(S - E) + dist(E, A)
•                          cost(S - F) + dist(F, A)
•                          cost(S - G) + dist(G, A)

What's in there, the above? 

dist(B, A) is, of course, the distance from B back to A. 

dist(C, A) from C to A.

And so on.

Ahsan focuses on one of the cost values above..

What's cost(S-G)? 

S-G means the set S with G as the last node.

cost(S-G) would then mean a minimum-cost path that starts from A and covers every node in S-{G} once before coming to G.

So what is this value... cost(S-G)?

The path may end in B before going on to G.

The path may end in C before going on to G.

Or it may end in D before coming to G.

Or in E.

Or in F...

Or in G...

In other words, Ahsan articulates: 

cost(S-G) = minimum among the following:

•                          cost(S - G - B) + dist(B, G)
•                          cost(S - G - C) + dist(C, G) 
•                          cost(S - G - D) + dist(D, G)
•                          cost(S - G - E) + dist(E, G) 
•                          cost(S - G - F) + dist(F, G)

or maybe i should write it in this way.. he squibbles

•                          cost(S - {G, B}) + dist(B, G)
•                          cost(S - {G, C}) + dist(C, G) 
•                          cost(S - {G, D}) + dist(D, G)
•                          cost(S - {G, E}) + dist(E, G) 
•                          cost(S - {G, F}) + dist(F, G)

what am i doing here...

Ahsan glances at the clock.. it's past midnight.

I'm calculating the shortest path for the case whereby we start from A, and the last city before returning back to A is G.

So I have to consider the case where the path before G ends in B.

or ends in C.

or D..

or E..

or F.

and if you consider the path that ends in B...then we have as follows

All for the sake of finding cost(S - {G, B}), you need the minimum of:

•                          cost(S - {G, B, C}) + dist(C, B)
•                          cost(S - {G, B, D}) + dist(D, B) 
•                          cost(S - {G, B, E}) + dist(E, B)
•                          cost(S - {G, B, F}) + dist(F, B) 

And if you consider the first option, you will need to calculate cost(S - {G, B, C}).

Which is the minimum of

• cost(S - {G, B, C, D}) + dist(D, C) 
• cost(S - {G, B, C, E}) + dist(E, C)
• cost(S - {G, B, C, F}) + dist(F, C)

You will just keep continuing, right?

Recursively.. 

To compute  cost(S - {G, B, C, D}), you would need the minimum of 

• cost(S - {G, B, C, D, E}) + dist(E, D) 
• cost(S - {G, B, C, D, F}) + dist(F, D)

We are going recursively... 

At each recursive iteration, we look for the subpath with the smallest distance...

Ahsan beams with delight.

It all seems set then.

TSP can be solved recursively.

Is it better than a plain brute force method though? 

No.. same number of evaluations eventually.

Same number of possibilities...

He moans..

So no advantage..

No, just cleaner implementation probably.

But wait..

Are there repetitions in the recursive calculations?

Clearer if we put it in the form of a tree diagram, he thinks..

At a certain level, there will start to be duplicated computations.

You can see it above.

cost(S-{B,D,E,F}) is the cost for a set in that goes from A, traversing elements in a set that excludes B, D and E, and then coming to F followed by E.

cost(S-{D,B,E,F}) is the cost for a set in that goes from A, traversing elements in a set that excludes B, D and E, then coming to F followed by E.

To fix this repetitions, to eliminate it, we can do as follows: just do it all bottom up.

The fancy name for this: dynamic programming.

It's just recursion turned upside down..

A Sketch of the Python Code

What code I have largely a simplification of the one in https://gist.github.com/mlalevic/6222750.

Suppose we have cities with the following coordinates:

[[3.0, 3.0], [4.0, 5.0], [6.0, 9.0], [0.0, 7.0], [9.0, 9.0], [3.0, 10.0]]

The adjacency matrix, let's name the variable as all_distances, can be derived to be as follows (just use calculator or worksheet or punch in a simple python code :-):

[[ 0.          2.236     6.708     5.          8.485    7.        ]

 [ 2.236    0.           4.472     4.472    6.403    5.099  ]

 [ 6.708    4.472     0.           6.324    3.          3.162  ]

 [ 5.          4.472     6.324     0.          9.220    4.243  ]

 [ 8.485    6.403     3.           9.220    0.          6.083  ]

 [ 7.          5.099     3.162     4.243    6.083    0.        ]]

So how will the dynamic programming work..

First build all subsets of size 2, with each starting from city 0 - whatever your first city 

In our case here, it is [3.0, 3.0].

Build the list of subsets as a dictionary (https://www.tutorialspoint.com/python/python_dictionary.htm), the key being a tuple of the form:  (subset, last_node)

and the value being a tuple of the form: (distance, path)

So the dictionary will be of the form:

{ (subset, last_node): (distance, path),  (subset, last_node): (distance, path), ... }

In more details..

You already have an adjacency matrix, all_distances.

Initialize a blank dictionary A

  A = {}

Iterate through the distances from 0 as follows, using enumerate (http://book.pythontips.com/en/latest/enumerate.html)

  for idx,dist in enumerate(all_distances[0][1:]):

The pairs of idx and dist produced by the loop will be the following:

0 , 2.23606798

1 , 6.70820393

2 , 5.0

3 , 8.48528137

4 , 7.0

Each time in the loop, create a set (Python frozenset: https://www.programiz.com/python-programming/methods/built-in/frozenset), 

        subset = frozenset([0, idx+1])

Each set will just be of the form {0, index}. 

In the code, index is idx + 1, since we want the index to start at 1, not 0 (that's the source).

The last city in the set is just idx+1

        lastCity = idx+1 

The path involves just 2 nodes, 0 and idx+1.

        thePath = [0,idx+1]

Now build a dictionary entry for A:

        A[(subset, lastCity)] = (dist, thePath)

 The overall initial code as follows:

  A = {}

  for idx,dist in enumerate(all_distances[0][1:]):

        subset = frozenset([0, idx+1])

        lastCity = idx+1 

        thePath = [0,idx+1]

        A[(subset, lastCity)] = (dist, thePath)

Your A will be as follows:

{

   (frozenset({0, 1}), 1): (2.236, [0, 1]), 

   (frozenset({0, 2}), 2): (6.708, [0, 2]), 

   (frozenset({0, 3}), 3): (5.0, [0, 3]), 

   (frozenset({0, 4}), 4): (8.485, [0, 4]), 

   (frozenset({0, 5}), 5): (7.0, [0, 5])

}

Now we are going to incrementally build larger paths..

Loop for subset size m (not including the starting point 0) ranging from 2 to the # cities:

  for m in range(2, numcities):

For each subset size, initialize a blank dictionary B:

        B = {}

B is going to be our new dictionary, containing paths longer by one at each iteration. 

Now create combinations of size m.

We make use of the itertools package (https://docs.python.org/2/library/itertools.html).

        for C in itertools.combinations(range(1, numcities), m):

Let S be the combination C with the starting city (0) appended to the front.              

             S = frozenset(C) | {0}

At m = 2, S will be the following:

frozenset({0, 1, 2})

frozenset({0, 1, 3})

frozenset({0, 1, 4})

frozenset({0, 1, 5})

frozenset({0, 2, 3})

frozenset({0, 2, 4})

frozenset({0, 2, 5})

frozenset({0, 3, 4})

frozenset({0, 3, 5})

frozenset({0, 4, 5})

For each of the combinations above, we are going to find the best sequence..

We shall try sequences ending in every possible city

To do this, iterate over the cities in S, minus the starting city

             for j in S - {0}:

   

At each iteration, we are to build a list containing all path ending in the city

                  temp_list = []

For every other city in S, not including 0 and j (the city currently being considered)

                  for k in S:

                        if k != 0 and k!=j:   # for each k which is not 0 and not j

Consider what was the best path (and its distance) that did not include j (the current city), and which ended in k.

How to do this?!

Make use of A !

                               prevSubsetVal = A[(S-{j}, k)]

                               kLastDistPrev = prevSubsetVal[0]

                               kLastPathPrev = prevSubsetVal[1]

Append j to that path.

And add up the cost.

That becomes ur tuple, temp.

                               temp = (kLastDistPrev + all_distances[k][j], kLastPathPrev + [j])

Build up a list containing every path ending in j

                               temp_list.append(temp)

Now you can find the min among all combination ending in j

Find that and put the min in the new cost dictionary, B

                 B[(S, j)] = min(temp_list)

When you are done with computing subsets of size m, update A

        A = B

Here's the overall code up to this stage:

    cnt = len(all_distances)    

    for m in range(2, cnt):

        print('****')

        print ('the subset size, m, is ', m)

        B = {}

        for C in itertools.combinations(range(1, cnt), m):

            S = frozenset(C) | {0}

            print('S is ', S)

            

            # consider subsets ending in j

            for j in S - {0}:

                print('considering subset S of size ', m, ' ending in ',j)

                temp_list = []

                for k in S:

                    if k != 0 and k!=j:

                        prevSubsetVal = A[(S-{j}, k)]

                        kLastDistPrev = prevSubsetVal[0]

                        kLastPathPrev = prevSubsetVal[1]

                        temp = (kLastDistPrev + all_distances[k][j], kLastPathPrev + [j])

                        temp_list.append(temp)

            

                print('Look for min in ', temp_list)

                B[(S, j)] = min(temp_list)  

                print('Adding subsets ending at j = ', j, ' gives you B =', B)

        A = B

        print('A, now containing subset of sizes ', m, ' is ', A)

And when you are done up to the final subset size....

We can list out the final possible paths ...
    final_list = []

To build this list, iterate over the keys in A

Remember, in A,  a key is of the form: (subset, last_node)

and the value: (distance, path)

    for d in iter(A):

Add up distance for the last leg (from last visited node to the starting node):

        entry = (A[d][0] + all_distances[0][d[1]], A[d][1])

Append (distance, path) to final_list
        final_list.append(entry)

Take the minimum among the possible paths:
    res = min(final_list)

Job done 

Branch-and-Bound for TSP

Babu lives in a certain village A, and in a sudden fit of materialism, he decides to earn extra income selling dubious medicine, like the ones above, in other villages within the vicinity.

To avoid trouble, he will not visit the same village twice, and to minimize cost, he has to keep his travelling distance the shortest possible - that being the major cost component, the medicine practically costing nothing (since it is dubious after all).  He will need the shortest possible path that visits every other city once before returning to the safety of his own village, A. And he needs the travelling cost before he starts selling the medicine, to be able to factor in that cost into his selling price. But he (somehow) knows that its going to be O(N!) , just doing the calculation, and he doesn't have that much time. 

So, not wanting to spend too much time going through a brute-force evaluation of all possible paths, he decides to keep track of the lower bound for the cost. This is a cost value below which the actual cost can never go below. He wanders for a while on what or how this lower bound is to be calculated, and after much jostling about, hanging about, staring into space, spamming scribbles into pieces of papers, he chances upon an idea. Suppose in the shortest path, for every village, one considers the 2 shortest road into or out from the village. Of course, it may or may not be possible to actually form a path using the 2 shortest roads for each of the villages. But still it may be possible, and he's considering that best-scenario possibility. The lower bound for the total cost is then a sum of the length of the 2 shortest roads for every village. There is certainly no way for the cost of the actual shortest path to go lower than this.

So he draws up the following table.. for each village, he's going to record the two shortest roads.

Here's what he have in the table,:

Now he sum up the total of the shortest 2 distances for each village:

And then calculate the sum of all the sums:

And he get 70, or 70km to be precise. That is a pretty long trip, but is 70km really the lower bound, he wondered.  He pondered again over his map.

He came to realize that if 2 villages share the same shortest edge, than that edge is going to be counted twice. In fact, it's the same for all the other consecutive villages on the shortest path. So 70 is likely an overestimate. If the shortest path indeed comprises of all the 2 shortest roads for each village, then he would have counted each road twice, as shown above. His forehead wrinkled pondering over this, he realized that he has to divide the 70 by 2. Whatever the value obtained by summing up the 2 shortest roads for each village, he has to divide it by two. In terse form, it looks as shown below:

The e with 0 as the superscript and v as the subscript denotes the shortest edge of village v, where v can be anything from A to G. The e with superscript 1 is the second shortest edge.

Applying the formula as it is above, Babu obtains the value of 35. The shortest path for him to travel cannot be any shorter than 35. But now comes the actual problem: what is the actual path? In all likelihood the actual path he'll be taking will be much longer than the theoretical shortest path, the one with the length of 35.  It doesn't make good business sense to consider the theoretical lower bound to be the actual shortest travelling distance.

He thinks of possible options he has when actually carving out the routes. From A, he can go to any of the following 3: B, G, F.

Had he chosen B, he could proceed on to G or C. And had he gone to G, he could from there, gone on to B or C or D or E or F. And as can be seen below, from F, he could continue as shown below, to proceed on to either G and E:

Now, that's lots of work.. Babu keeps thinking. He imagines a complete path A-B-G-C-D-E-F.

Summing up the length of the roads along the path (including the road from F back to A), he gets 

But that's just a single path.... Should he also explore further the path A-B-G-D? Should he? Babu ponders, his forehead now wrinkled so much that's it ages beyond his age... He has the lower cost (35). But that lower cost makes no assumption about what roads to be fixed, what roads selected. But if he knows the lower cost, after fixing A-B-C-D, then he needs explore further only if the lower cost is lesser than the 36 he found for A-B-G-C-D-E-F. If that lower cost is more than 36, then he cannot expect anything better than 36 extending the A-B-C-D path. 

So the question now for Babu is the following... Having the overall lower cost bound, how should he calculate the new lower cost after fixing a number of edges (or roads)?

Like suppose, from A, he decides to go to B, as shown below. What should be the new lower cost bound then? Logically, one needs to remove certain part from the lower bound - the cost for shortest or second shortest edges for A and B. And you need to add in the overall actual cost so far, that is the distance from A to B. 

The new lower bound should then be something like as follows:

Babu gazes lovingly at his new found formula. Just a part missing - what should be subtracted from the original lower bound? It must be the length of edges connected to A and B. He thinks about it, and decides that it should be the average of the shortest edges from A and from B. He adjusts his formula to look as follows:

It seems perfectly logical now. Take away the cost of the smallest road in A and in B from the original lower bound, then add to the adjusted lower bound cost the total distances of the roads selected up to this point.

Now, what happen if he proceed further, from B to C? 

He thinks about how the lower bound will now be adjusted.

Surely, he will need to subtract another term from the original lower bound. It must be the average of the shortest roads in B and that in C. But since the shortest road from B has already been subtracted out, for B, he will have to settle for the second shortest road. Hence, the revised lower bound is as follows:

Babu is about done now thinking about how he's going to search for the shortest path. With luck, if he can cut out many branches in his search for the shortest path, his Branch-and-Bound method will take him much less than O(N!) to find the shortest path. There is no guarantee, of course. And the amount of time he needs may still be a lot. But he has the whole weekend to do it. His trip will start on the Monday to come.