The traveling salesperson problem (TSP)
can be solved with the minimum- spanning-tree (MST) heuristic, which estimates the
cost of completing a tour, given that a partial tour has already been constructed. The MST
cost of a set of cities is the smallest sum of the link costs of any tree that connects all the
1 Model this problem as a search problem, including, how to define the state space,
start states, operators, path cost and goal state. Show that how the MST heuristic can
be derived from a relaxed version of the TSP, and it is admissible.
2 Write a problem generator for instances of the TSP where cities are represented by
random points in the unit square.
3 Find an efficient algorithm for constructing the MST, and use it with the A * graph
search to solve instances of the TSP.
4 Implement an A* search algorithm to solve the problem. How far can you go with the
A* approach, as the problem size (#cities increases) increases, record the time
(measured by the number of nodes explored) and space (measured by the maximum
number of nodes stored in the open list during the program execution) needed for a
certain size of problem.
5 When the problem size increase, A* runs out of memory. So implement the SMA* to
solve the memory limit problem. Put a fixed limit on the number of nodes that you
can store in open list, show that with the same amount of memory available, SMA* is
able to solve larger size of problem while A* cannot solve. What is the solution found
by SMA*, is it optimal?
6 Sometimes you need find a solution within limited amount of time, you need trade off
the computation time with the solution quality. Modify the A* to an anytime A* and
try it with different w values, record the results you get. Show the multiple different
solutions found by the anytime A* as search time increases.
7 Implement a GUI that allows the choices of #cities, memory size (#nodes) and the
algorithm to run, and demonstrate the solution both graphically and numerically.