Link to home
Start Free TrialLog in
Avatar of Neo78
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
Avatar of obg
obg

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.
Avatar of ozo
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?
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 !!
Avatar of Neo78

ASKER

It is used for searching. It uses heuristics.
Similar to depth first and breadth first search.
Avatar of Neo78

ASKER

Aggarwal

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.
Avatar of Neo78

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
ASKER CERTIFIED SOLUTION
Avatar of Frost_Byte
Frost_Byte
Flag of Israel image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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