Solve the problem.An amusement park safety inspector plans to leave his home in Cincinnati, Ohio to inspect roller coasters at parks in the following cities: Williamsburg, Virginia; Atlanta, Georgia; Cleveland, Ohio; and Myrtle Beach, South Carolina. The costs of one-way flights between these locations are listed below:a) Represent this traveling salesman problem with a complete graph showing the costs on the appropriate edges.b) Use the Nearest Neighbor method to approximate the optimal route for the inspector to travel to each city and return to Cincinnati. Give the cost of the route found.c) Randomly select another route from Cincinnati to the other cities and compute the cost of

Question

this route. Compare this cost to the cost found in part (b).

What will be an ideal response?

Answer 1

a) 
 
b) Cincinnati ? Cleveland ? Atlanta ? Myrtle Beach ? Williamsburg ? Cincinnati : $755
c) Answers will vary. One possibility is:
Cincinnati ? Atlanta ? Williamsburg ? Myrtle Beach ? Cleveland ? Cincinnati : $1152. This is $397 more than the route in part (b).