Neo78
asked on
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
and some nodes are common to others meaning two parents may have the same child....
I'm stuck here too...Thanx
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.
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?
> 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?
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 !!
ASKER
It is used for searching. It uses heuristics.
Similar to depth first and breadth first search.
Similar to depth first and breadth first search.
ASKER
Aggarwal
I've been trying to do the program based on an algorithm I got. But I'm stuck.
I've been trying to do the program based on an algorithm I got. But I'm stuck.
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
Better yet, post the algorithm.
Or both.
ASKER
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;
add the child to open
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;
add the child to open
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
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;
add the child to open
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;
add the child to open
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
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
Moondancer
Moderator @ Experts Exchange