Princeton COS 126, Possible Heuristics for TSP Extra Credit

  • nearest insertion
  • It is just like the greedy insertion heuristic above, except that the next city to insert need not be chosen in the same order as the input.
  • Start with a tour consisting of two cities. Repeat the following: (i) among all cities not in the tour, choose the one that is closest to some city in the tour, (ii) insert it into the tour in the position where it causes the smallest increases in the tour distance.
  • You will have to store all of the unused cities in an appropriate data structure, until they get inserted into the tour.
  • If your code takes a long time, you algorithm probably performs approximately N^3 steps. If you're careful and clever, this can be improved to N^2 steps.

  • farthest insertion heuristic
  • Same as above, but replace "closest" with "farthest" when selecting the next city to insert.
  • This heuristic seems counterintuitive, but typically outperforms nearest insertion. Can you give a plausible explanation?

  • node interchange heuristic
  • Run the original greedy heuristic (or any other heuristic). Then repeat the following: (i) choose a pair of cities, (ii) swap the two cities in if this improves the tour. For example if the heuristic returns 1-5-6-2-3-4-1, you might consider swapping 5 and 3 to get the tour 1-3-6-2-5-4-1.
  • Does this imply that the resulting tour is optimal?
  • Writing a function to swap two nodes in a linked list provides great practice with coding linked lists. Be careful, it can be a little trickier that you might first expect (e.g., make sure your code handles the case when the 2 cities occur consecutively in the original tour).

  • edge exchange heuristic
  • Run the original greedy heuristic (or any other heuristic). Then repeat the following: (i) choose a pair of edges in the tour, say 1-2 and 3-4, (ii) replace them with 1-3 and 2-4 if this improves the tour.
  • This requires some care, as you will have to reverse the orientation of the links in the original tour between nodes 3 and 2 so that your data structure remains a circular linked list.
  • After performing this heuristic, there will be no crossing edges in the tour, although it need not be optimal.