1

I'm very new at Prolog and I have no idea how to really start on this exercise. Hints and examples would be very appreciated.

We have a garden with a patio. A random amount of trees is planted in the garden and there is exactly one path between each tree and the patio. Additionally some trees are connected with each other through exactly one path. We know the length of each path.

An example of such a garden is given by the following facts:

patio_to_tree(t1,4).
patio_to_tree(t2,4).
patio_to_tree(t3,1).
patio_to_tree(t4,6).
patio_to_tree(t5,12).

tree_to_tree(t1,t2,4).
tree_to_tree(t2,t3,7).
tree_to_tree(t2,t4,2).

The assignment is to write a predicate walk/2 that calculates a list P of the shortest path around the garden so that you only use each path once and visit every tree. A walk always starts and ends on the patio.

Example for the garden described above:

walk(P,L).
P = [t, b1, b2, b4, t, b3, t, b5, t].
L = 42.

The predicate only has to work with two variables, it doesn't need to be able to calculate a path for a given length L for example.

My experience in Prolog is limited to simple list and arithmetic examples so I'm not sure where to start. I figured findall/3 may be useful to get a list of all trees in the garden, as there could be any amount. I'll probably have to recursively go over that list to get additional information about the trees but what should my base case be? The simplest walk is when the garden has no trees so that would simply be P = [t], L = 0. So is that a suitable base case?

I'm assuming the shortest path that meets the requirements is simply visiting each tree that's not connected to another tree and returning to the patio, then visit every tree that is connected to another tree in order. Will I need an accumulator to hold the value of the total length of paths visited so far or is there an easier way to get that?

I noticed this is very similar to a problem called the Travelling salesman problem, except there is a central point to return to but I'm not sure if I'm supposed to solve this in a similar manner.

Thanks in advance for your help.

1 Answer 1

1

This is the classical traveling salesman problem (TSP) with the usual constraint of returning to the start location.

Your intuition about findall is correct. Get the list of trees, call it L. Then use permutation (built-in to SWI-Prolog) and setof to get all permutations of L and check their total path length, i.e. including the cost of starting from and returning to the patio.

This generate-and-test approach is expensive, but much easier to program than the A* algorithm for the TSP or the branch-and-bound one.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.