You are the CEO of a startup company. You have designed some new software and you are planning to have a worldwide demonstration of the product. There are n cities you would like to visit. Starting from San Francisco, you wish to visit all the n cities exactly once, with minimum mileage, and then return to San Francisco. Now, you need to come up with a plan on how to visit the n cities.

More formally, in the traveling-salesperson problem (TSP), a salesperson must visit n cities. Modeling the problem as a complete graph with n vertices, we can say that the salesperson wishes to make a tour visiting each city exactly onc e and finishing at the city he starts from. There is a cost c(i, j) to travel from city i to city j, and the salesperson wishes to make the tour with minimum total cost. The total cost is the sum of the individual costs along the edges of the tour.

This homework is a natural extension of Q6 in homework #3. You may want to take a look at the solution of Q6 before starting this homework.

The TSP is a relatively old problem: it was documented as early as 1759 by Euler, whose interest was in solving the knight’s tour problem: A correct solution would have a knight visit each of the 64 squares of a chess board exactly once on this tour. The term "traveling salesman" was first used in a 1932 German book "The traveling salesman, how and what he should do to get commissions and be successful in this business" (a book about business!). The RAND Corporation introduced the TSP in 1948. RAND’s reputation helped to make the TSP a well-known and popular problem. (excerpt from the class notes of EESOR 213)

We can abstract the TSP as a search problem by specifying:

• State

A state is a list of cities visited so far.

• Initial state

• Operator

• Goal state

• Path cost

The path cost between two cities is the distance between the cities

• Total cost

Fig. 1

In fig.1, the optimal tour will be (SF, LA, Miami, NY, SF) or (SF, NY, Miami, LA, SF).

As mentioned in the solution of HW #3, one possible heuristic function (maybe not the best) can be defined as the distance from the last city in the list to the farthest city that still needs to be visited.

For example, assume you have visited SF and LA. The cities you still need to visit are Miami, NY and SF. Since NY is farthest away from LA, h-hat( (SF, LA) ) = 7.2.

We can implement the A* search by using a priority queue L. Here is the algorithm:

L = list of initial states

While (L is not empty)

{

n = removeFront(L)

if (isGoal(n) == TRUE)

return n

else

S = successor(n)

insert(S, L)

}

Note:

• L is the priority queue, in which the element with the lowest value (f-hat-value in our case) is put in the front.
• removeFront(L) and insert(S, L) are the two operations on the queue

• n is a state
• S, L are lists of states

Here is how we can apply the algorithm to the problem in fig. 1.

Iteration 0:

Initial L: < [(SF) 5] > // g-hat-value = 0, h-hat-value = 5. So the initial f-hat-value of (SF) is 5

Iteration 1:

n = [(SF), 5]

S = < [(SF, NY) 12.2], [(SF, Miami) 11], [(SF, LA) 10.2] >

L = < [(SF, LA) 10.2], [(SF, Miami) 11], [(SF, NY) 12.2] >

Note:

• (SF, NY) is a state for the search problem. [(SF, NY) 12.2] is the data structure we insert into the priority queue.

• [(SF, NY) 12.2], [(SF, Miami) 11], [(SF, LA) 10.2] are the successors of [(SF,) 6].
• The g-hat-value of (SF, NY) is 5. The h-hat-value of (SF, NY) is 7.2, which is the distance between NY and LA. So the f-hat-value for (SF, NY) is 12.2.
• After putting the 3 successors back in L, the one with the lowest value is put in the front.

Iteration 2:

n = [(SF, LA) 10.2]

S = < [(SF, LA, NY), 16.2], [(SF, LA, Miami), 13.2] >

L = < [(SF, Miami) 11], [(SF, NY) 12.2], [(SF, LA, Miami), 13.2], [(SF, LA, NY), 16.2] >

Iteration 3:

n = [(SF, Miami) 11]

S = < [(SF, Miami, NY), 18.2], [(SF, Miami, LA), 16.2] >

L = < [(SF, NY) 12.2], [(SF, LA, Miami), 13.2], [(SF, LA, NY), 16.2], [(SF, Miami, LA), 16.2],

[(SF, Miami, NY), 18.2] >

…

Finally, we will find (SF, LA, Miami, NY, SF) as the goal with cost 18.2.

1. Briefly describe the design of your admissible heuristic function.
2. Using your heuristic function, solve the TSP in Fig. 1. Draw the corresponding search tree.
3. Briefly describe the design of your program. In particular, describe the data structure you used to represent the search tree and the algorithm of the A* search.

Extra credits will be given if you design a heuristic function better than the one suggested. Show qualitatively why your heuristic function is better. Note that your heuristic function should be admissible and can be computed effic iently.

This will be given to the group which finds the optimal tour will the fewest number of node expansions. Basically, a good heuristic function will reduce the number of node expansions.

Write a program that finds the optimal tour of a TSP.

• Input

You will be given 3 input files: in1.dat, in2.dat and in3.dat. Each input file contains a specific scenario of TSP. For example, fig. 1 will be specified by in1.dat. Here is the format of the file:

4

SF 1 5

NY 5 8

Miami 5 2

LA 1 2

The first integer, 4, specifies the number of cities. Then, the first column specifies the names of the cities. The second and the third column specify the X-coordinates and the Y-coordinates of the cities.

• Output

The name of your executable program should be hsearch. You need to write your Makefile so that we can compile your program. Your program should be invoked by:

elaine11:~>hsearch in.1

And you should produce the following output:

Number of nodes expanded: 11

The optimal tour is: (SF, LA, Miami, NY, SF) with cost 18.2

The assignment is due on Feb 16. Part A should be written on papers.

For Part B, you should use the submit script for submission. To submit:

elaine:>/usr/class/cs121/submit2

To resubmit:

elaine:>/usr/class/cs121/submit2 –-replace

Remember to submit your source code, Makefile, and include the members of your group in the README file.

Before you send email to ask questions, please refer to the FAQ. The URL is:

This is the quickest way you get the answers for your questions.