Bidirectional search

${\displaystyle b}$

the branching factor of a search tree

${\displaystyle k(n,m)}$

the cost associated with moving from node ${\displaystyle n}$ to node ${\displaystyle m}$

${\displaystyle g(n)}$

the cost from the root to the node ${\displaystyle n}$

${\displaystyle h(n)}$

the heuristic estimate of the distance between the node ${\displaystyle n}$ and the goal

${\displaystyle s}$

the start state

${\displaystyle t}$

the goal state (sometimes ${\displaystyle g}$, not to be confused with the function)

${\displaystyle d}$

the current search direction. By convention, ${\displaystyle d}$ is equal to 1 for the forward direction and 2 for the backward direction (Kwa 1989)

${\displaystyle d'}$

the opposite search direction (i.e. ${\displaystyle d'=3-d}$)

${\displaystyle \mathrm {TREE} _{d}}$

the search tree in direction d. If ${\displaystyle d=1}$, the root is ${\displaystyle s}$, if ${\displaystyle d=2}$, the root is ${\displaystyle t}$

${\displaystyle \mathrm {OPEN} _{d}}$

the leaves of ${\displaystyle \mathrm {TREE} _{d}}$ (sometimes referred to as ${\displaystyle \mathrm {FRINGE} _{d}}$). It is from this set that a node is chosen for expansion. In bidirectional search, these are sometimes called the search 'frontiers' or 'wavefronts', referring to how they appear when a search is represented graphically. In this metaphor, a 'collision' occurs when, during the expansion phase, a node from one wavefront is found to have successors in the opposing wavefront.

${\displaystyle \mathrm {CLOSED} _{d}}$

the non-leaf nodes of ${\displaystyle \mathrm {TREE} _{d}}$. This set contains the nodes already visited by the search

Front-to-Back algorithms calculate the ${\displaystyle h}$ value of a node ${\displaystyle n}$ by using the heuristic estimate between ${\displaystyle n}$ and the root of the opposite search tree, ${\displaystyle s}$ or ${\displaystyle t}$.

Front-to-Back is the most actively researched of the three categories. The current best algorithm (at least in the Fifteen puzzle domain) is the BiMAX-BS*F algorithm, created by Auer and Kaindl (Auer, Kaindl 2004).

Front-to-Front algorithms calculate the h value of a node n by using the heuristic estimate between n and some subset of ${\displaystyle \mathrm {OPEN} _{d'}}$. The canonical example is that of the BHFFA (Bidirectional Heuristic Front-to-Front Algorithm),[2] where the h function is defined as the minimum of all heuristic estimates between the current node and the nodes on the opposing front. Or, formally:

${\displaystyle h_{d}(n)=\min _{i}\left\{H(n,o_{i})|o_{i}\in \mathrm {OPEN} _{d'}\right\}}$

where ${\displaystyle H(n,o)}$ returns an admissible (i.e. not overestimating) heuristic estimate of the distance between nodes n and o.

Front-to-Front suffers from being excessively computationally demanding. Every time a node n is put into the open list, its ${\displaystyle f=g+h}$ value must be calculated. This involves calculating a heuristic estimate from n to every node in the opposing OPEN set, as described above. The OPEN sets increase in size exponentially for all domains with b > 1.