- Decide on 5 schools that you want to visit on your tour. Your schools can be all in San Antonio, the state of Texas, or in the United States.
- Assume that you will visit all 5 schools in one trip and that the starting and ending points of your tour will be your home.
- Use the Internet to look up the addresses of the schools you plan to visit.
- Use Google maps to find the actual driving distances or time between each location.
- Make sure you find the driving distances between each pair of schools.
Once you have collected all of your data, draw a weighted-edge graph representing all possible paths. Name each vertex a different letter. Put the weights from your data collection on your edges. Answer these questions before you prepare your graph.
- What does each vertex represent?
- What does each edge represent?
- How many vertices should your graph contain?
- How many possible paths will your graph contain?
Apply the nearest-neighbor algorithm and the sorted-edges algorithm to find a tour that minimizes the driving distance necessary to visit all 5 schools in one trip.
Decide which algorithm produces the minimum-distance tour. Describe the minimum-distance tour you found for visiting the 5 schools that you chose.
Make a Poster:
The following items must be presented on your poster:
- A Google map that contains the 5 schools and your home, with markings to clearly identify each location. (You may use a highlighter, stickers, colored pencils, etc to mark your points of interest.) Map of United States Map of Texas Map of San Antonio
- Weighted-edge Graphs
- 1 graph showing your model of the college visit problem
- 1 graph showing the Hamiltonian circuit created using the nearest-neighbor algorithm.
- 1 graph showing the Hamiltonian circuit created using the sorted-edges algorithm.
- A key that identifieswhat each vertex represents in your model (For example: I = Incarnate Word)
- A written explanation of your solution/conclusions to the college visit problem describing which algorithm produced the best result. (This MUST be typed). You may use the following sentence stems:
- Each vertex represents...
- Each edge represents...
- For my sorted edges/nearest neighbor path, I started at _____________, then traveled __________ miles to ______________, .....
- My path using the sorted edges/nearest neighbor algorithm was ________________ miles (or took _______________ hours)
- If I were to make this roadtrip, I would choose the _____________ algorithm because _______________.