Module 10 Assignment - Problems

G180 Module 10 Assignment

Use the following graph for problems 1 and 2.

1. For the weighted graph given above, use the Brute Force Algorithm to find an optimal Hamilton Circuit stating at vertex D. Make sure to list all of your steps!

1. Using the nearest-neighbor algorithm on the weighted graph above, provide the resulting Hamilton circuit depending on the starting vertex given below.

   1. Using a starting vertex of A.

1. 1. Using a starting vertex of B.

1. Which algorithm will always result in an optimal solution? Why? What are the benefits of the other algorithm?

1. Suppose you are planning a trip around the world. Below is a table of the distances (in miles) between the cities you want to visit. Assume that you will start and end your trip in New York City.

1. Find the nearest-neighbor tour with New York as the starting city.

1. Find the nearest-neighbor tour with Moscow as the starting city.

1. Find the total weight of both tours.