Practice 3: TSP Heuristics
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York 11451
1. i. Use A. Nearest neighbor B. Sorted edges in attempting to get a relatively good or optimal solution to the TSP problems below. ii. Are any of the solutions you get optimal? Use Home = 0 as the start of your tour. (List the tour you get and the cost of the tour.)
Since nearest neighbor can be computed so easily, try finding the nearest neighbor tour from each of the vertices of the graph in turn. Do you get the same tour each time? What idea does this suggest about finding a method which might find a near optimal tour for a TSP quickly?