# The Trials And Tribulations Of The Traveling Salesman

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

As we dive deeper and deeper into the world of computer science, one thing starts to become very clear, very quickly: some problems seem to show up again and again, in the strangest of forms. In fact, some of the most famous problems in the history of computer science have no specific origin that anyone knows of. Instead, the same problem shows up in different forms and avatars, in different places around the world, at different time periods.

The hardest problems in software are the most fun to solveāāāand some of them havenāt even been figured out yet! One of these hard problems is the traveling salesman problem, and depending on whom you ask, it might be the most notorious of them all.

I first heard about the traveling salesman problem a few years ago, and it seemed super daunting to me at the time. To be totally honest, even coming back to it now, it still feels a little bit daunting, and it might seem scary to you, too. But something is different this time around: weāve got a whole wealth of knowledge and context to draw from! Throughout this series, weāve been building upon our foundation core of computer science, and returning to some of the same concepts repeatedly in an effort to understand them on a more technical levelāāābut only when we feel fully equipped to do so. The same goes for this look into the the traveling salesman problem.

In order to understand why this problem is so notorious, we need to wrap our heads around what it is, how we can solve it, why it is important, and what makes it so hard. It might sound overwhelming, but weāll get through it together, one step at a time.

So, letās hop to it!

### Geometry, circuits, and a dude named Hamilton

The idea behind the ** traveling salesman problem** (

*TSP*) is rooted in a rather realistic problem that many people have probably actually encountered. The thesis is simple: a salesman has to travel to every single city in an area, visiting each city only once. Additionally, he needs to end up in the same city where he starts his journey from.

The actual āproblemā within the traveling salesman problem is finding the most *efficient* route for the salesman to take. There are obviously many different routes to choose from, but finding the best oneāāāthe one that will require the least cost or distance of our salesmanāāāis what weāre solving for.

In more ways than one, the practical aspects of this problem are reminscient of The Seven Bridges of KĆ¶nigsberg, a mathematical problem that weāre already familiar with, which was the basis for Eulerās invention of the field called āthe geometry of positionā, which we now know today as *graph theory*.

But graph theory didnāt end with Euler and the city of KĆ¶nigsberg! Indeed, the Seven Bridge problem was just the beginning, and the traveling salesman problem is a prime example of someone building upon the ideas of those who came before him.

The āsomeoneā in this scenario is none other than William Rowan Hamilton, an Irish physicist and mathematician who was inspired by and subsequently continued the research of mathematicians who came before him in order to create a subset of mathematical problems that are directly tied to the traveling salesman problem that we are familiar with today.

In the late 1800ās, both Hamilton and the British mathematician Thomas Kirkman were working on mathematical problems that were fundamentally similar to TSP. Hamiltonās claim to fame was his work on deriving a something called a ** Hamiltonian path** , which bears resemblance to Eulerās famous Eulerian path.

While a Eulerian path is a path where every single edge in a graph is visited once, a Hamiltonian path is one where every single *vertex* is visited exactly once.

By the same token, a Eulerian circuit is a Eulerian path that ends at the same vertex where it began, touching each *edge* once. A ** Hamiltonian circuit** , on the other hand, is a Hamiltonian path that ends at the same vertex where it began, and touches each

*vertex*exactly once.

A good rule of thumb to determine whether a path through a graph is Hamiltonian or Eulerian is this:

in a

, every edge doesnāt need to be visited, but every node must visitedāāābut only once! In comparison, in anHamiltonian pathEulerian path, some vertices could be visited multiple times, but every edge can only ever be visited once.

The reason that Hamiltonās work, which is built upon Eulerās formulations, comes up in the context of the famous traveling salesman problem is that the job of the salesmanāāātraveling to each city exactly once and ending up where he beganāāāis really nothing more than a graph problem!

Hamiltonās work expanded graph theory to the point where he was actually solving the TSP before it was really a thing. Hamilton invented a game that was similar to the traveling salesman problem, which he called the ** icosian game** , whose objective was to find a path through the points of a dodecahedron, or a polygon with 12 flat faces.

Hamiltonās game was eventually turned into an actual board game. And, if we think about it, even the icosian game is really just another variation on the traveling salesman problem! Just as as dodecahedron has 20 vertices, we could imagine Hamiltonās game as a map of 20 cities. Using this analogy, our traveling salesman would need to find a way through 20 cities, visiting each city once, and ending up exactly where he started.

Thus, the traveling salesman problem can really just be reformulated to be represented as a graph. Luckily, we have covered a whole lot of different topics when it comes to complex graphs. Weāve got a solid foundation to build upon, just like Hamilton did!

Once weāre able to wrap our heads around the fact that the traveling salesman problem is really just a graph traversal problem, we can start getting down to business. In other words, we can start trying to *solve* this problem. For our purposes, we wonāt worry ourselves with trying to get the best solution or using the most efficient approach. Instead, weāll start by simply trying to get some kind of solution to begin with. Using the old adage attributed to Kent Beck, we must first āMake it workā before we can even begin to think about making it ārightā or āfastā.

So, letās get to work and get our salesman on the road!

### Brute-force to begin with

The traveling salesman in our example problem has it pretty luckyāāāhe only has to travel between four cities. For simplicityās sake, weāll call these four cities w, x, y, and z. Because we know that TSP is a graph problem, we can visualize our salesmanās possible routes in the form of ** a weighted, undirected graph**. Weāll recall that a

*weighted*graph is one whose edges have a cost or distance associated with them, and an

*undirected*graph is one whose edges have a bidirectional flow.

Looking at an illustrated example of our salesmanās graph, weāll see that some routes have a greater distance or cost than others. Weāll also notice that our salesman can travel between any two vertices easily.

*w*?

Letās say that our salesman lives in city w, so thatās where heāll start his journey from. Since weāre looking for a Hamiltonian cycle/circuit, we know that this is also where he will need to end up at the end of his adventures. So, how can we solve for the optimal path so that our salesman starts and ends at city (node) w, but also visits every single city (x, y, and z) in the process?

Remember, weāre not going to think about the most efficient strategyāāājust one that *works*. Since weāre going to use the brute-force approach, letās think about what weāre really trying to solve for here. The brute-force approach effectively means that weāll solve our problem by figuring out every single possiblity and then picking the best one from the lot. In other words, we want to find every single ** permutation** or

**that our salesman could take. Every single of one of these potential routes is basically a directed graph in its own right; we know that weāll start at the node w and end at w, but we just donāt know quite yet which order the nodes x, y, and z will appear in between.**

*possible path*So, we need to solve every single possible combination to determine the different ways that we could arrange x, y, and z to replace the nodes that are currently filled with ?ās. That doesnāt seem *too* terrible.

But how do we actually solve for these ? nodes, exactly? Well, even though weāre using a less-than-ideal brute-force approach, we can lean on *recursion* to make our strategy a little more elegant.

The basic idea in the recursive TSP approach is that, for every single node that we visit, we keep track of the nodes that we can navigate to next, and then recursively visit them.

Eventually, weāll end up with no more nodes to check, which will be our recursive base case, effectively ending our recursive calls to visit nodes. Donāt worry if this seem complicated and a little confusing at the moment; it will become a lot clearer with an example. So, letās recursively brute-force our way through these cities and help our salesman get home safe and sound!

We already know that our salesman is going to start at node w. Thus, this is the node weāll start with and visit first. There are two things we will need to do for every single node that we visitāāāweāll need to remember the fact that weāve visited it, and weāll need to keep track of the nodes that we can *potentially* visit next.

Here, weāre using a list notation to keep track of the nodes that we can navigate to from node w. At first, we can navigate to three different places: {x, y, z}.

Recall that recursion is basically the idea that a āfunction calls itself from within itselfā. In other words, as part of solving this problem, weāre going to have to apply the same process and technique to every single node, again and again. So thatās exactly what weāll do next! For every single node that we can potentially navigate to, we will recursively visit it.

Notice that weāre starting to create a tree-like structure. For each of the potential nodes to visit from the starting node w, we now have three potential child āpathsā that we could take. Again, for each of these three vertices, weāre keeping track of the node itself that weāre visiting as well as any potential nodes that we can visit next, which havenāt already been visited in that path.

Recursion is about repetition, so weāre going to do the same thing once again! The next step of recursion expands our tree once again.

Weāll notice that, since each of the three nodes x, y, and z had two nodes that we could potentially visit next, each of them have spawned of two of their own recursive calls. Weāll continue to make recursive calls in the same way and, in the process, weāll start to see that weāre creating different permutations using the same nodes.

Weāll notice that weāre now at the third level of recursive calls, and each node has only one possible place to visit next. We can probably guess what happens nextāāāour tree is going to grow again, and each of the bottom-level nodes is going to spawn a single recursive call of its own, since each node has only one unvisited vertex that it can potentially check.

The image shown below illustrates the next two levels of recursive calls.

Notice that, when we get to the fourth level of child nodes, there is nowhere left to visit; every node has an empty list ({} ) of nodes that it can visit. This means that weāve finished recursively checking for all permutations of paths.

However, since weāre solving for a Hamiltonian cycle, we arenāt exactly done with each of these paths just yet. We know we want to end back where we started at node w, so in reality, each of these last recurisvely-determined nodes needs to link back to vertex w.

Once we add node w to the end of each of the possible paths, weāre done expanding all of our permutations! Hooray! Remember how we determined earlier that every single of one of these potential routes is just a directed graph? All of those directed graphs have now revealed themselves. If we start from the root node, w, and work down each possible branch of this ātreeā, weāll see that there are six distinct paths, which are really just six directed graphs! Pretty cool, right?

So, what comes next? Weāve expanded all of these pathsā¦but how do we know which one is the shorted one of them all?

We havenāt really been considering the cost or distance of this weighted graph so far, but thatās all about to change. Now that weāve expanded this problem and found all of its possible permutations, we need to consider the total cost of each of these paths in order to find the shortest one. This is when an adjacency matrix representation of our original graph will come in handy. Recall that an ** adjacency matrix** is a matrix representation of exactly

*which*nodes in a graph contain edges between them. We can tweak our typical adjacency matrix so that, instead of just 1ās and 0ās, we can actually store the weight of each edge.

Now that we have an adjacency matrix to help us, letās use it to do some mathāāāsome *recursive* math, that is!

### Mirror mirror on the wall, which is the shortest path of them all?

In order to determine which of these six possible paths is the shortest oneāāāand thus the ideal choice for our salesmanāāāwe need to build up the cost of every single one of these paths.

Since weāve used recursion to expand these paths until we hit our base case of āno more nodes left to visitā, we can start to close up these recursive calls, and calculate the cost of each path along the way.

Once we know the cost between two vertices, we can sum the distance between them, and the remove the node from the tree. This will make more sense with an example, so letās work our way from the lowest-level of this tree until we have found a solution for the shortest path.

We know that every single one of these branchesāāāeach of which represents a permutation of this particularly problemāāāends with the node that we started on: node w. Weāll start with node w, and calculate the cost for our salesman to travel there.

Well, since our salesman *starts at* node w, the cost of traveling to node w is actually just 0. This makes sense if we think about it, because our salesman is already *at* that vertex, so it isnāt going to ācostā him anything to travel there! So, the math for the bottom level is pretty easyāāāthe cost to get from w to w is 0. Next, weāll apply the same technique again, but this time, weāll move one level up.

For example, if we refer to our adjacency matrix from the previous section, weāll see that the cost of traveling from w to z is 3. Since weāre traveling from w ā> w ā> z, we can sum the distances between each of these vertices as we go. Traveling from w ā> w is 0, and traveling from w ā> z is 3, so we are essentially calculating 0 + 3. In a similar vein, the cost from z to y is 2. So, we will need to calculate w ā> w ā> z -> y, which is 0 + 3 + 2.

The drawing below illlustrates how this addition slowly works its way up the tree, condensing the recursive calls that built it up in the first place.

Through this process, weāre effectively building up the cost or distance of each path, one level at a time, using our tree structure. Each time that we sum the distance between two nodes, we can remove the bottom node (the deeper of the two nodes being added together) from the tree, since we donāt need to use it anymore.

It is worth mentioning that ** we need to keep track of each of these paths** , even after we finish doing the work of adding up their costs. For the sake of brevity, the paths themselves are not included in the illustrations shown here. However, it is crucial to keep track of which nodes were at the bottom of the treeāāāotherwise, weād lose the entire path itself!

We will continue this process, but at some point, an odd thing is going to happen. In the next iteration of this recursive addition, weāll notice that we come to an interesting fork in the roadāāāliterally! When we reach the third level and have condensed the bottom part of the tree, we have two possible options of how we can proceed with our additon.

For example, looking at the child paths/branches from node x, we could either sum the distance from x to y, or we could sum the distance from x to z. So, how do we decide which one to choose?

Our gut instinct would tell us that weāre looking for the *shortest path*, which probably means that weāll want to choose the *smaller* of the two values. And thatās exactly what weāll do! Weāll choose the path from z leading back to x, since the cost of that path is 6, which is definitely smaller than the path from y leading back to x, which is 9.

Once weāve chosen the smallest of the two paths in our āfork in the roadā, we are left with just three paths. All thatās left to do is to figure out the total cost of from x to w, y to w, and z to w. Referring to our adjacency matrix, weāll see that these distances are 6, 1, and 3, respectively.

We can add these to the total costs of the paths that weāve been recursively summing this whole time. In the illustration above, weāll see that the three shortest paths that weāve determined are actually noted down for convenience. As it turns out, there is one path that costs 12, and two paths that both cost 11. One of those travels from w to y, and takes the route of w -> y -> x -> z -> w, while the other travels from w to z, and takes the route of w -> z-> x -> u -> w.

Since two of our three paths are equivalently small in size, it doesnāt really matter which one we choose; both of them are the āshortest pathā in solving the traveling salesman problem.

And there we have it! Weāve solved for a Hamiltonian circuit by finding teh shortest path, with a distance/cost of 11, that starts and ends at node w.

Solving that was pretty awesome, right? It seemed super daunting at first, but as we worked through it, it got easier with each step. But hereās the thing: we had to take a *lot* of steps to do this. We knew from the beginning that we werenāt going to have the most elegant solution to this problemāāāwe were just trying to get *something* working. But just how painful is the brute-force method, exactly?

Well, what if instead of a salesman who has to travel to four cities, we were trying to help out a salesman who had to travel to a whole lot more cities? What if the number of cities that they had to visit was n? How bad would our brute-force technique be?

Well, in our first example, n = 4. Weāll recall that, since we had already visited our first city (node w), we only had to make three recursive calls. In other words, we had to make 4āāā1, or nāāā1 recursive calls.

But, for each of those recursive calls, we had to spawn off two more recursive calls! That is to say, for each potential city that we *could* visit from the three nodes x, y, and z, we had 4āāā2 = 2 options of paths to take. In abstract terms, weād effectively have nāāā2 recursive calls at the next level of our tree.

If we continue figuring out this math, weāll see that, at each level of the tree, we are basically on the path to finding a number that is going to be a factorial. To be more specific, weāre going to end up with n!, or ** n factorial**.

Now, when we were dealing with a salesman who needed to visit just four cities, this really wasnāt too terrible of scenario to deal with. But, what happens when n is something much, much larger than 4? Most salesmen and women arenāt going to be traveling just to four cities; in almost every realistic case, n is going to be a much larger number!

Well, to get a sense of how unscalable a factorial algorithm is, we neednāt increase the value of n by all that much. For example, when n = 4, we made 3! or 6 recursive calls. But if we had increased this only slightly so that n = 5, we would make 4! or 24 recursive calls, which would lead to a much, much larger tree. And what about when n = 10? That would result in 9! recursive calls, which is a really huge number: 362,880 to be exact. We probably canāt even imagine what would happen if our salesman had to travel to every city in the country, or even just 10 cities for that matter!

Surely, there must be a better way of helping our traveling salesman out so that heās not traveling forever? Well, there certainly is. But more on that next week. In the meantime, someone should really tell this salesman about eBayāāāit would probably solve him a whole lot of heartache!

### Resources

Unsurprisingly, there are many resources on the traveling salesman problem. However, not all of them are necessarily easy to understand! Some of them dive deep into the theory and mathematics of the problem, and it can be hard to find beginner-friendly content. Here are a few resources that are fairly easy to understand, and a good place to get started if youāre looking to learn more about TSP!

- Travelling Salesman Problem, 0612 TV w/ NERDfirst
- Coding Challenge #35.1: Traveling Salesperson, The Coding Train
- History of TSP, University of Waterloo, Department of Mathematics
- The Traveling Salesman problem, Professor Amanur Rahman Saiyed
- A brief History of the Travelling Salesman Problem, Nigel Cummings
- The Traveling Salesman Problem and Its Variation, Gregory Gutin and Abraham P. Punnen

Are u yet to post the link for other programming approaches of TSP apart from Brute force method ? If present then will you please share the link below.

Good article.

Thanks.