Contemporary Mathematics: Contemporary Mathematics at Nebraska

In the last section, we considered optimizing a walking route for a postal carrier. How is this different than the requirements of a package delivery driver? While the postal carrier needed to walk down every street (edge) to deliver the mail, the package delivery driver instead needs to visit every one of a set of delivery locations. Instead of looking for a circuit that covers every edge once, the package deliverer is interested in a circuit that visits every vertex once.

Hamiltonian paths and circuits are named for William Rowan Hamilton who studied them in the 1800’s. Sometimes you will see them referred to simply as Hamilton paths and circuits.

Unlike with Euler circuits, there is no nice theorem that allows us to instantly determine whether or not a Hamiltonian circuit exists for all graphs.

¹

There are some theorems that can be used in specific circumstances, such as Dirac’s theorem, which says that a Hamiltonian circuit must exist on a graph with \(n\) vertices if each vertex has degree \(n/2\) or greater.

With Hamiltonian circuits, our focus will not be on existence, but on the question of optimization; given a graph where the edges have weights, can we find the optimal Hamiltonian circuit; the one with lowest total weight.

To answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches. The first option that might come to mind is to just try all different possible circuits.

The Brute Force Algorithm is optimal; it will always produce the Hamiltonian circuit with minimum weight. Is it efficient? To answer that question, we need to consider how many Hamiltonian circuits a graph could have. For simplicity, let’s look at the worst-case possibility, where every vertex is connected to every other vertex. This is called a complete graph.

Using a type of mathematics called combinatorics, we can find a formula that gives the number of unique Hamilton circuits for a complete graph with any number, \(n\text{,}\) of vertices. The results are as follows:

As you can see, the number of circuits starts small but grows extremely quickly. If a computer looked at one billion circuits a second, it would still take almost two years to examine all the possible circuits with only 20 vertices. With 30 vertices, the most powerful supercomputer in the world would take about 140 million years to do so! Certainly Brute Force is not an efficient algorithm.

Unfortunately, no one has yet found an efficient and optimal algorithm to solve the TSP, and it is very unlikely anyone ever will.

²

This is actually related to a famous problem in computer science. It is considered important enough that a $1 million reward has been offered for a solution.

Since it is not practical to use Brute Force to solve the problem, we turn instead to heuristic algorithms: efficient algorithms that give approximate solutions. In other words, heuristic algorithms are fast, but are not guaranteed to produce the optimal circuit.

We ended up finding the worst circuit in the graph! What happened? Unfortunately, while it is very easy to implement, the NNA is a greedy algorithm, meaning it only looks at the immediate decision without considering the consequences in the future. In this case, following the edge AD forced us to use the very expensive edge BC later.

Going back to Example 16.1.6, how could we improve the outcome? One option would be to redo the nearest neighbor algorithm with a different starting point to see if the result changed. Since nearest neighbor is so fast, doing it several times isn’t a big deal.