13.3 Hamilton Paths and Hamilton Circuits 869 Now that we have been introduced to Hamilton circuits, we will apply this knowledge to solving traveling salesman problems. Traveling Salesman Problems In Examples 1 and 4, we saw how complete graphs can represent cities and the process of traveling between these cities. Our goal in a traveling salesman problem is to determine the least expensive or shortest way to visit each city once and return to the starting location. In terms of graph theory, our goal is to determine the Hamilton circuit with the lowest associated cost or distance. The Hamilton circuit with the lowest associated cost (or shortest distance, etc.) is called the optimal solution. In this section, we will discuss two methods, the brute force method and the nearest neighbor method. In both methods, we will use the term complete, weighted graph. A complete, weighted graph is a complete graph with the weights (or numbers) listed on the edges, as illustrated in Fig. 13.41. We now introduce the brute force method. Example 4 American Idol Travel Lionel Richie, Katy Perry, Luke Bryan, and Ryan Seacrest, the cast of the television show American Idol, are in Hollywood H( ). They need to travel to the following cities to judge contestants’ auditions: San Antonio SA ( ), East Rutherford ER ( ), Birmingham B( ), Memphis M( ), and Seattle S( ). In how many different ways can the cast, traveling together, visit each of these cities and return to Hollywood? Solution We can represent this problem with the complete graph in Fig. 13.40. In the graph, the six vertices represent the six locations and the edges represent the one-way flights between these locations. To determine the number of possible routes, we need to determine the number of Hamilton circuits within this graph. We know that there are − = = (6 1)! 5! ⋅ ⋅ ⋅ ⋅ = 5 4 3 2 1 120 different Hamilton circuits within this graph. So the cast has 120 different ways to start in Hollywood, visit each of these five cities, and return to Hollywood. 7 Now try Exercise 23 M B SA ER S H Figure 13.40 M N A O 229 139 103 171 161 110 Figure 13.41 THE BRUTE FORCE METHOD OF SOLVING TRAVELING SALESMAN PROBLEMS To determine the optimal solution: 1. Represent the problem with a complete, weighted graph. 2. List all possible Hamilton circuits for this graph. 3. Determine the cost (or distance) associated with each of these Hamilton circuits. 4. The Hamilton circuit with the lowest cost (or shortest distance) is the optimal solution. PROCEDURE Example 5 Using the Brute Force Method In Example 1, we introduced Priya, the chief operating officer for Hard Rock Cafe International. We now want to use the brute force method to determine the optimal solution for Priya to start at her home in Orlando O( ), visit restaurants in Atlanta A( ), Memphis M( ), and New Orleans N( ), and then return to her home in Orlando. Solution We illustrated two complete, weighted graphs for the example in Fig. 13.35. The graph in Fig. 13.35(a) is repeated in Fig. 13.41. The numbers shown on the graph represent the one-way fares, in dollars, between the two cities. m Luke Bryan, Katy Perry and Lional Richie Kathy Hutchins/Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=