• Data-collection:

    • 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.


    Data Collection



    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.  

    Sorted Edges and Nearest Neighbor Notes

    Sorted Edges Algorithm Tutorial Video

    Nearest Neighbor Algorithm Tutorial Video 


    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. 1 graph showing your model of the college visit problem
      2. 1 graph showing the Hamiltonian circuit created using the nearest-neighbor algorithm.
      3. 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:
      1. Each vertex represents...
      2. Each edge represents...
      3. For my sorted edges/nearest neighbor path, I started at _____________, then traveled __________ miles to ______________, .....
      4. My path using the sorted edges/nearest neighbor algorithm was ________________ miles (or took _______________ hours)
      5. If I were to make this roadtrip, I would choose the _____________ algorithm because _______________.