Published in

basecs

# Geometry, circuits, and a dude named Hamilton

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.

# Brute-force to begin with

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.

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`.

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

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.

# 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

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