INTELLIGENT WORK FORUMS
FOR ENGINEERING PROFESSIONALS

Log In

Come Join Us!

Are you an
Engineering professional?
Join Eng-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Eng-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Jobs

Travelling salesmen problem

Travelling salesmen problem

(OP)
Hi, i've been trying to crack this problem for ages but have failed miserably.does anyone know the answer?

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] ).

roadlist([ road(s1,s2,5),
           road(s2,s3,8),
           road(s3,s4,5),
           road(s4,s5,6),
           road(s5,s1,8),
           road(s1,s3,3),
           road(s2,s4,1)
         ]).

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

|?- tour(30).

could give the response
[s1,s3,s2,s4,s5]
yes
| ?-

(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.

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Eng-Tips Forums free from inappropriate posts.
The Eng-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Eng-Tips forums is a member-only feature.

Click Here to join Eng-Tips and talk with other members!


Resources


Close Box

Join Eng-Tips® Today!

Join your peers on the Internet's largest technical engineering professional community.
It's easy to join and it's free.

Here's Why Members Love Eng-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close