13.3 Hamilton Paths and Hamilton Circuits 871 Now we introduce a method for determining an approximate solution to a traveling salesman problem. Approximate solutions can be used in cases where determining the optimal solution is not reasonable. One method for determining an approximate solution is the nearest neighbor method . In this method, the salesperson begins at a given location. If the salesperson wishes to minimize the distance traveled, the salesperson first visits the city (or location) closest to his or her starting location. Then the salesperson visits the next city (or location) closest to his or her present location that has not already been visited. This process continues until all the cities (or locations) are visited. Thus, the salesperson moves to the nearest neighbor . Sometimes the salesperson wishes to minimize the cost of travel, such as airfare. In this case, from the starting location the salesperson first visits the city (or location) in which the cost of travel is a minimum. Then from the present location, the salesperson visits the city (or location) where the cost of travel is a minimum. This process continues until all the cities (or locations) are visited. Approximate solutions will always be Hamilton circuits. NEAREST NEIGHBOR METHOD OF DETERMINING AN APPROXIMATE SOLUTION TO A TRAVELING SALESMAN PROBLEM To approximate the optimal solution: 1. Represent the problem with a complete, weighted graph. 2. Identify the starting vertex. 3. Of all the edges attached to the starting vertex, choose the edge that has the smallest weight. This edge is generally either the shortest distance or the lowest cost. Travel along this edge to the second vertex. 4. At the second vertex, choose the edge that has the smallest weight that does not lead to a vertex already visited. Travel along this edge to the third vertex. 5. Continue this process, each time moving along the edge with the smallest weight until all vertices are visited. 6. Travel back to the original vertex. PROCEDURE Did You Know? Six Degrees of Kevin Bacon m Tom Hanks The Six Degrees of Kevin Bacon is a trivia game started by Albright College students Craig Fass, Brian Turtle, and Mike Ginelli. The object is to link any actor to the actor Kevin Bacon through associations from different films. A Bacon number is the number of movies it takes to link an actor to Kevin Bacon. For example, Tom Hanks has a Bacon number of 1, since he was in Apollo 13 (1995) with Kevin Bacon. Halle Berry has a Bacon number of 2, since she was in New Year’s Eve (2011) with Sarah Jessica Parker and Sarah Jessica Parker was in Footloose (1984) with Kevin Bacon. What does this game have to do with graph theory? A graph with actors as vertices and common movies as edges could be used to represent these associations. Such a graph would be very large and difficult to draw. However, computerized versions of the game can manage the associations quite nicely. The website OracleOfBacon.org makes use of a 500-MB database that contains the casts of more than 500,000 movies to compute the Bacon number of more than 390,000 actors, ranging in Bacon number 0 (Bacon himself) to 10 (three individuals). Other online databases provide links among musicians (Six Degrees of Vince Gill), baseball players (The Oracle of Baseball), and mathematicians (Erdös Numbers). Example 6 Using the Nearest Neighbor Method In Example 4, we discussed the American Idol cast’s plan to visit five cities in which auditions would take place and then return to Hollywood. Use the nearest neighbor method to determine an approximate solution for the cast’s visits. The one-way per person flight prices between cities are given in Table 13.3. Table 13.3 Birmingham East Rutherford Hollywood Memphis San Antonio Seattle Birmingham ( B) * $258 $114 $324 $274 $155 East Rutherford (ER) $258 * $134 $104 $355 $154 Hollywood (H) $114 $134 * $144 $129 $108 Memphis (M) $324 $104 $144 * $634 $299 San Antonio (SA) $274 $355 $129 $634 * $119 Seattle (S) $155 $154 $108 $299 $119 * Image Press Agency/NurPhoto/Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=