Bidirectional search

Bidirectional search

Bidirectional search is a graph search algorithm that runs two simultaneous searches: one forward from the initial state, and one backward from the goal, and stopping when the two meet in the middle. The reason for this approach is that each of the two searches has complexity O(b^{d/2}) (in Big O notation), and O(b^{d/2}+b^{d/2}) is much less than the running time of one search from the beginning to the goal, which would be O(b^{d}).

This does not come without a price: Aside from the complexity of searching two times in parallel, we have to decide which search tree to extend at each step; we have to be able to travel backwards from goal to initial state - which may not be possible without extra work; and we need an efficient way to find the intersection of the two search trees. This additional complexity means that the A* search algorithm is often a better choice if we have a reasonable heuristic.

Bi-directional search can use a heuristic as well. An admissible heuristic will also produce a shortest solution as was proven originally for the A* search algorithm.

A node to be expanded is selected from the frontier that has the least number of open nodes and which is most promising. Termination happens when such a node resides also in the other frontier. A descendant node's f-value must take into account the g-values of all open nodes at the other frontier. Hence node expansion is more costly than for A*. The collection of nodes to be visited can be smaller as outlined above. Thus one trades in less space for more computation. The 1977 reference showed that the bi-directional algorithm found solutions where A* had run out of space. Shorter paths were also found when non admissible heuristics were used. These tests were done on the 15-puzzle used by Ira Pohl.

Ira Pohl was the first one to design and implement a bi-directional heuristic search algorithm. A descendant node in a frontier was evaluated only regarding the target at the other side. He reported that the two search trees were missing each other and did not meet in the middle of the search space.


*Dennis de Champeaux & Lenie Sint, An Improved Bi-directional Heuristic Search Algorithm, Journal ACM, vol 24, no 2, 1977 May, pp 177-191.

*Dennis de Champeaux, Bi-Directional Heuristic Search Again, Journal ACM, vol 30, no 1, 1983 January, pp 22-32.

*Ira Pohl, Bi-directional Search, in Machine Intelligence, vol. 6, eds. Meltzer and Michie, Edinburgh University Press, 1971, pp. 127-140.

*Stuart Russell and Peter Norvig. "Artificial Intelligence: A Modern Approach", 2nd ed., Prentice Hall, 2002 (§3.4).

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Search algorithm — In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer… …   Wikipedia

  • A* search algorithm — In computer science, A* (pronounced A 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). It uses a distance plus cost heuristic function… …   Wikipedia

  • Depth-first search — Order in which the nodes are visited Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

  • Iterative deepening depth-first search — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • Depth-limited search — Class Search Algorithm Data structure Graph Worst case performance O( | V | + | E | ) …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Retrosynthetic analysis — is a technique for solving problems in the planning of organic syntheses. This is achieved by transforming a target molecule into simpler precursor structures without assumptions regarding starting materials. Each precursor material is examined… …   Wikipedia

  • Bendix G-15 — The Bendix G 15 computer was introduced in 1956 by the Bendix Corporation, Computer Division, Los Angeles, California. It was about 5 by 3 by 3 ft (1.5m by 1m by 1m) and weighed about 950 lb (450 kg). The base system, without peripherals, cost… …   Wikipedia

  • RTBS — Real Time Bidirectional Search Problembereich in der AI …   Acronyms

  • RTBS — Real Time Bidirectional Search Problembereich in der AI …   Acronyms von A bis Z

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”