Travelling salesmen problem
Travelling salesmen problem
The well-known "Travelling Salesman Problem" is defined as follows. An instance of the problem consists of a collection of sites, together with numerical values indicating distances between pairs of sites. Given an instance, the question is: in what order should one visit all sites so as to minimize the total distance travelled? Note that we want to return to the starting point of the tour, so there is no issue regarding which site we should start from. Each site is to be visited exactly once, and the distance travelled between two consective sites on the tour is always the given distance between that pair of sites. If no distance is given, that means that the tour is not allowed to have those two sites consecutively. This assignment asks you to implement a test for whether there exists a tour whose length is less than some amount provided by a user, as described below.
You can assume that the information on an instance of the problem is made available to a program using two predicates "sitelist" and "roadlist". A query or subgoal such as "sitelist(X)" will give X a value consisting of a list of atoms, which represent the sites in the problem instance. "roadlist(X)" will give X a value consisting of a list of terms, each of the form "road(A,B,C)" where A and B are sites and C is a number indicating the length of the road. This can be done by including, for example, the following two clauses in the program.
sitelist( [s1,s2,s3,s4,s5] ).
The above code identifies the problem instance as having five sites, s1,s2,s3,s4,s5, with for example a road of length 8 connecting s2 and s3. The existence of a term "road(X,Y,Z)" means that there exists a road of length Z between X and Y, and the distance Z applies in either direction, so that if X follows Y, or Y follows X in the tour, then Z is the contribution to the total distance.
The task for this assignment is to implement a predicate "tour" with one argument, that should be satisfied if there exists a tour whose total length is less that the (numerical) value of that argument. Given a query in which "tour" is provided with a number as its argument, the program should output a permutation of the list of sites that corresponds to a tour that satisfies the query.
In the example above, the query
could give the response
(The length of the above tour, including the return from s5 to s1, is 26, which is of course less than 30.) The query "tour(50)." would be allowed to output either the above sequence, or alternately the sequence [s1,s2,s3,s4,s5]. Or indeed either sequence in reverse order would be valid. Only one satisfying sequence need be output however. Finally, the predicate does not need to be able to answer queries like "tour(N)" in which the argument is a variable; it only needs to test whether a given number is greater than the length of the shortest tour.