World Library  
Flag as Inappropriate
Email this Article

Best-first search

Article Id: WHEBN0000148271
Reproduction Date:

Title: Best-first search  
Author: World Heritage Encyclopedia
Language: English
Subject: A* search algorithm, B*, List of algorithms, Heuristic function, D*
Collection: Search Algorithms
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Best-first search

Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule.

Judea Pearl described best-first search as estimating the promise of node n by a "heuristic evaluation function f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain."[1][2]

Some authors have used "best-first search" to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution, so that paths which are judged to be closer to a solution are extended first. This specific type of search is called greedy best-first search[2] or pure heuristic search.[3]

Efficient selection of the current best candidate for extension is typically implemented using a priority queue.

The A* search algorithm is an example of best-first search, as is B*. Best-first algorithms are often used for path finding in combinatorial search. (Note that neither A* nor B* is a greedy best-first search as they incorporate the distance from start in addition to estimated distances to the goal.)

Contents

  • Algorithm 1
  • Greedy BFS 2
  • See also 3
  • References 4
  • External links 5

Algorithm

An algorithm implementing best-first search follows.[4]

OPEN = [initial state]
while OPEN is not empty or until a goal is found
do
 1. Remove the best node from OPEN, call it n.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. Evaluate each successor, add it to OPEN, and record its parent.
done

Note that this version of the algorithm is not complete, i.e. it does not always find a possible path between two nodes, even if there is one. For example, it gets stuck in a loop if it arrives at a dead end, that is a node with the only successor being its parent. It would then go back to its parent, add the dead-end successor to the OPEN list again, and so on.

The following version extends the algorithm to use an additional CLOSED list, containing all nodes that have been evaluated and will not be looked at again. As this will avoid any node being evaluated twice, it is not subject to infinite loops.

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
       a. If it is not in CLOSED and it is not in OPEN: evaluate it, add it to OPEN, and record its parent.
       b. Otherwise, if this new path is better than previous one, change its recorded parent.
          i.  If it is not in OPEN add it to OPEN.
          ii. Otherwise, adjust its priority in OPEN using this new evaluation.
done

Also note that the given pseudo code of both versions just terminates when no path is found. An actual implementation would of course require special handling of this case.

Greedy BFS

Using a greedy algorithm, expand the first successor of the parent. After a successor is generated:[5]

  1. If the successor's heuristic is better than its parent, the successor is set at the front of the queue (with the parent reinserted directly behind it), and the loop restarts.
  2. Else, the successor is inserted into the queue (in a location determined by its heuristic value). The procedure will evaluate the remaining successors (if any) of the parent.

See also

References

  1. ^ Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
  2. ^ a b . pp. 94 and 95 (note 3).
  3. ^
  4. ^ http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html Best First Search
  5. ^ http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search when EHC Fails, Carnegie Mellon

External links

  • Wikibooks: Artificial Intelligence: Best-First Search
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.