Bidirectional search
Encyclopedia
Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex
to a goal vertex in a directed graph
. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet in the middle. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree
with branching factor
b, and the distance from start to goal is d, each of the two searches has complexity O(bd/2) (in Big O notation
), and the sum of these two search times is much less than the O(bd) complexity that would result from a single search from the beginning to the goal.
This speedup comes with a price: a bidirectional search algorithm must include additional logic to decide which search tree to extend at each step, increasing the difficulty of implementation. The goal state must be known (rather than having a general goal criterion that may be met by many different states), the algorithm must be able to step backwards from goal to initial state (which may not be possible without extra work), and the algorithm needs an efficient way to find the intersection of the two search trees. Additionally, the branching factor of backwards steps may differ from that for forward steps. The additional complexity of performing a bidirectional search means that the A* search algorithm is often a better choice if we have a reasonable heuristic.
As in A* search, bi-directional search can be guided by a heuristic estimate of the remaining distance to the goal (in the forward tree) or from the start (in the backward tree). An admissible heuristic
will also produce a shortest solution, as was proven originally for A*.
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. Later, he and his student, George Politowski improved this method by choosing D - nodes as natural intermediaries.
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
to a goal vertex in a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet in the middle. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
with branching factor
Branching factor
In computing, tree data structures, and game theory, the branching factor is the number of children at each node. If this value is not uniform, an average branching factor can be calculated....
b, and the distance from start to goal is d, each of the two searches has complexity O(bd/2) (in Big O notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
), and the sum of these two search times is much less than the O(bd) complexity that would result from a single search from the beginning to the goal.
This speedup comes with a price: a bidirectional search algorithm must include additional logic to decide which search tree to extend at each step, increasing the difficulty of implementation. The goal state must be known (rather than having a general goal criterion that may be met by many different states), the algorithm must be able to step backwards from goal to initial state (which may not be possible without extra work), and the algorithm needs an efficient way to find the intersection of the two search trees. Additionally, the branching factor of backwards steps may differ from that for forward steps. The additional complexity of performing a bidirectional search means that the A* search algorithm is often a better choice if we have a reasonable heuristic.
As in A* search, bi-directional search can be guided by a heuristic estimate of the remaining distance to the goal (in the forward tree) or from the start (in the backward tree). An admissible heuristic
Admissible heuristic
In computer science, specifically in algorithms related to Pathfinding, a heuristic function is said to be admissible if it is no more than the lowest-cost path to the goal. In other words, a heuristic is admissible if it never overestimates the cost of reaching the goal...
will also produce a shortest solution, as was proven originally for A*.
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. Later, he and his student, George Politowski improved this method by choosing D - nodes as natural intermediaries.