Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Best-first search program

Posted on 1999-06-23
11
Medium Priority
?
4,206 Views
Last Modified: 2008-03-17
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
Comment
Question by:Neo78
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
11 Comments
 
LVL 2

Expert Comment

by:obg
ID: 1262911
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
 
LVL 84

Expert Comment

by:ozo
ID: 1262912
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
 
LVL 1

Expert Comment

by:Aggarwal
ID: 1262913
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 1

Author Comment

by:Neo78
ID: 1262914
It is used for searching. It uses heuristics.
Similar to depth first and breadth first search.
0
 
LVL 1

Author Comment

by:Neo78
ID: 1262915
Aggarwal

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

Expert Comment

by:Aggarwal
ID: 1262916

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
 
LVL 8

Expert Comment

by:shlomoy
ID: 1262917
Better yet, post the algorithm.
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 1262918
Or both.
0
 
LVL 1

Author Comment

by:Neo78
ID: 1262919
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
0
 

Accepted Solution

by:
Frost_Byte earned 280 total points
ID: 1262920
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
 
LVL 1

Expert Comment

by:Moondancer
ID: 6820323
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

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

670 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question