basecs
Published in

basecs

The Trials And Tribulations Of The Traveling Salesman

The trials and tribulations of the traveling salesman!

Geometry, circuits, and a dude named Hamilton

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 icosian game, invented by W.R. Hamilton in the 1800's.
Hamilton’s icosian game, © Puzzle Museum

Brute-force to begin with

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.

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.

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?

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.

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

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store