prolog out of local stack using lists

Question

i have to find route between two states and ive reached here and i am having error as of now regarding out of stack help me

% state 1 is border of state 2
% borders(A , B). 
borders(sasktchewan, alberta).
borders(saskatchewan, manitoba).
borders(saskatchewan, nwt).
borders(alberta, british_columbia).
borders(alberta, saskatchewan).
borders(alberta, nwt).
borders(british_coumbia, yukon).
borders(british_coumbia, nwt).
borders(british_coumbia, alberta).
borders(nwt, saskatchewan).
borders(nwt, alberta).
borders(nwt, british_columbia).
borders(nwt, yukon).
borders(nwt, manitoba).
borders(manitoba, saskatchewan).
borders(manitoba, nwt).

route( A, B, [ go(A,B) ] ) :-   borders( A, B ). 
route( A, B, [ go(A,Z) | ZtoB ] ) :-   borders( A, Z ),   route( Z, B, ZtoB ).

Show an example query that you entered which leads to stack overflow. It is infinitely recursing on `route`. If you do a `trace`, then you can see what arguments are causing this. But in general, it means you are "going around in circles" on the route. One way to fix that is to keep track of where you've been in an additional argument and check if you've been there already (with `member`). Here's a [problem which is a little different](http://stackoverflow.com/questions/28614903/how-to-express-a-transitive-relationship), but the same principle applies. — lurker, Feb 23 '15 at 11:34

Willem Van Onsem · Answer 1 · 2015-02-23T17:31:19.113

The problem is that you don't bookkeep where you've already been. Now say you are looking to go from sasktchewan to manitoba. Prolog will evaluate this as:

(sasktchewan) <--------------
 `--(alberta)                \
     `--(british_columbia)   |
        |--(yukon) fail!     |
        `--(nwt)             |
           `-(sasktchewan)---/

Now since you don't tell prolog you can't going in loops, it will keep appending (sasktchewan) -> (alberta) -> (nwt) to the path and never find the aimed target.

Demo:

?- route(sasktchewan,manitoba,L).
L = [go(sasktchewan, alberta), go(alberta, saskatchewan), go(saskatchewan, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, saskatchewan), go(saskatchewan, manitoba), go(manitoba, nwt), go(nwt, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, saskatchewan), go(saskatchewan, nwt), go(nwt, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, nwt), go(nwt, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, nwt), go(nwt, saskatchewan), go(saskatchewan, manitoba)] ;
L = [go(sasktchewan, alberta), go(alberta, nwt), go(nwt, manitoba), go(manitoba, saskatchewan), go(saskatchewan, manitoba)] ;

What you need to do is use an accumulator that lists all the places where you've already been. Each time you do a member-check from the moment you've already visited that city, you break. Thus:

%We start a route with being in city A
route(A, B, L) :-
    route(A, B,[A], L).

%In case we find a city with a border, don't hesitate and go to the city!
route( A, B,_,[go(A,B)]) :-
    borders(A,B).
%Too bad, now looking for an extra city
route(A,B,Been,[go(A,Z)|ZtoB]) :-
    borders(A,Z), %hahaa, we can access city Z
    \+ member(Z,Been), %hold on! Did we already visit Z. No! we didn't
    route(Z,B,[Z|Been],ZtoB). %Log city Z and look for a root from Z to B

This is not optimal: once a visit to city a failed at one path, it will also fail if you took another path to that city. You can use the non-bactrackable store to maintain a list of cities that you've visited in order to convert it to an O(n²) algorithm. The implementation depends on the dialect.

prolog out of local stack using lists

1 Answers1