Traveling Salesman Problem
Finding the shortest Hamiltonian cycle that starts and ends at the same vertex and visits every other vertex once, including the classical case on complete graphs, the practical case using least distances between vertices, and estimating bounds with the nearest neighbor and deleted vertex algorithms.
Hamiltonian Paths
A Hamiltonian path is a path which visits every vertex once, with no repetition of vertices.
Note that a Hamiltonian path does not require every edge to be visited. However, no edge can be repeated without repeating a vertex and so no edge is repeated either.
Examples
Hamiltonian Cycles
A Hamiltonian cycle is a cycle that visits every vertex with no vertex repeated except the start / end.
Note that the same graph can have multiple Hamiltonian Cycles.
The cycle AEFDABCA is not Hamiltonian since A is repeated in the middle.
The cycle AEFDCBA is Hamiltonian.
Both graphs above are Hamiltonian (they are the same graph).
Hamiltonian and semi-Hamiltonian graphs
When a graph has a Hamiltonian cycle, we call it a Hamiltonian graph.
When a graph has a Hamiltonian path, but not a Hamiltonian cycle, we call it a semi-Hamiltonian graph.
Definition of the Traveling Salesman Problem
The traveling salesman problem is a scenario where we are looking for the shortest path that starts and ends at the same vertex on a graph, and visits every other vertex exactly once.
Each of these paths is a Hamiltonian cycle by definition. To find the solution, we're looking for the Hamiltonian cycle with the smallest total weight.
A Hamiltonian cycle with total weight 3+8+6+3+7=27.
A Hamiltonian cycle with total weight 3+8+9+3+4=27
Classical Traveling Salesman Problem
The classical traveling salesman problem is a special case of the problem where the graph we're looking at is complete and where the shortest path between any two vertices is the edge between those vertices.
There is no "good" way to find the shortest Hamiltonian cycle other than finding all the Hamiltonian cycles and comparing their weights. There are, however, ways to find upper and lower bounds on the optimal solution. Then we know that the optimal solution is somewhere between those two.
Nearest neighbor algorithm as an upper bound
In the special case where the graph is complete, we can use the so-called nearest neighbor algorithm to find an upper bound on the least weight Hamiltonian path.
A complete graph is always Hamiltonian.
The algorithm works like this:
Choose any starting vertex.
Move to the nearest vertex that has not yet been visited (choosing at random if there is a tie)
Repeat step 2 until all vertices are visited.
Move back to the starting vertex.
Add up the weights of this Hamiltonian cycle.
Because this cycle has visited every vertex exactly once and returned to the start, it is at least a solution to the traveling salesman problem. And if there is a more optimal solution, it's only because it has lower weight. That means that our solution can be considered an upper bound on the traveling salesman problem.
Deleted vertex algorithm as an lower bound
The deleted vertex algorithm is a method for determining a lower bound on the solution to the traveling salesman problem in the case where the graph is complete.
The algorithm is based on the following observation: If you take a traveling salesman tour, which is a loop through all the vertices, and you delete one of the vertices, what you end up with is a tree that spans all of the remaining vertices. That remaining tree cannot be any smaller than the minimum spanning tree.
We can work backwards from this fact by deleting a chosen vertex from our graph and finding the minimum spanning tree of what remains. Next, we reconnect our deleted vertex to this minimum spanning tree. And because we're looking for a cycle, we need at least two edges connected to our deleted vertex. We therefore choose the two shortest edges that connect to the MST.
Practical TSP and table of least distances
The practical traveling salesman problem is the broader case of searching for the shortest Hamiltonian circuit in a graph that is not necessarily complete, and where the edges between vertices are not necessarily the shortest path between those vertices.
For example, in the graph below, the edge CE has weight 8, but CA+AE has a weight 7, so the shortest path between C and E is not the direct one.
The good news is that we can turn a practical traveling salesman problem into a classical case by finding the least distances between each pair of vertices.
The graph ABCDE is not complete, and the edge CE=8 is longer than path CAE=7. Let's build a table of least distances. In each cell, we put the shortest distance between the row and column vertex.
Note that since the graph is undirected, the table is symmetric, so there's no need to fill in the bottom half.
Now we essentially have this updated, complete graph, where every edge is the shortest distance between its vertices.
This takes us back to the classical case, where we can use the nearest neighbor and deleted vertex algorithms to find upper and lower bounds.
Nice work completing Traveling Salesman Problem, here's a quick recap of what we covered:
Skills covered
Exercises checked off