The idea behind bidirectional search is to run two simultaneous searches – one forward from the the initial state and the other backward from the goal, stopping when the two searches meet in the middle (figure (12)). The motivation is that $b^{d/2}$ is much less than $b^d$, or in the figure, the area of the two small circles is less than the area of one big circle centered on the start and reaching to the goal.
Bi-directional search is implemented by having one or both of the searches check each node before it is expanded to see if it is in the fringe of the other search tree, if so, a solution has been found.
Example: If a problem has solution depth d = 6, and each direction runs BFS one node at a time, then in the worst case the two searches meet when each has expanded all but one the nodes at depth 3.
figure (2) A schematic view of a bidirectional search that is about to succeed, when a branch from the start node meets a branch from the goal node.
Compared uniformed search strategies.
| Criterion |
BFS |
Uniform cost |
Depth first |
Depth limited |
Iterative Deepening |
Bi-directional |
| Complete |
$Yes^a$ |
$Yes^{a,b}$ |
No |
No |
$Yes^a$ |
$Yes^{a,b}$ |
| Time |
$O(b^{d+1})$ |
$O(b^{c*/6})$ |
$O(b^m)$ |
$O(b^l)$ |
$O(b^d)$ |
$O(b^{d/2})$ |
| Space |
$O(b^{d+1})$ |
$O(b^{c*/ \in})$ |
O(bm) |
b(bl) |
O(bd) |
$O(b^{d/2})$ |
| Optimal |
$Yes^c$ |
Yes |
No |
No |
$Yes^c$ |
$Yes^{c,d} $ |
Figure. Evaluation of search strategies.
b – branching factor.
d – depth of the shallowest solution.
m – maximum depth of the search tree.
l – depth limit.
Super script caveats are as follows:
$a_{complete}$ if b is finite,
$b_{complete}$ if step costs $\geq$ $\in$ for positive $\in$,
$c_{optimal} $ if step costs are all identical,
$d_{if}$ both directions use BFS.
and 5 others joined a min ago.
teamques10
★ 68k
pedsangini276
• 4.8k