prolog - Error 1, Backtrack Stack Full

问题:

im trying to write a program in prolog that determine if there is a way from place to place. these are the relations:

road(ny,florida).
road(washington,florida).
road(washington,texas).
road(vegas,california).

I want to write: there_is_way(X,Y) that determine if there is a way or not. for example:

?- road(florida,ny).
no
?-there_is_way(florida,ny).
yes

This is my code:

there_is_way(X,Y):- road(X,Y);
                        road(Y,X);
                        road(X,Z),road(Z,Y),X\=Y;
                        road(X,Z),road(Y,Z),X\=Y;
                        road(Z,X),road(Z,Y),X\=Y;
                        road(Z,X),road(Y,Z),X\=Y.
there_is_way(X,Y):-
                        road(Z,Y),there_is_way(X,Z).
there_is_way(X,Y):-
                        road(Y,Z),there_is_way(X,Z).

but unfortunately I get "Error 1, Backtrack Stack Full".

someone?

thank you

回答1:

First, we need a symmetric definition:

:- meta_predicate symm(2, ?,  ?).

symm(P_2, A, B) :-
   call(P_2, A, B).
symm(P_2, A, B) :-
   call(P_2, B, A).

Now, using closure0/3

there_is_way(A, B) :-
   closure0(symm(road), A, B).

回答2:

If you are treating the road/2 as a directed edge, then you can simply have:

road(ny,florida).
road(washington,florida).
road(washington,texas).
road(vegas,california).

there_is_way(X,Y):- road(X,Y).
there_is_way(X,Y):- road(X,Z),there_is_way(Z,Y).

If however you have a loop in your graph, either because of the directions or you assume that road/2 is an undirected edge (and correspondingly implement this) then you need to keep track of where you have been while route finding. Otherwise you will get into an infinite loop. Remember prolog searches depth first by default so you need to make a check that when adding an item to a route it is not already there, otherwise prolog will find the same route over and over..

See chapter 5 of this book: https://www.cs.bris.ac.uk/~flach/SL/SL.pdf for a complete discussion.