Part B Instructions
You will use your knowledge of Hamiltonian circuits and the Brute Force and nearest neighbor algorithms to design a minimum-distance tour of 5 national parks of your choice.
Data- collection: Decide on 5 national parks you would like to visit in a tour. Assume you will visit all 5 parks in one trip, starting and ending at your home. Use the Internet to look up the addresses of the national parks you plan to visit, then use Google ® maps to find the actual driving distances between each location. Make sure you find the driving distance between each pair of parks (including your home).
Model the situation: Once you have collected all of your data, draw a weighted-edge graph representing all possible paths (This should be a complete graph).
Computations: Use each algorithm studied in the chapter on graph theory (i.e., brute force, nearest neighbor, repeated nearest neighbor, and sorted edges algorithm) to find a tour that minimizes the driving distance necessary to visit all 5 parks in one trip.
Conclusions: Decide which algorithm most efficiently produces the optimal minimum-distance tour. Describe the minimum distance tour you found and why the algorithm is most efficient.
Present your solution: You will present your tour in a 3 – 4 page paper, including diagrams and explanations of how you came up with your final solution. The following items must be present in your paper:
a. A Google ® map that contains the 5 parks and your home, with markings to clearly identify each location.
b. Three weighted-edge graphs. One graph showing:
1. Your model of the park visit problem
2. The Hamiltonian circuit created using the nearest-neighbor algorithm
3. The Hamiltonian circuit created using the sorted- edges
c. A key that identifies what each vertex represents in your model.
d. A calculation of the number of possible Hamiltonian circuits that exist in your graph.
e. An explanation of your solution/conclusions to the national park tour describing which algorithm produced the best result.