I am hoping you could help me with this.
I am trying to learn about Depth First search algorithm in Prolog and I have come across the following code
go(Start, Goal) :-
empty_stack(Empty_been_list),
stack(Start, Empty_been_list, Been_list),
path(Start, Goal, Been_list).
% path implements a depth first search in PROLOG
% Current state = goal, print out been list
path(Goal, Goal, Been_list) :-
reverse_print_stack(Been_list).
path(State, Goal, Been_list) :-
mov(State, Next),
% not(unsafe(Next)),
not(member_stack(Next, Been_list)),
stack(Next, Been_list, New_been_list),
path(Next, Goal, New_been_list), !.
reverse_print_stack(S) :-
empty_stack(S).
reverse_print_stack(S) :-
stack(E, Rest, S),
reverse_print_stack(Rest),
write(E), nl.
I kind of understand what is going on, but I cant for the life of me find or invent some facts that I can use with it.
Please help. Even if its a really simple set of facts, I just need somewhere to start
Thank you in advance
The Following is an example of DFS used in prolog code
% solve( Node, Solution):
% Solution is an acyclic path (in reverse order) between Node and a goal
solve( Node, Solution) :-
depthfirst( [], Node, Solution).
% depthfirst( Path, Node, Solution):
% extending the path [Node | Path] to a goal gives Solution
depthfirst( Path, Node, [Node | Path] ) :-
goal( Node).
depthfirst( Path, Node, Sol) :-
s( Node, Node1),
\+ member( Node1, Path), % Prevent a cycle
depthfirst( [Node | Path], Node1, Sol).
depthfirst2( Node, [Node], _) :-
goal( Node).
depthfirst2( Node, [Node | Sol], Maxdepth) :-
Maxdepth > 0,
s( Node, Node1),
Max1 is Maxdepth - 1,
depthfirst2( Node1, Sol, Max1).
goal(f).
goal(j).
s(a,b).
s(a,c).
s(b,d).
s(b,e).
s(c,f).
s(c,g).
s(d,h).
s(e,i).
s(e,j).
In order to test this code head over to Swish SWI prolog and paste this into terminal.
Then query the code and type on right hand side: solve(a, Sol)
The solution will be: Sol = [j, e, b, a]
You can debug this code by typing: trace, (solve(a, Sol)).
The Following is an example of BFS used in prolog code
Head over to swish and query it using the same steps as before
The solution will be: Sol = [f, c, a]
% solve( Start, Solution):
% Solution is a path (in reverse order) from Start to a goal
solve( Start, Solution) :-
breadthfirst( [ [Start] ], Solution).
% breadthfirst( [ Path1, Path2, ...], Solution):
% Solution is an extension to a goal of one of paths
breadthfirst( [ [Node | Path] | _], [Node | Path]) :-
goal( Node).
breadthfirst( [Path | Paths], Solution) :-
extend( Path, NewPaths),
append( Paths, NewPaths, Paths1),
breadthfirst( Paths1, Solution).
extend( [Node | Path], NewPaths) :-
bagof( [NewNode, Node | Path],
( s( Node, NewNode), \+ member( NewNode, [Node | Path] ) ),
NewPaths),
!.
extend( Path, [] ). % bagof failed: Node has no successor
s(a,b).
s(a,c).
s(b,d).
s(b,e).
s(c,f).
s(c,g).
s(d,h).
s(e,i).
s(e,j).
goal(j).
goal(f).
Hope this helps for understanding DFS and BFS
Use this diagram to help you understand the tree