13.3 Hamilton Paths and Hamilton Circuits 875 b) Use the brute force method to determine the shortest route for Song to accomplish her errands and then return back to her office. O D S L O , , , , or O L S D O , , , , c) What is the minimum distance Song can walk? 925 feet 30. Job Interviews Christina is searching for a new job. She lives in Shreveport, Louisiana, and has interviews in Barrow, Alaska; Tucson, Arizona; and Rochester, New York. The costs of the one-way flights between these four cities are as follows: Shreveport to Barrow costs $855, Shreveport to Tucson costs $803, Shreveport to Rochester costs $113, Barrow to Tucson costs $393, Barrow to Rochester costs $337, and Tucson to Rochester costs $841. a) Represent this traveling salesman problem with a complete, weighted graph showing the prices of the flights on the appropriate edges. * b) Use the brute force method to determine the least expensive route for Christina to travel to each city and return home to Shreveport. S T B R S , , , , or S R B T S , , , , c) What is the minimum cost she can pay? $1646 31. A Family Vacation The Ackermans live in Tunkhannock, Pennsylvania T( ), and are planning their summer vacation. They wish to visit the following national parks: Acadia A( ), Cuyahoga Valley C( ), and Great Smoky Mountains S( ). The approximate distances among these locations are as follows: T to A is 582 miles, T to C is 342 miles, T to S is 663 miles, A to C is 917 miles, A to S is 1188 miles, and C to S is 521 miles. a) Represent this traveling salesman problem with a complete, weighted graph showing the distances along the edges. * b) Use the brute force method to determine the shortest route for the Ackermans to visit each national park and return to their home. T A S C T , , , , or T C S A T , , , , c) What is the minimum distance the Ackermans can travel? 2633 miles 32. Retirement Road Trip To celebrate his retirement, Baron B( ) wishes to ride his motorcycle to visit his friends Woody W( ), Marcellus M( ), and Simeon S( ). The approximate distances between the homes of these friends are as follows: B to W is 940 miles, B to M is 507 miles, B to S is 374 miles, W to M is 799 miles, W to S is 575 miles, and M to S is 332 miles. a) Represent this traveling salesman problem with a complete weighted graph showing the distances along the edges. * b) Use the brute force method to determine the shortest route for Baron to visit his friends and return home. B S W M B , , , , or B M W S B , , , , c) What is the minimum distance that Baron can travel? 2255 miles 33. Package Delivery Laurice works for FedEx and is in her office O( ). She has packages to deliver to the following families: Moller M( ), Ransford R( ), Seifert S( ), and Warren W( ). The approximate distances among these locations are as follows: O to M is 4.8 miles, O to R is 5.6 miles, O to S is 2.3 miles, O to W is 1.7 miles, M to R is 3.1 miles, M to S is 2.4 miles, M to W is 4.3 miles, R to S is 7.2 miles, R to W is 6.4 miles, and S to W is 0.9 miles. a) Represent this traveling salesman problem with a complete, weighted graph showing the distances along the edges. * b) Use the nearest neighbor method to approximate the optimal route for Laurice to deliver the packages and return to her office. Give the distance of the route determined. O W S M R O , , , , , ;13.7miles c) Randomly select another route for Laurice to deliver the packages and return to her office. Compute the distance of this route. Compare this distance with the distance determined in part (b). Answers will vary. 34. Basketball Teams Jasmine lives in Elko, Nevada E( ), and is planning a trip to see the following basketball teams play on their home courts: Utah Jazz J( ), Sacramento Kings K( ), Portland Trailblazers T( ), and Golden State Warriers W( ). The approximate distances among these locations are as follows: E to J is 230 miles, E to K is 420 miles, E to T is 625 miles, E to W is 501 miles, J to K is 650 miles, J to T is 766 miles, J to W is 730 miles, K to T is 577 miles, K to W is 84 miles, and T to W is 631 miles. a) Represent this traveling salesman problem with a complete, weighted graph showing the distances along the edges. * b) Use the nearest neighbor method to approximate the optimal route for Jasmine to visit each location and return to her home. Give the distance of the route determined. E J K W T E , , , , , ; 2220miles c) Randomly select another route for Jasmine to visit the locations and return to her home and compute the distance of this route. Compare this distance with the distance determined in part (b). Answers will vary. *See Instructor Answer Appendix m Great Smoky Mountains Simon Crumpton/Alamy Stock Photo
RkJQdWJsaXNoZXIy NjM5ODQ=