The Trials And Tribulations Of The Traveling Salesman

Vaidehi Joshi
Nov 6, 2017 · 17 min read
The trials and tribulations of the traveling salesman!

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.
William Rowan Hamilton, Wikimedia Commons
Comparing Eulerian and Hamiltonian paths.
TSP as a Hamiltonian circuit problem.

in a Hamiltonian path, every edge doesn’t need to be visited, but every node must visited — but only once! In comparison, in an Eulerian 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 icosian game, © Puzzle Museum

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.

How can we solve for the optimal path starting and ending at node w?
Every permutation is, on its own, a directed graph.

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!

Generating recursive calls for TSP, part 1.
Generating recursive calls for TSP, part 2.
Generating recursive calls for TSP, part 3.
Generating recursive calls for TSP, part 4.

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?

We can use an adjacency matrix to help us keep track of edge costs/distances.

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.

Calculating recursive costs using recursion for TSP, part 1.
Understanding the logic behind recursive addition for TSP.
Calculating recursive costs using recursion for TSP, part 2.
Calculating recursive costs using recursion for TSP, part 3.
Calculating recursive costs using recursion for TSP, part 4.
Calculating recursive costs using recursion for TSP, part 5.

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 the shortest path, with a distance/cost of 11, that starts and ends at node w.

We’ve solved for a Hamiltonian circuit!
Solving for n cities in the TSP.
Building up an unscalable “n factorial” problem.
The traveling salesman is not a fan of factorial algorithms!

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!

  1. Coding Challenge #35.1: Traveling Salesperson, The Coding Train
  2. History of TSP, University of Waterloo, Department of Mathematics
  3. The Traveling Salesman problem, Professor Amanur Rahman Saiyed
  4. A brief History of the Travelling Salesman Problem, Nigel Cummings
  5. The Traveling Salesman Problem and Its Variation, Gregory Gutin and Abraham P. Punnen

basecs

Exploring the basics of computer science, every Monday, for a year.

Vaidehi Joshi

Written by

Writing words, writing code. Sometimes doing both at once.

basecs

basecs

Exploring the basics of computer science, every Monday, for a year.