Traveling Salesperson Problem

After completing this section, you should be able to:

1. Distinguish between brute force algorithms and greedy algorithms.
2. List all distinct Hamilton cycles of a complete graph.
3. Apply brute force method to solve traveling salesperson applications.
4. Apply nearest neighbor method to solve traveling salesperson applications.

An algorithm is a sequence of steps that can be used to solve a particular problem. We have solved many problems in this chapter, and the procedures that we used were different types of algorithms. In this section, we will use two common types of algorithms, a brute force algorithm and a greedy algorithm. A brute force algorithm begins by listing every possible solution and applying each one until the best solution is found. A greedy algorithm approaches a problem in stages, making the apparent best choice at each stage, then linking the choices together into an overall solution which may or may not be the best solution.

To understand the difference between these two algorithms, consider the tree diagram in . Suppose we want to find the path from left to right with the largest total sum. For example, branch A in the tree diagram has a sum of \(10+2+11+13=36\).

To be certain that you pick the branch with greatest sum, you could list each sum from each of the different branches:

A: \(10+2+11+13=36\)

B: \(10+2+11+8=31\)

C: \(10+2+15+1=28\)

D: \(10+2+15+6=33\)

Condensed — the full section is in OpenStax Contemporary Mathematics.

Now let’s focus our attention on the graph theory application known as the traveling salesperson problem (TSP) in which we must find the shortest route to visit a number of locations and return to the starting point.

Recall from Hamilton Cycles, the officer in the U.S. Air Force who is stationed at Vandenberg Air Force base and must drive to visit three other California Air Force bases before returning to Vandenberg. The officer needed to visit each base once. We looked at the weighted graph in representing the four U.S. Air Force bases: Vandenberg, Edwards, Los Angeles, and Beal and the distances between them.

Any route that visits each base and returns to the start would be a Hamilton cycle on the graph. If the officer wants to travel the shortest distance, this will correspond to a Hamilton cycle of lowest weight. We saw in that there are six distinct Hamilton cycles (directed cycles) in a complete graph with four vertices, but some lie on the same cycle (undirected cycle) in the graph.

Since the distance between bases is the same in either direction, it does not matter if the officer travels clockwise or counterclockwise. So, there are really only three possible distances as shown in .

The possible distances are:

So, a Hamilton cycle of least weight is V → B → E → L → V (or the reverse direction). The officer should travel from Vandenberg to Beal to Edwards, to Los Angeles, and back to Vandenberg.

Notice that we listed all of the Hamilton cycles and found their weights when we solved the TSP about the officer from Vandenberg. This is a skill you will need to practice. To make sure you don't miss any, you can calculate the number of possible Hamilton cycles in a complete graph. It is also helpful to know that half of the directed cycles in a complete graph are the same cycle in reverse direction, so, you only have to calculate half the number of possible weights, and the rest are duplicates.

The method we have been using to find a Hamilton cycle of least weight in a complete graph is a brute force algorithm, so it is called the brute force method. The steps in the brute force method are:

Step 1: Calculate the number of distinct Hamilton cycles and the number of possible weights.

Step 2: List all possible Hamilton cycles.

Step 3: Find the weight of each cycle.

Step 4: Identify the Hamilton cycle of lowest weight.

Now suppose that the officer needed a cycle that visited all 5 of the Air Force bases in . There would be \((5-1)!=4!=4\times 3\times 2\times 1=24\) different arrangements of vertices and \(\frac{(5-1)!}{2}=\frac{4!}{2}=\frac{24}{2}=12\) distances to compare using the brute force method. If you consider 10 Air Force bases, there would be \((10-1)!=9!=9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1=362,880\) different arrangements and \(\frac{(10-1)!}{2}=\frac{9!}{2}=\frac{9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1}{2}=181,440\) distances to consider. There must be another way!

When the brute force method is impractical for solving a traveling salesperson problem, an alternative is a greedy algorithm known as the nearest neighbor method, which always visit the closest or least costly place first. This method finds a Hamilton cycle of relatively low weight in a complete graph in which, at each phase, the next vertex is chosen by comparing the edges between the current vertex and the remaining vertices to find the lowest weight. Since the nearest neighbor method is a greedy algorithm, it usually doesn’t give the best solution, but it usually gives a solution that is "good enough." Most importantly, the number of steps will be the number of vertices. That’s right! A problem with 10 vertices requires 10 steps, not 362,880. Let’s look at an example to see how it works.

Suppose that a candidate for governor wants to hold rallies around the state. They plan to leave their home in city A, visit cities B, C, D, E, and F each once, and return home. The airfare between cities is indicated in the graph in .

Let’s help the candidate keep costs of travel down by applying the nearest neighbor method to find a Hamilton cycle that has a reasonably low weight. Begin by marking starting vertex as \({V}_{1}\) for "visited 1st." Then to compare the weights of the edges between A and vertices adjacent to A: $250, $210, $300, $200, and $100 as shown in . The lowest of these is $100, which is the edge between A and F.

Mark F as \({V}_{2}\) for "visited 2nd" then compare the weights of the edges between F and the remaining vertices adjacent to F: $170, $330, $150 and $350 as shown in . The lowest of these is $150, which is the edge between F and D.

Mark D as \({V}_{3}\) for "visited 3rd." Next, compare the weights of the edges between D and the remaining vertices adjacent to D: $120, $310, and $270 as shown in . The lowest of these is $120, which is the edge between D and B.

So, mark B as \({V}_{4}\) for "visited 4th." Finally, compare the weights of the edges between B and the remaining vertices adjacent to B: $160 and $220 as shown in . The lower amount is $160, which is the edge between B and E.

Now you can mark E as \({V}_{5}\) and mark the only remaining vertex, which is C, as \({V}_{6}\). This is shown in . Make a note of the weight of the edge from E to C, which is $180, and from C back to A, which is $210.

Condensed — the full section is in OpenStax Contemporary Mathematics.

• A brute force algorithm always finds the ideal solution but can be impractical whereas a greedy algorithm is efficient but usually does not lead to the ideal solution.
• A Hamilton cycle of lowest weight is a solution to the traveling salesperson problem.
• The brute force method finds a Hamilton cycle of lowest weight in a complete graph.
• The nearest neighbor method is a greedy algorithm that finds a Hamilton cycle of relatively low weight in a complete graph.

• In a complete graph with \(n\) vertices, the number of distinct Hamilton cycles is \((n-1)!\).
• In a complete graph with \(n\) vertices, there are at most \(\frac{(n-1)!}{2}\) different weights of Hamilton cycles.