CODEWITHSUNDEEP
prolog
AndreaNobili
AndreaNobili

Reputation: 43027

Is it correct this interpretation of DFS algorithm version that avoids loops in Prolog?

I am studying DFS algorithm the DFS algorithm version that avoids loops, this is the code 

/* It is TRUE that Solution is the path from the start node Node to a goal state node
   if it is TRUE the depthfirst2/3 predicate where:
   []: it is the of nodes that was already visited (at the beginning is empty)
   Node: is the current node that I am visiting
   Solution: is the path (without cycles) from the start node to the current node Node 
*/
solve2(Node, Solution) :- depthfirst2([], Node, Solution).

/* BASE CASE: [Node|Path] is the Solution path fro the start node to a GOAL node if it
              is TRUE that Path is the list of visited node until reach Node and Node
              is a GOAL state
*/
depthfirst2(Path, Node, [Node|Path]) :- goal(Node).


/* RULE: Else (if Node this is not a GOAL state) and Path is the list of visited node and
         Sol is the path from the start node to the current node Node it is TRUE if it is
         True that:
         Node1 is the successor of Node
         I have not already visited Node1 (Node1 is not in the visited node list)
         Add Node to the list of visited node and execute depthfirst2 searching the path
         to Node1
*/
depthfirst2(Path, Node, Sol) :- s(Node, Node1),             
                            not(member(Node1, Path)),       
                            depthfirst2([Node|Path], Node1, Sol).

Is my interpretation correct?

Tnx

Upvotes: 0

Views: 153

Answers (1)

CapelliC
CapelliC

Reputation: 60034

Your reading seems ok, except the path is reversed. Using a 3 arguments predicate is usually meant to reverse the path on goal reaching.

To enforce the Else part, I think you need a cut after goal(Node) succeeds. Otherwise, you are extending the path - possibly - after the target Node. If this is unique, there is little utility in doing, because it will be ruled out by subsequent \+ member test.

For efficiency, call \+ memberchk instead of \+ member, as memberchk doesn't leave choicepoints and (in SWI-Prolog) is implemented efficiently at lower level than member.

with this base data:

s(a, b).
s(b, c).
s(c, d).
s(a, d).
goal(d).

you can see the difference of the cut after goal(Node):

without

?- solve2(a, P).
P = [d, c, b, a] ;
P = [d, a] ;
false.

with cut

?- solve2(a, P).
P = [d, c, b, a] ;
P = [d, a].

Upvotes: 2

Related Questions