Simplified Travelling Salesman in Prolog

Question

I've looked through the similar questions but can't find anything that's relevant to my problem. I'm struggling to find an algorithm or set of 'loops' that will find a path from CityA to CityB, using a database of

distance(City1,City2,Distance)

facts. What I've managed to do so far is below, but it always backtracks at write(X), and then completes with the final iteration, which is what I want it to do but only to a certain extent.

For example, I don't want it to print out any city names that are dead ends, or to use the final iteration. I want it to basically make a path from CityA to CityB, writing the name of the cities it goes to on the path.

I hope somebody can help me!

all_possible_paths(CityA, CityB) :-
    write(CityA),
    nl,
    loop_process(CityA, CityB).

loop_process(CityA, CityB) :- 
    CityA == CityB.
loop_process(CityA, CityB) :-
    CityA \== CityB,
    distance(CityA, X, _),
    write(X),
    nl,
    loop_process(X, CityB).

Answer 1

I tried to demonstrate how you can achieve what you're working on so that you can understand better how it works. So since your OP wasn't very complete, I took some liberties ! Here are the facts I'm working with :

road(birmingham,bristol, 9).
road(london,birmingham, 3).
road(london,bristol, 6).
road(london,plymouth, 5).
road(plymouth,london, 5).
road(portsmouth,london, 4).
road(portsmouth,plymouth, 8).

Here is the predicate we will call to find our paths, get_road/4. It basically calls the working predicate, that has two accumulators (one for the points already visited and one for the distance we went through).

get_road(Start, End, Visited, Result) :-
    get_road(Start, End, [Start], 0, Visited, Result).

Here is the working predicate,
get_road/6 : get_road(+Start, +End, +Waypoints, +DistanceAcc, -Visited, -TotalDistance) :
The first clause tells that if there is a road between our first point and our last point, we can end here.

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, End, Distance),
    reverse([End|Waypoints], Visited),
    TotalDistance is DistanceAcc + Distance.

The second clause tells that if there is a road between our first point and an intermediate point, we can take it and then solve get_road(intermediate, end).

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, Waypoint, Distance),
    \+ member(Waypoint, Waypoints),
    NewDistanceAcc is DistanceAcc + Distance,
    get_road(Waypoint, End, [Waypoint|Waypoints], NewDistanceAcc, Visited, TotalDistance).

Usage is as follows :

?- get_road(portsmouth, plymouth, Visited, Distance).

And yields :

Visited = [portsmouth, plymouth],
Distance = 8 ;
Visited = [portsmouth, london, plymouth],
Distance = 9 ;
Visited = [portsmouth, plymouth, london, plymouth],
Distance = 18 ;
false.

I hope it will be helpful to you.

Answer 2

Please separate the pure part from the impure (I/O, like write/1, nl/0 but also (==)/2 and (\==)/2). As long as they are entirely interlaced with your pure code you cannot expect much.

Probably you want a relation between a starting point, an end point and a path in between.

Should that path be acyclic or do you permit cycles?

To ensure that an element X does not occur in a list Xs use the goal maplist(dif(X),Xs). You do not need any further auxiliary predicates to make this a nice relation!

Answer 3

You should return a successful list as an Out variable in all_possible_paths. Then write out that list. Don't do both in the same procedure.