B* search algorithm

From Wikipedia, the free encyclopedia

Graph search algorithms
Search A* B* Bellman-Ford algorithm Best-first search Bidirectional search Breadth-first search Depth-first search Depth-limited search Dijkstra's algorithm Floyd-Warshall algorithm Hill climbing Iterative deepening depth-first search Johnson's algorithm Uniform-cost search

In computer science, B* (pronounced "B star") is a best-first, graph search algorithm that finds the least-cost path from a given initial node to one goal node (out of one or more possible goals). First published by Hans Berliner in 1979, it is related to the A* search algorithm. It stores intervals for nodes of the tree as opposed to single point-valued estimates. Then, leaf nodes of the tree can be searched until one of the top level nodes has an interval which is clearly "best."

[edit] References

• Berliner, Hans (1979). "The B* Tree Search Algorithm. A Best-First Proof Procedure.". Artificial Intelligence (journal) 12 (1): pp. 23–40. doi:10.1016/0004-3702(79)90003-1. 
• Russell, S. J.; Norvig, P. (2003). Artificial Intelligence: A Modern Approach, pp. 188. ISBN 0-13-790395-2. 
• page on Berliner's paper provided by the Defense Technical Information Center