F A E B D C
1. Does this graph have a Hamilton circuit? If so, find one. If not, carefully explain why not.
Yes it does. Several – one of which is AFBCDEA.
2. “The nearest neighbor is an approximate and efficient algorithm.” Explain in a complete English sentence what this means.
The nearest neighbor algorithm is approximate, in the sense that it does not always find the route with the least possible weight, although it is efficient – so even as the number of vertices (or locations) grows, the time required to implement this algorithm does not grow disproportionately large.
You need to start in DC, visit 5 other cities, and then return back to DC. The cost of travel between each pair of cities is shown on the graph below. In each of the following questions determine the route that you would take (you do not need to find the cost of the trip – only the route)
Boston 85 New York 140 120 185 500 220
100 280 300 Chicago 150 DC 310 270 290
275 Miami 410 San Fran
Boston 85 New York
185 500 220 100
Chicago 150 DC
Miami 410 San Fran
you should indicate the order in which you select the edges.
3. If you use the nearest neighbor algorithm, starting in DC,
what route will you take?
The nearest neighbor to DC is NY. From NY the nearest
(unvisited) neighbor is Boston. Then Chicago, San Fran,
Miami and finally back to DC.
4. If you use the cheapest link algorithm, what route will you take?
Don’t forget that your travels must begin and end in DC.
The cheapest link is Boston-NY, followed by NY-DC, so we need to be sure to include these edges. We don’t then need NY-Chi (we don’t need a 3rd flight into or out of NY) or Bos-DC (it would close a circuit), but can use DC-Chi. Continuing in this way, we then pick Chi-SF, Boston-Miami, and finally Miami-SF.
So our route is DC-NY-Boston-Miami-SF-Chicago-DC (or the same in reverse order)