Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

DFS searching in Prolog 2

Status
Not open for further replies.

ridoy

Programmer
May 3, 2013
6
0
0
I am new in Prolog,working with trees such as forming a tree,counting nodes etc.I had done those,face problems when i am trying to apply DFS search to find a node.
Below is my code so far..
Code:
constructTree(tree(1,
            tree(2,
                tree(3,nil,nil),
                tree(4,nil,nil)),
            tree(5,
                tree(6,nil,nil),
                tree(7,nil,nil))
        )
    ).
count_nodes(nil,0).
count_nodes(tree(_,L,R),N):-
    count_nodes(L,CL),
    count_nodes(R,CR),
    N is CL+CR+1.
When i test it it gives output like..
?- constructTree(T),count_nodes(T,N).
T = tree(1, tree(2, tree(3, nil, nil), tree(4, nil, nil)), tree(5, tree(6, nil, nil), tree(7, nil, nil))),
N = 7.(total node number)

So how can i modify it for searching a node in DFS? Suppose,i want to search node 5 and count iteration number needs to find that node,finally N will print that count number.
 
You can try
Code:
search_node(tree(Node, _, _), Node, 0) :- !.


search_node(tree(_, L, R), Node, N) :-
	(   search_node(L, Node, N1); search_node(R, Node, N1)),
	N is N1+1.
 
Thanks for your response.I think your code counts level of a node actually,it not counts iteration number according DFS search.Cosider for node 6, it counts 2 according to your code because it is in level 2.But according to DFS search,it should be 5,isn't it?
 
If I understand what you mean, for 6 it should 10 :
6 is not 1 : step 1
then I search in left tree
6 is not 2 : step 2
I search in left tree
6 is not 3 : step 3
I search in left tree
tree empty : step 4
I search in right tree
tree empty : step 5
.....
According to this scheme I propose :
Code:
:- dynamic node/1.
search_node(Tree,Node, N) :-
	retractall(node(_)),
	assert(node(1)),
	search_node_(Tree,Node),
	retract(node(N)).


search_node_(tree(Node, _, _), Node) :- !.


search_node_(tree(_, L, R), Node) :-
	(   retract(node(N)),
	    N1 is N+1,
	    assert(node(N1)),
	    search_node_(L, Node)
	;   retract(node(N2)),
	    N3 is N2+1,
	    assert(node(N3)),
	    search_node_(R, Node)).
 
I think your approach is right,i can do some modification on it according to my requirement.Thank you very much for sharing it. Give a star for your effort..[smile]
Hope now i will try for BFS search according to your approach.
 
A little bit clarification needed,do you please explain how the work is going and the function of retract(),retractall() and assert()?
 
This sample can be usefull.

Code:
:- dynamic fact/1.

example :-
	test(asserta),
	test(assertz).


test(Pred) :-
	format('~nWith ~w~n~n', [Pred]),

	Call_1 =.. [Pred, fact(1)],
	Call_2 =.. [Pred, fact(2)],
	Call_3 =.. [Pred, fact(3)],

	maplist(call, [Call_1, Call_2, Call_3]),
	list,

	retract(fact(P)),
	format('Retract : value of P : ~w~n~n', [P]),
	list,

	retractall(fact(_)),
	list.

list :-
	listing(fact).
 
Could you edit your above search_node() for BFS search like the way you do it for DFS?
 
It's easyer than bfs :

Code:
bfs_search_node(Tree,Node, N) :-
	bfs_search_node_([Tree],Node, 1, N).

bfs_search_node_([tree(Node, _, _) | _T], Node, FN, FN) :- !.

bfs_search_node_([tree(_, L, R) | T], Node, CN, FN) :-
	CN1 is CN + 1,
	append(T, [L, R], T1),
	bfs_search_node_(T1, Node, CN1, FN).
 
I can't edit my posts so, I give you another way to count nodes in DFS without assert/retract :

Code:
dfs_search_node(Tree,Node, N) :-
	dfs_search_node_(Tree,Node, 1, _, N).


dfs_search_node_(tree(Node, _, _), Node, FN, _, FN) :- !.

dfs_search_node_(tree(_, L, R), Node, CN, _TN, FN) :-
	CN1 is CN + 1,
	dfs_search_node_(L, Node, CN1, TN1, FN),
	(   CN1 \== FN
	->  dfs_search_node_(R, Node, TN1, _TN, FN)
	;   true).

dfs_search_node_(nil, _Node, CN, TN, _FN) :-
	TN is CN + 1.
 
Thanks for your effort.It was so helpful for me.Do you refer any link or tutorial about how to make a chess game in Prolog where the game should be played between me and computer implementing AI?
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top