Exercise 4.3

In this exercise, we explore the use of local search methods to solve TSPs of the type defined in Exercise tsp-mst-exercise.

1. Implement and test a hill-climbing method to solve TSPs. Compare the results with optimal solutions obtained from the A* algorithm with the MST heuristic (Exercise tsp-mst-exercise).

2. Repeat part (a) using a genetic algorithm instead of hill climbing. You may want to consult @Larranaga+al:1999 for some suggestions for representations.