TSP with Prolog
Thomas Lindgren
Does anyone know how to program the Travelling Salesman Problem with
Prolog?
I think it's quite easy but ican't find an elegant solution...
It depends on what algorithm you are using, of course. In
Reform Prolog, we have two variations as benchmarks: one approximation
algorithm and one based on a genetic algorithm. The size is 500 lines
or less for each algorithm, and the programs look about as expected.
(I.e., straightforward implementations of the algorithms.)
A third solution, which might use Prolog's implicit search in a stronger
way, is to generate all paths and compute the lengths. Then select the
minimal one. You may want to use branch-and-bound in that case:
pass around a global minimum and cut off search when the current path
is longer than the minimum; update the minimum when a better solution
is found.
Peter Szeredi's article 'Exploiting Or-Parallelism in Optimisation
Problems', in JICSLP'92 (pp. 703-716) discusses such an approach, among
other things, in an or-parallel language.
Thomas
--
Thomas Lindgren, Uppsala University "Kkkkttttt."
tho...@csd.uu.se, lind...@sics.se
http://www.csd.uu.se/~thomasl/home.html
Pierre Raufast
Does anyone know how to program the Travelling Salesman Problem with
Prolog?
I think it's quite easy but ican't find an elegant solution...
Thank you.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Pierre RAUFAST 2A Ecole des Mines de NANCY
rauf...@mines.u-nancy.fr
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Matthew Huntbach
: Does anyone know how to program the Travelling Salesman Problem with
: Prolog?
: I think it's quite easy but ican't find an elegant solution...
: A third solution, which might use Prolog's implicit search in a stronger
: way, is to generate all paths and compute the lengths. Then select the
: minimal one. You may want to use branch-and-bound in that case:
: pass around a global minimum and cut off search when the current path
: is longer than the minimum; update the minimum when a better solution
: is found.
: Peter Szeredi's article 'Exploiting Or-Parallelism in Optimisation
: Problems', in JICSLP'92 (pp. 703-716) discusses such an approach, among
: other things, in an or-parallel language.
For comparison, I discuss the approach in an and-parallel language in my
paper "Parallel Branch and Bound Search in Parlog" in International
Journal of Parallel Programming 20, 4 pp.299-314, 1991. I also have a version
which will appear in a paper next year which has local minima to avoid the
bottleneck effect of many processes accessing a single global minimum.
Matthew Huntbach
Steve Gregory
: Thomas Lindgren (tho...@arnold.csd.uu.se) wrote:
: : In article <1994Nov2...@mines.u-nancy.fr> rauf...@mines.u-nancy.fr (Pierre Raufast) writes:
: : Does anyone know how to program the Travelling Salesman Problem with
: : Prolog?
: : pass around a global minimum and cut off search when the current path
: : is longer than the minimum; update the minimum when a better solution
: : is found.
: paper "Parallel Branch and Bound Search in Parlog" in International
: Journal of Parallel Programming 20, 4 pp.299-314, 1991. I also have a version
: which will appear in a paper next year which has local minima to avoid the
: bottleneck effect of many processes accessing a single global minimum.
: Matthew Huntbach
A similar approach to Matthew's was implemented and applied to the
Travelling Salesman Problem; see my paper "Experiments with speculative
parallelism in Parlog" in ILPS93. A TR version of this paper, and a KL1
version of the actual code, can be found at
http://star.cs.bris.ac.uk/Interests/spec.html.
steve gregory
JAY PRAKASH
Mostowski Collapse
Step 1: Use Google, enter "Experiments with speculative parallelism in Parlog"
Step 2: Click on Paper:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.4719