Bidirectional Search, in depth: level-synchronous BFS, why growth rate decides the payoff, and MM for heuristic search

Why two small balls beat one big one

The saving comes from the shape of the search frontier. A breadth-first search from s that reaches t at distance d has to cover every node within distance d of s, a ball of radius d. Two searches that meet in the middle each cover a ball of radius d/2. Whether that is a big saving depends entirely on how the size of a ball grows with its radius.

If the ball grows exponentially, as it does in a tree-like state space with branching factor b, then two balls of radius d/2 hold about 2b^d/2 nodes, which is roughly the square root of b^d. If the ball grows polynomially, as on a two-dimensional grid where a ball of radius r holds about 2r² cells, then two balls of radius d/2 hold about d² cells against 2d²: a factor of 2. In D dimensions the factor is about 2^D−1. Road networks, game maps and meshes sit near the polynomial end. Word ladders, puzzle state spaces and social graphs sit near the exponential end.

Prerequisites for searching backward

Before writing any code, check that the problem supports a backward search at all.

• A predecessor function. The backward search needs the in-neighbours of a node. For an undirected graph that is the same as the successors. For a directed graph you need a reverse adjacency list, which doubles memory. For an implicit state space you need inverse operators: for a sliding-tile puzzle every move is reversible, but for a planner whose actions have preconditions, computing predecessors can be much harder than successors.
• One explicit goal state. Backward search starts from a concrete node. If the goal is a predicate such as any checkmate position, there may be millions of goal states and no single place to start. A multi-source backward search from all of them may cost more than it saves.
• A cost model that is the same in both directions. Edge costs must be read from the same edge whichever way it is traversed. With weighted edges, use bidirectional Dijkstra and its stop rule.

Level-synchronous bidirectional BFS

The version below works on unweighted directed graphs. It keeps a parent map for each direction and expands a whole level at a time, always choosing the direction whose current frontier is smaller.

def bidirectional_bfs(succ, pred, s, t):
    """Shortest s-t path in an unweighted directed graph, or None.

    succ(u) yields out-neighbours, pred(u) yields in-neighbours.
    Expands one whole level of the smaller frontier at a time.
    """
    if s == t:
        return [s]
    parent_f, parent_b = {s: None}, {t: None}
    front_f, front_b = [s], [t]
    while front_f and front_b:
        forward = len(front_f) <= len(front_b)
        front, parents, other, step = (
            (front_f, parent_f, parent_b, succ) if forward
            else (front_b, parent_b, parent_f, pred))
        nxt, meet = [], None
        for u in front:                      # never switch direction mid-level
            for v in step(u):
                if v in parents:
                    continue
                parents[v] = u
                nxt.append(v)
                if v in other and meet is None:
                    meet = v
        if meet is not None:
            path, x = [], meet
            while x is not None:             # walk back to s
                path.append(x)
                x = parent_f[x]
            path.reverse()
            x = parent_b[meet]
            while x is not None:             # then forward to t
                path.append(x)
                x = parent_b[x]
            return path
        if forward:
            front_f = nxt
        else:
            front_b = nxt
    return None                              # one side ran dry: no path

Two details carry the correctness. First, the search only changes direction at a level boundary, so each visited map is always a complete ball: every node within forward distance k_f of s, and every node within backward distance k_b of t. If the shortest path had length L at most k_f + k_b, the node on it at position min(k_f, L) would already lie in both balls, so no meeting so far proves L is at least k_f + k_b + 1. Expanding forward level k_f + 1 labels every new node with forward distance k_f + 1, and a meeting node has backward distance at most k_b, so the path through it has length at most k_f + k_b + 1, which is optimal. Finishing the level before returning is not required for correctness, but it keeps the invariant easy to read. Alternating node by node instead breaks it: the balls are then incomplete, and a meeting can be one hop longer than the true shortest path.

Second, alternating by frontier size rather than strictly in turn matters on directed graphs, where one direction can have a far larger branching factor than the other. Always expanding the cheaper side keeps total work close to the better of the two orders.

Testing the stop rule

Stop rules are where bidirectional search code goes wrong, so test against a one-sided oracle on many small random graphs, where odd shapes such as self-loops, parallel edges, unreachable targets and s next to t all occur naturally. The harness generated 3,000 random directed graphs with 2 to 40 nodes and up to four edges per node, compared path lengths with plain BFS, and checked that every returned path starts at s, ends at t and uses real edges. All 3,000 agreed. The same harness, pointed at a variant that alternated direction after every node instead of every level, failed on the fifth graph by returning a path one edge too long, which is exactly the incomplete-ball bug described above.

Measured: growth rate decides the payoff

Counting nodes removed from the frontier, the same code was run on two graphs.

The grid result matches the polynomial-growth prediction: half the area of one ball of radius 200, slightly less because the one-sided search stops part-way through its last level and its ball is clipped by the grid edge. The random graph matches the exponential prediction: with about three new neighbours per node per level, ten levels reach most of the graph, while two searches of five levels each touch a few hundred nodes. Before choosing bidirectional search, measure how fast your search ball grows; the answer decides whether the technique is a constant-factor tweak or a change of complexity class.

Why bidirectional A* disappointed

With a heuristic, the obvious generalisation is to run A* forward with h_F, an estimate of distance to t, and A* backward with h_B, an estimate of distance to s. Pohl proposed this in 1971, and for decades it disappointed: it rarely beat unidirectional A*. The popular explanation was that the two frontiers pass each other without meeting. Kaindl and Kainz showed in 1997 that this is wrong: the frontiers usually meet early, and most of the effort goes into proving that the path already found is optimal, because the stop test needs a lower bound that front-to-end heuristics raise slowly. Front-to-front heuristics, which estimate distance between frontier nodes, fix the guidance but cost a pairwise comparison per expansion.

MM: guaranteed to meet in the middle

MM, from Holte, Felner, Sharon and Sturtevant at AAAI 2016, was the first bidirectional heuristic search guaranteed to meet in the middle: neither search expands a node whose g-value exceeds half the optimal cost C*. It does this with one change to the priority. In each direction a node n has priority pr(n) = max(f(n), 2g(n)), where f = g + h. The 2g term stops a search from wandering past the halfway point however good its heuristic looks. MM expands whichever direction holds the smallest priority C, and it stops when the best path found, U, is at most the largest of four lower bounds on C*: C itself, the minimum f in each open list, and the sum of the two minimum g-values plus ε, the smallest edge cost.

import heapq

class Open:
    """Open list for one direction: current g per node plus lazy heaps on pr, f and g."""
    def __init__(self):
        self.g = {}
        self.hp, self.hf, self.hg = [], [], []
    def push(self, n, g, h):
        self.g[n] = g
        f = g + h
        heapq.heappush(self.hp, (max(f, 2 * g), n, g))
        heapq.heappush(self.hf, (f, n, g))
        heapq.heappush(self.hg, (g, n, g))
    def _top(self, h):                 # drop entries whose g is stale or already closed
        while h and self.g.get(h[0][1]) != h[0][2]:
            heapq.heappop(h)
        return h[0] if h else None
    def minp(self):
        t = self._top(self.hp); return t[0] if t else float("inf")
    def minf(self):
        t = self._top(self.hf); return t[0] if t else float("inf")
    def ming(self):
        t = self._top(self.hg); return t[0] if t else float("inf")
    def pop_p(self):
        t = self._top(self.hp); heapq.heappop(self.hp); del self.g[t[1]]
        return t[1], t[2]

def mm(succ, pred, s, t, h_f, h_b, eps=1):
    """MM: returns the optimal s-t cost. succ/pred yield (neighbour, cost)."""
    of, ob = Open(), Open()
    gf, gb = {s: 0}, {t: 0}
    of.push(s, 0, h_f(s)); ob.push(t, 0, h_b(t))
    U = float("inf")
    while of.g and ob.g:
        C = min(of.minp(), ob.minp())
        if U <= max(C, of.minf(), ob.minf(), of.ming() + ob.ming() + eps):
            return U
        if of.minp() == C:
            o1, o2, g1, g2, step, h = of, ob, gf, gb, succ, h_f
        else:
            o1, o2, g1, g2, step, h = ob, of, gb, gf, pred, h_b
        n, gn = o1.pop_p()
        for c, w in step(n):
            if c in g1 and g1[c] <= gn + w:
                continue                 # not an improvement (open or closed)
            g1[c] = gn + w               # new or improved: (re)open it
            o1.push(c, g1[c], h(c))
            if c in o2.g:
                U = min(U, g1[c] + g2[c])
    return U

The Open class stores the current g of each open node and three heaps with lazy deletion, so the minimum pr, f and g can be read in amortized logarithmic time. Node keys must be orderable, since ties in the heaps compare them. Checked against Dijkstra, this code agreed on 1,500 random weighted digraphs with h = 0 (the variant called MM0, a bidirectional brute-force search) and on 179 queries on a 60 x 60 grid with obstacles using Manhattan distance in both directions. A follow-up algorithm, NBS (Chen, Holte, Zilles and Sturtevant, IJCAI 2017), expands at most about twice as many nodes as an optimal front-to-end bidirectional algorithm would, given consistent heuristics.

Operational guidance

• Memory. Two visited maps replace one, but each is far smaller when growth is exponential. For a directed graph, budget for the reverse adjacency list.
• Implicit state spaces. Encode states compactly and hash them identically in both directions; BFS on implicit graphs covers state design.
• Many queries on one graph. Bidirectional search is a building block, not the end point. Road routers combine it with preprocessing such as contraction hierarchies.
• Heuristics. If a strong consistent heuristic exists and the goal is single, start with A* and try MM only if A* runs out of memory or time.

Failure modes

• Stopping at the first collision on weighted graphs returns a suboptimal path; the weighted case needs the μ test, not first contact.
• Backward search over a goal predicate with many satisfying states explodes; use one-sided search there.
• Directed graphs with a missing reverse index silently search the forward graph backwards and return paths that do not exist; the path-validity check in the test harness catches this.
• Strict alternation on asymmetric graphs can expand the expensive side half of the time.
• Reusing one visited set for both directions merges two different distance labels and breaks path recovery.

Trade-offs

Bidirectional search gives a large saving when the search ball grows exponentially, a small constant saving on low-dimensional graphs, and requires a predecessor function and a single goal. Its stopping logic is subtler than one-sided search, and with heuristics it needs an algorithm such as MM rather than two independent A* runs. For one-off puzzles and fixed-depth problems, meet-in-the-middle enumeration is a close cousin that trades the frontier for two precomputed half-tables.

What to do next

1. Measure how many nodes your one-sided search touches at depths 1, 2, 4 and 8. Exponential growth means bidirectional search is worth implementing; quadratic growth means expect 2x.
2. Confirm you can compute predecessors and that there is a single goal state.
3. Implement the level-synchronous BFS above, expanding the smaller frontier.
4. Build the random-graph oracle test before trusting any stop rule.
5. For weighted graphs, switch to bidirectional Dijkstra; for heuristic search, prototype MM and compare node expansions with A* on your own instances.