The traveling salesman problem
The problem is that in what order should the salesman visit all the sites so they minimize the total distance traveled. The salesman has to return to the starting point of the tour, so he could choose any starting point. Each site can only be visited once.
I need to develop a predicate tsp(N) to test if a tour whose length is less than the argument given by user.
The query or subgoal such as “vertices(X)” will give X a value consisting of a list of atoms, which represent the sites in the problem instance. “edges(X)” will give X a value consisting of a list of terms, each of the form “path(A,B,C)” where A and B are the sites and C is the length of the path connecting A to B. The distance C applies in either direction A to B or B to A.
Here are the two clauses of the problem.
vertices( [v1,v2,v3,v4,v5]).
edges([ path(v1,v2,5),
path(v2,v3,3),
path(v3,v4,2),
path(v4,v5,5),
path(v5,v1,3),
path(v1,v3,4),
path(v2,v4,5) ] ).
I need to develop a predicate ‘tsp’ with one argument, that should be satisfied if there exits a tour whose length is less that the (numerical) value of that argument. I only need to test whether a given number is greater than the length of the shortest tour.
The predicate “tsp(N)” will have a subgoal like vertices(X) that will give X the site list, followed by some other variable say, y is a permutation of X. Then we can test for whether the tour associated with Y has a cost at most N.
For example
| ?- tsp(20).
The response could be
[v1,v2,v3,v4,v5]
yes
| ?-
