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

Semicentennial

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.

Slogan

You sir, have gone above and beyond the call of duty! This is incredible, it is perfect and it actually makes sense! Sorry I'm such a dummy, I'm really new to prolog and while quite a lot of it has come very naturally I've really struggled with this task. Thank you so much so so sooooo much :] – Semicentennial

do not hesitate to post further questions if you struggle again to understand this code, I or others will answer them in comments :) – Slogan

@Slogan I really loved your approach to this problem, but I wanted to know how would you tackle it if instead of having a Start and End point, the Salesman had to pass through a set of cities inside the full scope of cities and return to the place he started. – Linstock

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!

Buoyage

Once a city has been used, it cannot be used again in the same path. So, acyclic. Also what do you mean by pure and impure? – Semicentennial

I added an explanation above. – Buoyage

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.

Hasan