**Practice 3: TSP Heuristics**

Prepared by:

Joseph Malkevitch

Department of Mathematics and Computer Studies

York College (CUNY)

Jamaica, New York 11451

email:

__malkevitch@york.cuny.edu__

web page:

__http://york.cuny.edu/~malk/__

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?

2. How many TSP tours would have to be checked if "brute force" were used to determine the exact solution to the TSP which involved 6 sites? 10 sites?