Route goes infinite loop prolog

Question

Just begin for prolog and have a practice for route question

train(a,b).
train(b,a).
train(b,c).
train(c,b).

route(X,Y,[]) :-
      train(X,Y)
   ;  train(Y,X).
route(X,Y,[H|T]) :-
   route(X,H,[]),
   route(H,Y,T).

by doing this route/3 The first rule give two direct connected places an empty set states that there is a route. Second rule states the case where there are intermediate places to reach from one to another. but when I query this and I got a loop route.

Someone said to have a helper predicate visited_route/4 to keep track of the places already visited, but don't know how this way works. Hints or example would be help.

Marandil Marandil · Accepted Answer · 2015-02-23T17:29:47

The problem with your current solution is that the Prolog solver generates infinite tracks like [a,b,a,b,a,b,a...] never reaching the end.

You may want to do, is to exclude cases, where X, Y, or H is a member of T (this may be the visited_route/4 predicate). This way, you won't ever pass the same node twice.

Edit

I've sat down and freshened my Prolog knowledge a little bit, creating such code, which seems to work:

train(a,b).
%train(b,a). Your predicate is symmetric, you don't need to specify both directions
train(b,c).
%train(c,b).
train(c,d).
train(c,e).
train(d,f).
train(e,f).

visited_route(X, Y, [], V) :-
    ( train(X,Y) ; train(Y,X) ),
    not(member(Y, V)).

visited_route(X, Y, [H | T], V) :-
    visited_route(X, H, [], [X | V]),
    visited_route(H, Y, T, [X | V]).

route(X,Y,R) :-
    visited_route(X, Y, R, []).

Visited route has an additional list containing all nodes visited on a way from X to Y (not counting Y). When solver finds a way leading from X to Y in first visited_route predicate, it then checks if the route doesn't go through already visited node, and discards the candidate if so.

Route goes infinite loop prolog

1 Answers