• Status: Solved
• Priority: Medium
• Security: Public
• Views: 4608

# Best-first search program

Does anyone have the program which implements the best first search algorithm to search the nodes of a tree.....
and some nodes are common to others meaning two parents may have the same child....
I'm stuck here too...Thanx
0
Neo78
1 Solution

Commented:
What do you mean by the "best first" algorithm? Is it like you try to find a node in the earliest occurance in the tree (at the highest level)? If that is the case, you should try to make a list of the nodes while building the tree... But I don't know what you are trying to do.
0

Commented:
Best in what metric?
> two parents may have the same child
then it's a directed graph, not a tree.
> I'm stuck here too...
What are you stuck on?
0

Commented:
i dun find any problem .. u have to mark the visited nodes , in case u r having some problems . Post the code u r trying !!
0

Author Commented:
It is used for searching. It uses heuristics.
Similar to depth first and breadth first search.
0

Author Commented:
Aggarwal

I've been trying to do the program based on an algorithm I got. But I'm stuck.
0

Commented:

whatever u r trying is not tree , as ozo correctly said it's dircted graph .thats why u have to mark the visited nodes , to make sure u r not into infinite loop or some other way of avoiding that .

why dun u post ur code here ( dont worry abt the status of the code ) !!!!

dun worry .. we all gonna help u ???

regards ,
aggarwal
0

Commented:
Better yet, post the algorithm.
0

Commented:
Or both.
0

Author Commented:
procedure best-first-search

begin
open:=[Start];
closed:=[];
while open not equal [] do
begin
remove the leftmost state from open, call it X;
if X=goal then return the path from Start to X;
else begin
generate children of X;
for each child of X do
case
the child is not in open or closed:
begin
assign the child a heuristic value;
end;
the child is already in open:
if the child was reached by a
shorter path
then give the state in open the
shorter path
the child is already in closed:
if the child was reached by a
shorter path then
begin
remove the state from closed;
end;
end;
put X on closed;
re-order states in open by heuristic merit
(best leftmost)
end;
return failure
end.

That's the algorithm.....Thanx for helping me out..guys
0

Commented:
As you have seen above there are meny search algs that are called "best-first-search". The topic is very nicelt covered in abook called "Artificial Intelligence A modern Approach" by Russell and Norvig (a must and I _don't_ know the authors :)
Anyway, code for all the examples given in the book as pseodo-code are available on the web in Lisp, C++, Java and Prolog
There should be one (at least) for BestFS at :
http://www.cs.berkeley.edu/~russell/aima.html
Hope this helps
Frost
0

Commented:
This question was awarded, but never cleared due to the JSP-500 errors of that time.  It was "stuck" against userID -1 versus the intended expert whom you awarded.  This corrects that and the expert will now receive these points, all verified.
Moondancer
Moderator @ Experts Exchange
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.