Finding a path in Prolog

Question

I'm trying to teach myself Prologue. Below I wrote code that, I think, should return all the paths between nodes in an undirected graph ... but that is not the case. I am trying to understand why this particular code is not working (which, I think, distinguishes this question from similar Prolog error messages). I run this in SWI-Prolog. Any clues?

% Define a directed graph (nodes may or may not be "room"s; edges are encoded by "leads_to" predicates). room(kitchen). room(living_room). room(den). room(stairs). room(hall). room(bathroom). room(bedroom1). room(bedroom2). room(bedroom3). room(studio). leads_to(kitchen, living_room). leads_to(living_room, stairs). leads_to(living_room, den). leads_to(stairs, hall). leads_to(hall, bedroom1). leads_to(hall, bedroom2). leads_to(hall, bedroom3). leads_to(hall, studio). leads_to(living_room, outside). % Note "outside" is the only node that is not a "room" leads_to(kitchen, outside). % Define the indirection of the graph. This is what we'll work with. neighbor(A,B) :- leads_to(A, B). neighbor(A,B) :- leads_to(B, A). 

Iff A → B → C → D is a path without a loop, then

 path(A, D, [B, C]) 

must be true. Ie, the third argument contains intermediate nodes.

 % Base Rule (R0) path(X,Y,[]) :- neighbor(X,Y). % Inductive Rule (R1) path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), not(member(Z, P)), path(Z,Y,P). 

Nonetheless,

 ?- path(bedroom1, stairs, P). 

is false. What for? Shouldn't we match R1 with

 X = bedroom1 Y = stairs Z = hall P = [] 

So,

 ?- neighbor(bedroom1, hall). true. ?- not(member(hall, [])). true. ?- path(hall, stairs, []). true . 

?

In fact, if I rate

 ?- path(A, B, P). 

I only get length-1 solutions.

Answer 1

Welcome to Prolog! The problem, in fact, is that when you get to not(member(Z, P)) in R1, P is still a pure variable because the evaluation has not yet reached path(Z, Y, P) . to identify her. One of the amazing but inspiring things about Prolog is that member(Ground, Var) will generate lists containing Ground and combine them with Var :

 ?- member(a, X). X = [a|_G890] ; X = [_G889, a|_G893] ; X = [_G889, _G892, a|_G896] . 

This has a confusing side effect that checking the value in an uncharted list will always succeed, therefore not(member(Z, P)) will always fail, as a result of which R1 will always fail. The fact that you get all the R0 solutions and none of the R1 solutions is the key to something in R1 makes him always fail. In the end, we know that R0 works.

If you change these two goals, you will get the first result that you want:

 path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), path(Z,Y,P), not(member(Z, P)). ?- path(bedroom1, stairs, P). P = [hall] 

If you ask for another solution, you will get a stack overflow. This is due to the fact that after the change, we are happy to generate solutions with cycles as quickly as possible using path(Z,Y,P) , only to cancel them after the fact using not(member(Z, P)) . (By the way, for a slight increase in efficiency, we can switch to memberchk/2 instead of member/2 Of course, doing something not so fast does not help much. :)

I would be inclined to convert this to a breadth-first search, which in Prolog would mean adding an “open set” argument to contain solutions that you have not tried yet, and each node first tries to do an open set, and then adding that node features until the end of the open set. When the open set is extinguished, you tried every node that you could access. For some path finding problems, this is a better solution than deep search anyway. Another thing you could try is to split the path into the visited and future component and only check the visited component. Until you create a loop in the current step, you can be sure that you are not generating it at all, there is no need to worry about future steps.

The way you have formulated the question makes me believe that you do not want a complete solution, just a hint, so I think that is all you need. Let me know if this is not the case.