Question

Given a graph and a node in it as the starting point, the traveling salesman problem (TSP) is about finding a least cost path that starts and ends at the starting node, and goes through each other node in the graph once and exactly once. The edges of the graph are labeled by a number representing the cost of traveling between the connecting two nodes. Formulate this problem as a search problem by specifying the states, possible initial states, goal test, operators, and operator costs.

Answer 1

Let the 100 states be represented by number 1 to 100.

Let the distance between  2 states i.e i and j be d (i,j)

Variables:-

k (i,j) =1 if the salesman travels from i to j

         = 0 if the salesman doesn’t travels from i to j

Constraints:-

1) Every node should have exactly 1 outgoing (means should lead to next node)

k(i,1) + k(i,2) + k(i,3) +…..k(i,98) + k(i,99) + k(i,100) = 1, for all i

2) Every node should have exactly 1 incoming (means should be next node to some node)

k(1,i) + k(2,i) + k(3,i) +…..k(98,i) + k(99, i) + k(100, i) = 1, for all i

3) k(i,j) should be binary.

Objective:-

Minimum distance travelled = Sum [d(i,j) * k(i,j) ] for i =1 to 100 and j =1 to 100