Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo
Contemporary Mathematics

12.9 Traveling Salesperson Problem

Contemporary Mathematics12.9 Traveling Salesperson Problem

Table of contents
  1. Preface
  2. 1 Sets
    1. Introduction
    2. 1.1 Basic Set Concepts
    3. 1.2 Subsets
    4. 1.3 Understanding Venn Diagrams
    5. 1.4 Set Operations with Two Sets
    6. 1.5 Set Operations with Three Sets
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  3. 2 Logic
    1. Introduction
    2. 2.1 Statements and Quantifiers
    3. 2.2 Compound Statements
    4. 2.3 Constructing Truth Tables
    5. 2.4 Truth Tables for the Conditional and Biconditional
    6. 2.5 Equivalent Statements
    7. 2.6 De Morgan’s Laws
    8. 2.7 Logical Arguments
    9. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  4. 3 Real Number Systems and Number Theory
    1. Introduction
    2. 3.1 Prime and Composite Numbers
    3. 3.2 The Integers
    4. 3.3 Order of Operations
    5. 3.4 Rational Numbers
    6. 3.5 Irrational Numbers
    7. 3.6 Real Numbers
    8. 3.7 Clock Arithmetic
    9. 3.8 Exponents
    10. 3.9 Scientific Notation
    11. 3.10 Arithmetic Sequences
    12. 3.11 Geometric Sequences
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  5. 4 Number Representation and Calculation
    1. Introduction
    2. 4.1 Hindu-Arabic Positional System
    3. 4.2 Early Numeration Systems
    4. 4.3 Converting with Base Systems
    5. 4.4 Addition and Subtraction in Base Systems
    6. 4.5 Multiplication and Division in Base Systems
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  6. 5 Algebra
    1. Introduction
    2. 5.1 Algebraic Expressions
    3. 5.2 Linear Equations in One Variable with Applications
    4. 5.3 Linear Inequalities in One Variable with Applications
    5. 5.4 Ratios and Proportions
    6. 5.5 Graphing Linear Equations and Inequalities
    7. 5.6 Quadratic Equations with Two Variables with Applications
    8. 5.7 Functions
    9. 5.8 Graphing Functions
    10. 5.9 Systems of Linear Equations in Two Variables
    11. 5.10 Systems of Linear Inequalities in Two Variables
    12. 5.11 Linear Programming
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  7. 6 Money Management
    1. Introduction
    2. 6.1 Understanding Percent
    3. 6.2 Discounts, Markups, and Sales Tax
    4. 6.3 Simple Interest
    5. 6.4 Compound Interest
    6. 6.5 Making a Personal Budget
    7. 6.6 Methods of Savings
    8. 6.7 Investments
    9. 6.8 The Basics of Loans
    10. 6.9 Understanding Student Loans
    11. 6.10 Credit Cards
    12. 6.11 Buying or Leasing a Car
    13. 6.12 Renting and Homeownership
    14. 6.13 Income Tax
    15. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  8. 7 Probability
    1. Introduction
    2. 7.1 The Multiplication Rule for Counting
    3. 7.2 Permutations
    4. 7.3 Combinations
    5. 7.4 Tree Diagrams, Tables, and Outcomes
    6. 7.5 Basic Concepts of Probability
    7. 7.6 Probability with Permutations and Combinations
    8. 7.7 What Are the Odds?
    9. 7.8 The Addition Rule for Probability
    10. 7.9 Conditional Probability and the Multiplication Rule
    11. 7.10 The Binomial Distribution
    12. 7.11 Expected Value
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  9. 8 Statistics
    1. Introduction
    2. 8.1 Gathering and Organizing Data
    3. 8.2 Visualizing Data
    4. 8.3 Mean, Median and Mode
    5. 8.4 Range and Standard Deviation
    6. 8.5 Percentiles
    7. 8.6 The Normal Distribution
    8. 8.7 Applications of the Normal Distribution
    9. 8.8 Scatter Plots, Correlation, and Regression Lines
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  10. 9 Metric Measurement
    1. Introduction
    2. 9.1 The Metric System
    3. 9.2 Measuring Area
    4. 9.3 Measuring Volume
    5. 9.4 Measuring Weight
    6. 9.5 Measuring Temperature
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  11. 10 Geometry
    1. Introduction
    2. 10.1 Points, Lines, and Planes
    3. 10.2 Angles
    4. 10.3 Triangles
    5. 10.4 Polygons, Perimeter, and Circumference
    6. 10.5 Tessellations
    7. 10.6 Area
    8. 10.7 Volume and Surface Area
    9. 10.8 Right Triangle Trigonometry
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  12. 11 Voting and Apportionment
    1. Introduction
    2. 11.1 Voting Methods
    3. 11.2 Fairness in Voting Methods
    4. 11.3 Standard Divisors, Standard Quotas, and the Apportionment Problem
    5. 11.4 Apportionment Methods
    6. 11.5 Fairness in Apportionment Methods
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  13. 12 Graph Theory
    1. Introduction
    2. 12.1 Graph Basics
    3. 12.2 Graph Structures
    4. 12.3 Comparing Graphs
    5. 12.4 Navigating Graphs
    6. 12.5 Euler Circuits
    7. 12.6 Euler Trails
    8. 12.7 Hamilton Cycles
    9. 12.8 Hamilton Paths
    10. 12.9 Traveling Salesperson Problem
    11. 12.10 Trees
    12. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  14. 13 Math and...
    1. Introduction
    2. 13.1 Math and Art
    3. 13.2 Math and the Environment
    4. 13.3 Math and Medicine
    5. 13.4 Math and Music
    6. 13.5 Math and Sports
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  15. A | Co-Req Appendix: Integer Powers of 10
  16. Answer Key
    1. Chapter 1
    2. Chapter 2
    3. Chapter 3
    4. Chapter 4
    5. Chapter 5
    6. Chapter 6
    7. Chapter 7
    8. Chapter 8
    9. Chapter 9
    10. Chapter 10
    11. Chapter 11
    12. Chapter 12
    13. Chapter 13
  17. Index
Three doors are shown side-by-side.
Figure 12.186 Each door on the route of a traveling salesperson can be represented as a vertex on a graph. (credit: "Three in a row, Heriot Row" by Jason Mason/Flickr, CC BY 2.1)

Learning Objectives

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.

We looked at Hamilton cycles and paths in the previous sections Hamilton Cycles and Hamilton Paths. In this section, we will analyze Hamilton cycles in complete weighted graphs to find the shortest route to visit a number of locations and return to the starting point. Besides the many routing applications in which we need the shortest distance, there are also applications in which we search for the route that is least expensive or takes the least time. Here are a few less common applications that you can read about on a website set up by the mathematics department at the University of Waterloo in Ontario, Canada:

  • Design of fiber optic networks
  • Minimizing fuel expenses for repositioning satellites
  • Development of semi-conductors for microchips
  • A technique for mapping mammalian chromosomes in genome sequencing

Before we look at approaches to solving applications like these, let's discuss the two types of algorithms we will use.

Brute Force and Greedy Algorithms

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 Figure 12.187. 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=3610+2+11+13=36.

A graph has 15 vertices. The vertices are labeled 1 to 15. 10 branches into 2 and 7. 2 branches into 11 and 15. 11 branches into 13 and 8. 15 branches into 1 and 6. 7 branches into 3 and 4. 3 branches into 20 and 14. 4 branches into 11 and 5. 13, 8, 1, 6, 20, 14, 11, and 5 are labeled A to H.
Figure 12.187 Points Along Different Paths

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=3610+2+11+13=36

B: 10+2+11+8=3110+2+11+8=31

C: 10+2+15+1=2810+2+15+1=28

D: 10+2+15+6=3310+2+15+6=33

E: 10+7+3+20=4010+7+3+20=40

F: 10+7+3+14=3410+7+3+14=34

G: 10+7+4+11=3210+7+4+11=32

H: 10+7+4+5=2610+7+4+5=26

Then we know with certainty that branch E has the greatest sum.

A graph has 15 vertices. The vertices are labeled 1 to 15. 10 branches into 2 and 7. 2 branches into 11 and 15. 11 branches into 13 and 8. 15 branches into 1 and 6. 7 branches into 3 and 4. 3 branches into 20 and 14. 4 branches into 11 and 5. 13, 8, 1, 6, 20, 14, 11, and 5 are labeled A to H. The edges 10 to 7, 7 to 3, and 3 to 20 are highlighted. An arrow from E points to 20.
Figure 12.188 Branch E

Now suppose that you wanted to find the branch with the highest value, but you only were shown the tree diagram in phases, one step at a time.

A graph has 3 vertices. The vertices are labeled 10, 2, and 7. 10 branches into 2 and 7. The edge, 10 to 7 is highlighted.
Figure 12.189 Tree Diagram Phase 1

After phase 1, you would have chosen the branch with 10 and 7. So far, you are following the same branch. Let’s look at the next phase.

A graph has 5 vertices. The vertices are labeled 10, 2, 7, 3, and 4. 10 branches into 2 and 7. 7 branches into 3 and 4. The edges, 10 to 7 and 7 to 4 are highlighted.
Figure 12.190 Tree Diagram Phase 2

After phase 2, based on the information you have, you will choose the branch with 10, 7 and 4. Now, you are following a different branch than before, but it is the best choice based on the information you have. Let’s look at the last phase.

A graph has 7 vertices. The vertices are labeled 10, 2, 7, 3, 4, 11, and 15. 10 branches into 2 and 7. 7 branches into 3 and 4. 4 branches into 11 and 5. The edges, 10 to 7, 7 to 4, and 4 to 11 are highlighted. 11 and 5 are labeled G and H.
Figure 12.191 Tree Diagram Phase 3

After phase 3, you will choose branch G which has a sum of 32.

The process of adding the values on each branch and selecting the highest sum is an example of a brute force algorithm because all options were explored in detail. The process of choosing the branch in phases, based on the best choice at each phase is a greedy algorithm. Although a brute force algorithm gives us the ideal solution, it can take a very long time to implement. Imagine a tree diagram with thousands or even millions of branches. It might not be possible to check all the sums. A greedy algorithm, on the other hand, can be completed in a relatively short time, and generally leads to good solutions, but not necessarily the ideal solution.

Example 12.42

Distinguishing between Brute Force and Greedy Algorithms

A cashier rings up a sale for $4.63 cents in U.S. currency. The customer pays with a $5 bill. The cashier would like to give the customer $0.37 in change using the fewest coins possible. The coins that can be used are quarters ($0.25), dimes ($0.10), nickels ($0.05), and pennies ($0.01). The cashier starts by selecting the coin of highest value less than or equal to $0.37, which is a quarter. This leaves $0.37$0.25=$0.12$0.37$0.25=$0.12. The cashier selects the coin of highest value less than or equal to $0.12, which is a dime. This leaves $0.12$0.10=$0.02$0.12$0.10=$0.02. The cashier selects the coin of highest value less than or equal to $0.02, which is a penny. This leaves $0.02$0.01=$0.01$0.02$0.01=$0.01. The cashier selects the coin of highest value less than or equal to $0.01, which is a penny. This leaves no remainder. The cashier used one quarter, one dime, and two pennies, which is four coins. Use this information to answer the following questions.

  1. Is the cashier’s approach an example of a greedy algorithm or a brute force algorithm? Explain how you know.
  2. The cashier’s solution is the best solution. In other words, four is the fewest number of coins possible. Is this consistent with the results of an algorithm of this kind? Explain your reasoning.

Your Turn 12.42

1.
Suppose that you lost the combination to a combination lock that consisted of three digits, and each was selected from the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. You desperately need to open the lock without breaking it. You decide to check all possible combinations methodically, 000, then 001, then 002, and so on until you find the right combination. Is this an example of a brute force algorithm or a greedy algorithm?

The Traveling Salesperson Problem

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 Figure 12.192 representing the four U.S. Air Force bases: Vandenberg, Edwards, Los Angeles, and Beal and the distances between them.

A graph represents the four California air force bases. The graph has four vertices: E, B, V, and L. The edge, E B is labeld 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles.
Figure 12.192 Graph of Four California Air Force Bases

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 Table 12.11 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.

Complete Graph Cycle Cycle Cycle
A graph has four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d.
A graph has four vertices, a, b, c, and d.  Edges connect a b, b c, c d, d a, a c, and b d. The edges, a c, and b d are in dashed lines.
A graph has four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a d, and b c are in dashed lines.
A graph has four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a b, and d c are in dashed lines.
Clockwise Hamilton Cycle
A graph has four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a c, and b d are in dashed lines. Directed arrows flow from a to b, b to c, c to d, and d to a.

abcda

A graph has four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, ad, and bc are in dashed lines. Directed edges flow from a to b, b to d, d to c, and c to a.

abdca

A graph has four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a b, and dc are in dashed lines. Directed edges flow from a to c, c to b, b to d, and d to a.

acbda

Counterclockwise Hamilton Cycle
A graph has four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a c, and b d are in dashed lines. Directed edges flow from a to d, d to c, c to b, and b to a.

adcba

A graph has four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a d, and bc are in dashed lines. The directed edges flow from a to c, c to d, d to b, and b to a.

acdba

A graph has four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a b, and dc are in dashed lines. The edges flow from a to d, d to b, b to c, and c to a.

adbca

Table 12.11 Hamilton Cycles in a Complete Graph with Four Vertices

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 Figure 12.193.

Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines. Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines. Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines.
Figure 12.193 Three Possible Distances

The possible distances are:

396+410+106+159=1071207+410+439+159=1215396+439+106+207=1148396+410+106+159=1071207+410+439+159=1215396+439+106+207=1148

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

Finding Weights of All Hamilton Cycles in Complete Graphs

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.

FORMULA

In a complete graph with nn vertices,

  • The number of distinct Hamilton cycles is (n1)!(n1)!.
  • There are at most (n1)!2(n1)!2 different weights of Hamilton cycles.

Checkpoint

TIP! When listing all the distinct Hamilton cycles in a complete graph, you can start them all at any vertex you choose. Remember, the cycle abca is the same cycle as bcab so there is no need to list both.

Example 12.43

Calculating Possible Weights of Hamilton Cycles

Suppose you have a complete weighted graph with vertices N, M, O, and P.

  1. Use the formula (n1)!(n1)! to calculate the number of distinct Hamilton cycles in the graph.
  2. Use the formula (n1)!2(n1)!2 to calculate the greatest number of different weights possible for the Hamilton cycles.
  3. Are all of the distinct Hamilton cycles listed here? How do you know?
    Cycle 1: NMOPN
    Cycle 2: NMPON
    Cycle 3: NOMPN
    Cycle 4: NOPMN
    Cycle 5: NPMON
    Cycle 6: NPOMN
  4. Which pairs of cycles must have the same weights? How do you know?

Checkpoint

TIP! When listing the possible cycles, ignore the vertex where the cycle begins and ends and focus on the ways to arrange the letters that represent the vertices in the middle. Using a systematic approach is best; for example, if you must arrange the letters M, O, and P, first list all those arrangements beginning with M, then beginning with O, and then beginning with P, as we did in Example 12.42.

Your Turn 12.43

1.
A complete weighted graph has vertices V, W, X, Y, and Z. List all the distinct Hamilton cycles. Use V as the starting vertex. Identify the pairs of cycles that have the same weight because they are reverses of each other.

The Brute Force Method

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.

Example 12.44

Applying the Brute Force Method

On the next assignment, the air force officer must leave from Travis Air Force base, visit Beal, Edwards, and Vandenberg Air Force bases each exactly once and return to Travis Air Force base. There is no need to visit Los Angeles Air Force base. Use Figure 12.194 to find the shortest route.

A graph represents the five California air force bases. The graph has five vertices: E, B, V, L, and T. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. The edge, E T is labeled 370 miles. The edge, L T is labeled 396 miles. The edge, B T is labeled 84 miles. The edge, V T is labeled 396 miles.
Figure 12.194 Distances between Five California Air Force Bases

Your Turn 12.44

1.
Suppose that the Air Force officer needed to leave from Travis Air Force base, visit each of Beal, Edwards, and Los Angeles Air Force bases exactly once and return to Travis. Use Figure 12.278 to find the shortest route.

Now suppose that the officer needed a cycle that visited all 5 of the Air Force bases in Figure 12.194. There would be (51)!=4!=4×3×2×1=24(51)!=4!=4×3×2×1=24 different arrangements of vertices and (51)!2=4!2=242=12(51)!2=4!2=242=12 distances to compare using the brute force method. If you consider 10 Air Force bases, there would be (101)!=9!=987654321=362,880(101)!=9!=987654321=362,880 different arrangements and (101)!2=9!2=9876543212=181,440(101)!2=9!2=9876543212=181,440 distances to consider. There must be another way!

The Nearest Neighbor Method

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 Figure 12.196.

A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars.
Figure 12.196 Airfares between Cities A, B, C, D, E, and F

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 V1V1 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 Figure 12.197. The lowest of these is $100, which is the edge between A and F.

A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. The edges from A are in dashed lines. A is labeled V 1.
Figure 12.197 Finding the Second Vertex

Mark F as V2V2 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 Figure 12.198. The lowest of these is $150, which is the edge between F and D.

A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. The edges from F are in dashed lines. A is labeled V 1. F is labeled V 2.
Figure 12.198 Finding the Third Vertex

Mark D as V3V3 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 Figure 12.199. The lowest of these is $120, which is the edge between D and B.

A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. A is labeled V 1. F is labeled V 2. D is labeled V 3. The edges, B D, C D, and D E are in dashed lines.
Figure 12.199 Finding the Fourth Vertex

So, mark B as V4V4 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 Figure 12.200. The lower amount is $160, which is the edge between B and E.

A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. A is labeled V 1. F is labeled V 2. D is labeled V 3. B is labeled V 4. The edges, B E and B C are in dashed lines.
Figure 12.200 Finding the Fifth Vertex

Now you can mark E as V5V5 and mark the only remaining vertex, which is C, as V6V6. This is shown in Figure 12.201. 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.

A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. A is labeled V 1. F is labeled V 2. D is labeled V 3. B is labeled V 4. E is labeled V 5. C is labeled V 6. The edges, A C, and E C are in dashed lines.
Figure 12.201 Finding the Sixth Vertex

The Hamilton cycle we found is AFDBECA. The weight of the circuit is $100+$150+$120+$160+$180+$210=$920$100+$150+$120+$160+$180+$210=$920. This may or may not be the route with the lowest cost, but there is a good chance it is very close since the weights are most of the lowest weights on the graph and we found it in six steps instead of finding 120 different Hamilton cycles and calculating 60 weights. Let’s summarize the procedure that we used.

Step 1: Select the starting vertex and label V1V1 for "visited 1st." Identify the edge of lowest weight between V1V1 and the remaining vertices.

Step 2: Label the vertex at the end of the edge of lowest weight that you found in previous step as VnVn where the subscript n indicates the order the vertex is visited. Identify the edge of lowest weight between VnVn and the vertices that remain to be visited.

Step 3: If vertices remain that have not been visited, repeat Step 2. Otherwise, a Hamilton cycle of low weight is V1V2VnV1V1V2VnV1.

Example 12.45

Using the Nearest Neighbor Method

Suppose that the candidate for governor wants to hold rallies around the state but time before the election is very limited. They would like 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 not as important as the time of travel, which is indicated in Figure 12.202. Use the nearest neighbor method to find a route with relatively low travel time. What is the total travel time of the route that you found?

A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 120 minutes, 140 minutes, 85 minutes, 90 minutes, and 180 minutes. Edges from B leading to C, D, E, and F are labeled 100 minutes, 80 minutes, 95 minutes, and 110 minutes. Edges from C to D, E, and F are labeled 220 minutes, 200 minutes, and 75 minutes. Edges from D to E and F are labeled 130 minutes and 70 minutes. An edge from E to F is labeled 210 minutes.
Figure 12.202 Travel Times between Cities A, B, C, D, E and F

Your Turn 12.45

1.
Use the nearest neighbor method to find a Hamilton cycle of relatively low weight beginning and ending at vertex D in Figure 12.240 and find its total weight. Give your answer in hours and minutes.

Check Your Understanding

75.
The advantage of a greedy algorithm is that it is more efficient.
  1. True
  2. False
76.
The disadvantage of a brute force algorithm is that it does not always give the ideal solution.
  1. True
  2. False
77.
The nearest neighbor method is an example of a brute force algorithm.
  1. True
  2. False
78.
The brute force method is an example of a greedy algorithm.
  1. True
  2. False
79.
The brute force method is used to find a Hamilton cycle of least weight in a complete graph.
  1. True
  2. False
80.
The nearest neighbor method is used to find the ideal solution to the traveling salesperson problem.
  1. True
  2. False
81.
The traveling salesman problem involves finding the shortest route to travel between two points.
  1. True
  2. False
82.
The traveling salesman problem can be represented as finding a Hamilton cycle of least weight on a weighted graph.
  1. True
  2. False
83.
There is always more than one Hamilton cycle of least weight, a given Hamilton cycle and the reverse of that Hamilton cycle.
  1. True
  2. False
84.
The greatest possible number of distinct weights for the Hamilton cycles of a complete graph with n vertices is ( n -1)!
  1. True
  2. False

Section 12.9 Exercises

For the following exercises, determine whether the algorithm described is a greedy algorithm or a brute force algorithm.
1 .
The algorithm for creating graph colorings in the section Navigating Graphs involved coloring the vertex of highest degree first, coloring as many other vertices as possible each color from highest to lowest degree, then repeating this process for the remaining vertices.
2 .
Pallets of goods are to be transported on 10 flatbed trucks which have weight limits. To determine which goods will be shipped together, all the possible ways to divide the goods into 10 groups is listed and the total weight of each group is calculated.
3 .
A wedding planner is creating a seating arrangement for the reception dinner. The couple has provided a list of which guests must be seated together. The wedding planner prefers to use the fewest tables possible so that there is more space to mingle at the reception. The planner creates a list of all possible seating arrangements and selects one that meets these criteria.
4 .
Packages must be loaded into freight cars to be transported by train. It is preferred to use the fewest freight cars possible to keep the costs down. As each freight car is packed, the package with the largest girth that will fit in the freight car is loaded and this is repeated until the freight car can hold no more packages. When a freight car can hold no more packages, the next freight car is loaded.
For the following exercises, use the figure to calculate the number of distinct Hamilton cycles beginning at the given vertex in the given graph. How many of those could possibly result in a different weight?
Four graphs. Graph A has four vertices: a, b, c, and d. The edges are labeled as follows: a b, 3; b d, 3; d c, 1; c a, 2; a d, 1; b c, 2. Graph B has five vertices: e, f, g, h, and I. The edges are labeled as follows: e f, 2-thirds; f g, 5-twelfths; g h, 1-twelfth; h i, 3-fourths; i e, 1-fourth; e h, 1-half; e g, 1-sixth; f i, -third; f h, 5-sixths; g i, 1. Graph C has five vertices: i, j, k, m, and n. The curved edges are labeled as follows: k m, 20; m n, 30; n j, 40; j i, 50; i k, 10. The straight edges are labeled as follows: k j, 90; k n, 60; m i, 100; m j, 70; n i, 80. Graph d has four vertices; o, p, q, and r. The edges are labeled as follows: o p, 1.7; p q, 4.3; q r, 3.5; r o, 2.9 p r, 3.; o p, 1.2.
5 .
Graph A, vertex a
6 .
Graph B, vertex e
7 .
Graph C, vertex k
8 .
Graph D, vertex o
For the following exercises, use the figure to list all the distinct Hamilton cycles beginning at the given vertex in the given graph. Indicate which pairs of Hamilton cycles are reverses of each other.
Four graphs. Graph A has four vertices: a, b, c, and d. The edges are labeled as follows: a b, 3; b d, 3; d c, 1; c a, 2; a d, 1; b c, 2. Graph B has five vertices: e, f, g, h, and I. The edges are labeled as follows: e f, 2-thirds; f g, 5-twelfths; g h, 1-twelfth; h i, 3-fourths; i e, 1-fourth; e h, 1-half; e g, 1-sixth; f i, -third; f h, 5-sixths; g i, 1. Graph C has five vertices: i, j, k, m, and n. The curved edges are labeled as follows: k m, 20; m n, 30; n j, 40; j i, 50; i k, 10. The straight edges are labeled as follows: k j, 90; k n, 60; m i, 100; m j, 70; n i, 80. Graph d has four vertices; o, p, q, and r. The edges are labeled as follows: o p, 1.7; p q, 4.3; q r, 3.5; r o, 2.9 p r, 3.; o p, 1.2.
9 .
Graph A, vertex a
10 .
Graph B, vertex e
11 .
Graph C, vertex k
12 .
Graph D, vertex o
For the following exercises, use the figure to find a Hamilton cycle of least weight for the given graph, beginning at the given vertex, and using the brute force method. What is the weight of the cycle?
Four graphs. Graph A has four vertices: a, b, c, and d. The edges are labeled as follows: a b, 3; b d, 3; d c, 1; c a, 2; a d, 1; b c, 2. Graph B has five vertices: e, f, g, h, and I. The edges are labeled as follows: e f, 2-thirds; f g, 5-twelfths; g h, 1-twelfth; h i, 3-fourths; i e, 1-fourth; e h, 1-half; e g, 1-sixth; f i, -third; f h, 5-sixths; g i, 1. Graph C has five vertices: i, j, k, m, and n. The curved edges are labeled as follows: k m, 20; m n, 30; n j, 40; j i, 50; i k, 10. The straight edges are labeled as follows: k j, 90; k n, 60; m i, 100; m j, 70; n i, 80. Graph d has four vertices; o, p, q, and r. The edges are labeled as follows: o p, 1.7; p q, 4.3; q r, 3.5; r o, 2.9 p r, 3.; o p, 1.2.
13 .
Graph A, vertex a
14 .
Graph B, vertex e
15 .
Graph C, vertex k
16 .
Graph D, vertex o
For the following exercises, use the figure to find a Hamilton cycle of low weight for the given graph, beginning at the given vertex, and using the nearest neighbor method. What is the weight of the cycle?
Four graphs. Graph A has four vertices: a, b, c, and d. The edges are labeled as follows: a b, 3; b d, 3; d c, 1; c a, 2; a d, 1; b c, 2. Graph B has five vertices: e, f, g, h, and I. The edges are labeled as follows: e f, 2-thirds; f g, 5-twelfths; g h, 1-twelfth; h i, 3-fourths; i e, 1-fourth; e h, 1-half; e g, 1-sixth; f i, -third; f h, 5-sixths; g i, 1. Graph C has five vertices: i, j, k, m, and n. The curved edges are labeled as follows: k m, 20; m n, 30; n j, 40; j i, 50; i k, 10. The straight edges are labeled as follows: k j, 90; k n, 60; m i, 100; m j, 70; n i, 80. Graph d has four vertices; o, p, q, and r. The edges are labeled as follows: o p, 1.7; p q, 4.3; q r, 3.5; r o, 2.9 p r, 3.; o p, 1.2.
17 .
Graph A, vertex a
18 .
Graph B, vertex e
19 .
Graph C, vertex k
20 .
Graph D, vertex o
For the following exercises, use your solutions to Exercises 13–20 to compare the results of the brute force method to the results of the nearest neighbor method for each graph. Indicate whether the Hamilton cycle was the same or different and whether the weights were the same or different. If the weights are different, indicate which method gave the lower weight. Are your observations consistent with the characteristics of brute force algorithms and greedy algorithms? Explain your reasoning.
21 .
Graph A, vertex a
22 .
Graph B, vertex e
23 .
Graph C, vertex k
24 .
Graph D, vertex o
For the following exercises, use the table to create a complete weighted graph in which the vertices are the given cities, and the weights are the distances between them.
Cities U V W X Y Z
U 0 89 37 49 54 28
V 89 0 76 68 92 112
W 37 76 0 45 52 49
X 49 68 45 0 66 47
Y 54 92 52 66 0 29
Z 28 112 49 47 29 0
Distances between Cities U, V, W, X, Y, and Z in kilometers
25 .
U, V, W, X
26 .
U, W, Y, Z
27 .
U, X, Y, Z
28 .
U, V, W, X, Y
29 .
U, W, X, Y, Z
30 .
U, V, W, X, Y, Z
For the following exercises, use your solutions to Exercises 25–30 and the nearest neighbor method to find a Hamilton cycle to solve the traveling salesperson problem of finding a reasonably short route to leave from city U, visit each of the other cities listed and return to city U. Indicate the distance required to travel the route you found.
31 .
U, V, W, X
32 .
U, W, Y, Z
33 .
U, X, Y, Z
34 .
U, V, W, X, Y
35 .
U, W, X, Y, Z
36 .
U, V, W, X, Y, Z
For the following exercises, use your solutions to Exercises 25–30 and the brute force method to find a Hamilton cycle of lowest weight to solve the traveling salesperson problem of finding a shortest route to leave from city U, visit each of the other cities listed and return to city U. Indicate the distance required to travel the route you found.
37 .
U, V, W, X
38 .
U, W, Y, Z
39 .
U, X, Y, Z
40 .
U, V, W, X, Y
41 .
U, W, X, Y, Z
For the following exercises, use your solutions to the indicated exercises to compare the results of the brute force method to the results of the nearest neighbor method for each traveling salesman problem of finding a reasonably short route to leave from city U, visit each of the other cities listed and return to city U. Indicate whether the greedy algorithm resulted in a Hamilton cycle of the same weight, lower weight, or higher weight. Is this consistent with the characteristics of brute force algorithms and greedy algorithms? Explain your reasoning
42 .
Exercises 32 and 38: U, W, Y, Z
43 .
Exercises 31 and 37: U, V, W, X
44 .
Exercises 34 and 40: U, V, W, X, Y
45 .
Exercises 35 and 41: U, W, X, Y, Z
46 .
Exercises 33 and 39: U, X, Y, Z
The products at a particular factory are manufactured in phases. The same equipment is utilized for each phase, but it must be formatted differently to accomplish different tasks. The transition time to convert between a format for one task and another task varies. The times are given in Table 12.13. In the following exercises, use the table and the nearest neighbor method to find an order in which to complete the tasks, which keeps the transition times down and ends with the same set up as it began so that the factory is ready to start the next batch. Assume that there are no restrictions on which tasks can be completed in which order. Hint: The nearest neighbor algorithm may give a different result depending on which vertex is the starting vertex, so, you must check all possibilities.
Task A B C D E F G
A 0 75 130 45 120 70 100
B 75 0 140 65 115 25 60
C 130 140 0 35 55 20 125
D 45 65 35 0 50 30 40
E 120 115 55 50 0 95 145
F 70 25 20 30 95 0 15
G 100 60 125 40 145 15 0
Manufacturing Equipment Transition Times in Minutes
47 .
A, C, D, F, G
48 .
B, D, E, F, G
49 .
A, B, C, D, E, F
50 .
B, C, D, E, F, G
51 .
A, B, C, D, E, F, G
Order a print copy

As an Amazon Associate we earn from qualifying purchases.

Citation/Attribution

This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Attribution information
  • If you are redistributing all or part of this book in a print format, then you must include on every physical page the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
  • If you are redistributing all or part of this book in a digital format, then you must include on every digital page view the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
Citation information

© Dec 21, 2023 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.