872 CHAPTER 13 Graph Theory For the sake of comparison, let us look at four other randomly chosen Hamilton circuits from Example 6 and the per person costs associated with them (see Table 13.4). Solution We will use the nearest neighbor method to determine the least expensive per person cost for the cast to complete the trip. We begin by modifying the graph from Example 4 by putting the one-way per person prices into place, making it a weighted graph (see Fig. 13.43). The cast starts in Hollywood and chooses the least expensive flight, which is to Seattle ($108). In Seattle, the cast chooses the least expensive flight to a location they have not already visited, San Antonio ($119). Next, in San Antonio, they choose the least expensive flight to a location they have not already visited, Birmingham ($274). In Birmingham, they choose the least expensive flight to a location they have not already visited, East Rutherford ($258). Once in East Rutherford, the cast has no choice but to fly to the only location not yet visited, Memphis ($104). Since they began in Hollywood, are now in Memphis, and have visited all five audition cities, the cast now returns to Hollywood ($144) to complete their trip. The nearest neighbor method would produce a Hamilton circuit of H S SA B ER M H , , , , , , . The cost per person is + + + + + = $108 $119 $274 $258 $104 $144 $1007. The total cost for all four cast members is × = $1007 4 $4028. 7 108 154 258 104 299 144 324 274 155 114 355 634 134 119 129 M H S ER B SA Figure 13.43 Now try Exercise 33 Nearest Neighbor Method Learning Catalytics Keyword: Angel-SOM-13.3 (See Preface for additional details.) Table 13.4 Randomly Chosen Hamilton Circuit Cost Calculation Per Person Cost H, SA, ER, B, M, S, H + + + + + $129 $355 $258 $324 $299 $108 $1473 H, M, S, B, ER, SA, H + + + + + $144 $299 $155 $258 $355 $129 $1340 H, ER, S, M, SA, B, H + + + + + $134 $154 $299 $634 $274 $114 $1609 H, ER, M, B, S, SA, H + + + + + $134 $104 $324 $155 $119 $129 $ 965 From Table 13.4, we see that the Hamilton circuit H ER M B S SA H , , , , , , results in a per person cost of $965, which is less than the $1007 we obtained in Example 6. Thus, we see that the nearest neighbor method does not always produce the optimal solution. Without using the brute force method, we cannot determine if the Hamilton circuit H ER M B S SA H , , , , , , is the optimal solution. The nearest neighbor method produces an approximation for the optimal solution. Note also that the nearest neighbor method did produce a Hamilton circuit that was less expensive than three of the four randomly chosen Hamilton circuits. Instructor Resources for Section 13.3 in MyLab Math • Objective-Level Videos 13.3 • Animation: Nearest Neighbor Method • PowerPoint Lecture Slides 13.3 • MyLab Exercises and Assignments 13.3
RkJQdWJsaXNoZXIy NjM5ODQ=