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
Medium Priority
4,206 Views
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
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

LVL 2

Expert Comment

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

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

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

LVL 1

Author Comment

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

LVL 1

Author Comment

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

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

ID: 1262917
Better yet, post the algorithm.
0

LVL 7

Expert Comment

ID: 1262918
Or both.
0

LVL 1

Author Comment

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;
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

Accepted Solution

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

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

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â€¦
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.
###### Suggested Courses
Course of the Month5 days, left to enroll