# Speeding Up The Traveling Salesman Using Dynamic Programming

###
Vaidehi Joshi
Nov 13 '17
*Originally published at Medium on Nov 13, 2017*

A large part of what makes computer science hard is that it can be hard to know where to start when it comes to solving a difficult, seemingly unsurmountable problem.

One of the reasons that some things can seem so tricky is that theyâ€™re multistep problems, and they involve us first understanding the problem, then considering the simplest solution, then iterating upon that solution to make it better, more efficient, and more elegant. I often think of the phrase that has been attributed to Kent Beck who said, *â€śMake it work, make it right, make itÂ fast.â€ť*

Some of the most complex problems in computer science are complex for *this* very reason: they involve these three distinct parts, and it can feel super overwhelming if we donâ€™t consider these three steps as unique points in our problem-solving strategy. The complex problems are the ones where we are forced to step back, and try to break up our problem-solving process into a segmented process, rather than trying to magically find the perfect solution in one go. To be honest, finding the perfect solution in one go *rarely* actually everÂ happens.

Weâ€™ve covered some tricky topics throughout the course of this series, but one of the more complicated topics presented itself more recently when we encountered the **traveling salesman problem** (*TSP*). Since we have already taken the first step of trying to find a solution to TSP that just works, we can now concern ourselves with the next steps: making it right (or more elegant), and hopefully a little bitÂ faster.

### No Fun Factorials

When we first stumbled upon the traveling salesman problem, we were dealing with a salesman who had a fairly easy task: to visit four cities in some order, as long as he visited each city once and ended up at the same city that he startedÂ in.

Now, the reason that this was an â€śeasyâ€ť task, so to speak, was simply because of the fact that visiting four cities isnâ€™t really a lot to do. In algorithmic terms, we were able to solve this problem and find the shortest path for our salesman using a brute-force technique, combined with recursion. We were able to determine that the brute-force approach was, by definion, a factorial algorithm. In our example, we determined that, for a salesman who needs to visit four cities would mean making 3! or â€śthree factorialâ€ť function calls, which equalsÂ 6.

We also started realizing that the factorial runtime of the brute-force technique for solving TSP was going to be unscalable over time. In fact, we realized that it was going to be unscalable almost *immediately*! For example, what would happen when our traveling salesman needed to visit not just *four* cities, but *five* cities? When we were dealing with four cities, we made six recursive calls. So, adding one extra city shouldnâ€™t be too difficult, right? After all, itâ€™s just *one*Â city.

Well, not exactly. Hereâ€™s how our algorithm scales from just four cities, toÂ five:

When our salesman only had to visit four cities, we made six recursive calls. But now, we have literally *quadrupled* our tree of â€śpotential pathsâ€ť, which seems really, really, *really* bad. Solving TSP for five cities means that we need to make 4! or four factorial recursive calls using the brute-force technique. As it turns out, 4! equals 24, which means we have to now make 24 recursive calls in order to accomodate just one additional city in our traveling salesmanâ€™s map.

If we compare the illustrated version of the â€śtreeâ€ť of recursive function calls from our previous example of TSP to the one that is drawn above, we start to get a pretty good idea of just *how* unsustainable a factorial algorithm reallyÂ is.

We have seen quite a few different forms of Big O Notation throughout this series, including the good and the bad. So, where do factorial algorithms fit into this narrative?

If constant, logarithmic, and linear time are good, and quadratic and exponential time are bad, there is only one thing left to explore: the ugly. Factorial algorithms are exactly that: theÂ ugly.

For an algorithm that runs in ** factorial** , or

**O(n!)**time, any operations that need to run will end up taking n! more time in relation to the data that is being operated upon, or the input dataÂ set.

Okay, but what does this *actually* mean? Well, letâ€™s look at how a factorial algorithm compares to all the other forms of Big O Notation that weâ€™re already familiarÂ with.

Weâ€™ll notice almost immediately that algorithms that grow in factorial time are super slow and ineffcient as input size grows. For example, weâ€™ll see that even a slight increase in the number of elements to be operated upon by a factorial algorithm causes it to shoot up in the number of operations required to run. If we compare this to linearithmic, linear, or even just *quadratic* time algorithmsâ€” which are still pretty bad in their own rightâ€Šâ€”â€Šweâ€™ll see that factorial algorithms are obsecenely terrible in comparison!

All of this is to say: our first approach to solving TSP using brute-force recursion is probably not the best solution. Yes, it works, but itâ€™s probably not as â€śrightâ€ť as it could be; it could stand to be improved, and surely could be made more elegant. And, of course, it is not fastâ€Šâ€”â€ŠatÂ all!

So, how can we improve upon this first attempt that weÂ made?

Well, if we think back to our foray into ** dynamic programming** (

*DP*), weâ€™ll remember that there is more than one approach when it comes to solving a DP problem. In our initial stab at this problem, we attempted to solve TSP using a kind of

**: we started with a large, complex problem, and broke it down into smaller parts. Then, when we got down to our base case, and expanded the problem down to its smallest possible parts, we used recursion to build up all the possible paths that our traveling salesman could take, which allowed us to choose the best (the shortest) permutation of all the paths that we hadÂ found.**

*top down approach*In the process, we figured out one way to solve the traveling salesman problem. But what if we approached it a different manner? What would happen if we took our top down approach and turned it upsideÂ down?

Thereâ€™s only one way to find outâ€Šâ€”â€Šwe have to try itÂ out!

### Turning TSP on itsÂ head

If we look at our top down methodology from last week, weâ€™ll see that we have enumerated through all of the permutations of pathsâ€Šâ€”â€Šthat is to say, we have brute-forced our way to determine every single route that our traveling salesman couldÂ take.

This methodology isnâ€™t particularly elegant, is kind of messy, and, as we have already determined, will simply never scale as our input size grows. But ignoring all of those issues for a moment, letâ€™s just take a look at this â€śtreeâ€ť of recursive function calls onceÂ again.

On second glance, weâ€™ll notice that there is something interesting going on here: weâ€™re starting with the more complex function call initially, and then, from within that, we are invoking three recursive function calls from *within* it. Each of those three recursive function calls spins off two more recursive calls of its own, which creates the third level of this function call â€śtreeâ€ť. This is, of course, keeping in tune with our working definition of a *top down* approach: starting with the largest problem first, and breaking it down into its smallest parts. But, now that we can see the smallest parts more obviously, we can change our approach from a top down method to a bottom upÂ method.

Weâ€™ll recall that a ** bottom up** dynamic programming approach starts with the smallest possible subproblems, figures out a solution to them, and then slowly builds itself up to solve the larger, more complicated subproblem. In the context of our â€śfunction call treeâ€ť, the smallest possible subproblem are the smallest possible function calls. Weâ€™ll see that the smallest function calls are the simplest onesâ€Šâ€”â€Šthe ones that have

*no recursive calls*within them. In our case, these are the function calls at the very bottom of our â€śfunction call treeâ€ť, which lead back to our starting node, node w, which is the city that our traveling salesman is â€śstartingâ€ť from, and will inevitably have to â€śendâ€ť upÂ at.

Now that weâ€™ve identified the smallest possible subproblems, we can turn TSP on its head. Weâ€™ll flip our top down approach to this problem and, instead, use a bottom up approach here. Letâ€™s start with our three simplest functionÂ calls.

Weâ€™ll see that each of these calls connects back to w, as we would expect. Recall that weâ€™re using a list notationto keep track of the nodes that we can navigate to. Since weâ€™re dealing with the smallest possible subproblem(s), there is nowhere that we can navigate to from these nodes; instead, all we can do is go back to our starting node, w. This is why each of the lists for these three subproblems is emptyÂ ({}).

However, we do need to keep track of cost and distance here, since inevitably, weâ€™re still going to have to find the shortest path for our traveling salesman, regardless of whether weâ€™re using a *top down* or *bottom up* approach. Thus, weâ€™re going to have to keep track of the distance between nodes as we build up our â€śbottom upâ€ť tree. In the image above, weâ€™ll see that we have the values 6, 1, and 3 next to nodes x, y, and z, respectively. These number represent the distance to get from each node back to the origin node,Â w.

When we first tried to solve TSP, we used an adjacency matrix to help us keep track of the distances between nodes in our graph. Weâ€™ll lean on our adjacency matrix in this approach yetÂ again.

However, in our bottom up approach, weâ€™ll use it to enumerate all the function calls that lead to one another. This is strikingly different than our top down approach, when we were using our adjacency matrix to help us enumerate all the possible paths. In our bottom up approach, weâ€™re trying to be a bit more elegant about how we do things, so weâ€™re aiming to not enumerate more than we need to! This will make more sense as we go on, but itâ€™s important to note the difference between enumerating ** paths** versus enumerating

**.**

*functionÂ calls*So, what would the second level of our function call â€śtreeâ€ť look like? Well, the question that weâ€™re trying to answer for each of our smallest possible subproblems here isÂ this:

If we are at the simplest possible version of this function call and cannot call anything recursively from within this function, what other function could possibly call thisÂ one?

Another way of thinking about it is in terms of nodes. Ultimately, weâ€™re trying to determine which possible nodes would allow us to get to the node that weâ€™re looking at. So, in the case of node x, the only way to get to node x would potentially be node y or node z. Remember that weâ€™re using a bottom up approach here, so weâ€™re almost retracing our steps backwards, starting at the end, and working our way back through theÂ circle.

Notice, again, that weâ€™re keeping track of the cost/distance from each of these nodes to the next. Weâ€™re going to need them prettyÂ soon!

Again, we can expand this function call â€śtreeâ€ť a bit more to add another level. Remember, weâ€™re trying to answer the question: *what other function could possibly call this function that we cannot expand anyÂ further?*

In the drawing depicted here, weâ€™ll see what this actually looks like in practice. For example, looking at the leftmost branch of this function call â€śtreeâ€ť, weâ€™ll notice that the only possible function call that will allow us to get to an empty node x is from either node y or node z, where the set contains only a possible â€śnextâ€ť node of x, like so: {x}. For both node y and z in the leftmost subtree, weâ€™ll see that the only possible way to get to y is from node z, when the set contains both x and y (or {x, y}). Similarly, the only possible way to get to z is from node y, when the set contains both x and z (or {x,Â z}).

This is a visualization exemplifies what we mean when we say that we are enumerating *function calls* rather than enumerating *potential paths*. As we continue to determine all the possible function calls that allow us to call other functions from within them, something starts to become very obvious: we have some overlapping subproblems here!

Weâ€™ll notice that there are two function calls that are instances of z when its set contains both x and y (or {x, y}), which is highlighted in yellow. Similarly, there are two function calls that are instances of y when its set contains both x and z (or {x, z}), highlighted in pink. Finally, weâ€™ll see two function calls that are instances of x when its set contains both y and z (or {y, z}), highlighted inÂ green.

Dynamic programming is all about identifying repeated work and being smarter and more efficient with our approach so that we donâ€™t actually have to repeat ourselves! So, letâ€™s cut out this repetition and use some dynamic programming to make things a little better for our traveling salesman.

### Dynamic programming to the salesmanâ€™s rescue

Now that weâ€™ve identified our overlapping and recurring subproblems, thereâ€™s only one thing left to do: eliminate the repetition, ofÂ course!

Using our function call â€śtreeâ€ť, we can rearrange some of our function calls so that weâ€™re not actually repeating ourselves in level three of thisÂ tree.

We can do this by cutting down our repeated subproblems so that they only show up once. Then, weâ€™ll reconfigure the bottom level of our tree so that it is still *accurate*, but also that we each function call show up *once*, notÂ twice.

Now it starts to become apparent how the bottom up approach is different than our top down method fromÂ before.

Weâ€™ll see that we no longer need to do the work of generating that entire bottom level of our function call â€śtreeâ€ť in order to figure out all o the recursive function calls. Nor do we need to determine all the possible paths that our traveling salesman could take by using brute force. Instead, weâ€™re enumerating through function calls, finding the repeated ones, and condensing our â€śtreeâ€ť of function calls as we continue to buildÂ it.

Once weâ€™ve eliminated the repeated subproblems, we can do the work of actually finding the shortest path. Remember that we will need to use our adjacency matrix to figure out the distance between one node to another. But, weâ€™ll also notice that weâ€™re not having to repeat ourselves nearly as much because we wonâ€™t see the same numbers appear too many times as we sum themÂ up.

In the illustration shown below, each of the function calls that allow our salesman to traverse from one node to another has a number (the cost or distance) associated with it. As we continue down this tree, weâ€™ll sum up the cost of each set of function calls. For example, if we choose the function calls that lead from w <- x <- y <- z, weâ€™ll sum up the cost between these nodes, which amounts to 6 + 4 + 2 =Â 12.

When we get down to the third level of our function call â€śtreeâ€ť, weâ€™ll see that we have two numbers that we can choose from. Recall that we had a similar scenario happen to us in our top down approach last week: we had two different paths with two different costs/distances to choose from. We ended up choosing the smaller of the two cost, since weâ€™re trying to find the shortest path for our salesman. In this case, we have two different function calls, with two different costs/distances to choose from. Again, weâ€™ll choose the smaller of the two costs, since weâ€™re still trying to find the shortest path here,Â too!

Eventually, as we continue sum the distances/costs, weâ€™ll see that we ended up witht he exact same results as our brute-force method from last week. The shortest cost for our traveling salesman is going to be 11, and there are two possible paths that would allow for them to achieve that lowest cost. However, using the bottom up approach, weâ€™ve optimized our TSP algorithm, since we no longer have six recursive calls being made in this method. Furthermore, weâ€™re also not generating as big of a tree structure! If we think back to when we were first introduced to dynamic programming, weâ€™ll recall that we could also use ** memoization** and save the results of our function calls as we calculate them, optimizing our solution evenÂ further.

Okay, so we started down this path in an effort to take the next step in the adage of â€ś*Make it work, make it right, make itÂ fast*.â€ť

We have arguably made our workable solution much better, and certainly more elegant, and far less repetitive. The illustration shown here exemplifies how the bottom up DP approach would scale for a traveling salesman problem where the salesman has to visit five cities instead of four. Weâ€™ll see that weâ€™re still making a lot of calls, but our function call â€śtreeâ€ť is a bit slimmer and significantly better thanÂ before.

By using dynamic programming, weâ€™ve made our solution for the traveling salesman problem just a little bit better by choosing to smartly enumerate function calls rather than brute-force our way through every single possible path that our salesman couldÂ take.

The only question we have to answer now is, of course, how does the runtime of this method compare to our ugly factorial, O(n!) runtime fromÂ earlier?

Well, as it turns out, the bottom up approach that weâ€™ve been exploring here is really the foundations of something called the ** Held-Karp algorithm** , which is also often referred to as the

**. This algorithm was derived in 1962, by both Michael Held and Richard M. Karp as well as Richard Bellman, who was working independently on his own related research at theÂ time.**

*Bellman-Held-Karp algorithm*The Held-Karp algorithm actually proposed the bottom up dynamic programming approach as a solution to improving the brute-force method of solving the traveling salesman problem. Bellman, Held, and Karpâ€™s algorithm was determined to run in ** exponential** time, since it still does a bulk of the work of enumerating through all the potential sets of function calls that are possible. The exponential runtime of the Held-Karp algorithm is still not perfectâ€Šâ€”â€Šitâ€™s far from it, in fact! But, itâ€™s not as ugly as a factorial algorithm, and itâ€™s still an improvement.

And, to be honest, Iâ€™m sure the traveling salesman would be happy to take whatever he couldÂ get.

### Resources

The traveling salesman problem has been written about, researched, and taught extensively. As it turns out, there are many different approaches when it comes to attempting to solve it, and the Held-Karp algorithm is just one of them. If you want to dig deeper into this particular topic, here are some good places toÂ start.

- Travelling Salesman Problem, 0612 TV w/ NERDfirst
- Traveling Salesman Problem Dynamic Programming Held-Karp, TusharÂ Roy
- What is an NP-complete in computer science?, StackOverflow
- Big O Notation and Complexity, Kestrel Blackmore
- A Dynamic Programming Algorithm for TSP,Â Coursera
- Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches, Rajesh Matai, Surya Singh, and Murari LalÂ Mittal

Saving to read later since i had problems implementing the traveling salesman using dp last year in uni :D

Too many text for reading at work, saving too. Would be an interesting challenge to implement this