The Trials And Tribulations Of The Traveling Salesman

Aswe 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 traveling salesman seeks to visit each city once, and end up in the same place he started.

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.

William Rowan Hamilton, Wikimedia Commons

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.

Comparing Eulerian and Hamiltonian paths.

In the late 1800’s, both Hamilton and the British mathematician Thomas Kirkmanwere 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.

TSP as a Hamiltonian circuit problem.

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

in a Hamiltonian path, every edge doesn’t need to be visited, but every node must visited — but only once! In comparison, in anEulerian 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!

The icosian game, invented by W.R. Hamilton in the 1800's.

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.

Hamilton’s icosian game

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 topicswhen 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!