Informed search

Bidirectional A*

Two A* searches race from both ends and meet in the middle.

Interactive demo coming soon — read the theory below

The idea

Bidirectional A* runs two informed searches at once: one moving forward from the start toward the goal, and one moving backward from the goal toward the start. Each is a normal A* search, guided by a heuristic (a smart guess of remaining distance). The search stops when the two search frontiers touch, and the path is stitched together from both halves. Because each side only has to explore about half the distance, it can be dramatically faster than a single A*.

How it works

Set up TWO searches: a forward search starting at the start node, and a backward search starting at the goal node. Each keeps its own OPEN list (nodes to explore) and CLOSED list (nodes already expanded).
The backward search explores using REVERSED moves, so it walks the graph 'from the goal outward' toward the start. This only makes sense if moves are reversible and the goal is known.
Alternate between the two: expand one node from the forward search, then one node from the backward search (or whichever side currently looks cheaper).
Each side picks its next node the A* way: lowest f = g + h, where g is the cost so far on that side and h is the heuristic estimate to that side's target.
After expanding a node, check if it has already been reached (is on CLOSED) by the OTHER search. If so, the two frontiers have met: you have a candidate path = forward half + backward half.
Don't stop at the very first touch. Keep a running best meeting cost and keep going until no cheaper meeting is possible, because a shorter path may still meet at a different node.
When the termination test confirms no better crossing exists, reconstruct the full path: follow parent pointers from the meeting node back to the start, then forward to the goal, and join them.
Return the stitched path as the solution.

OPEN, CLOSED & the data structures

["Forward search: OPEN_f (priority queue by f = g + h), CLOSED_f (expanded set), and parent pointers to rebuild the path.", "Backward search: OPEN_b, CLOSED_b, and parent pointers (these point 'toward the goal').", "g-scores per side (cheapest known cost to reach each node from that side's origin).", "A heuristic function h (estimate of remaining distance) for each direction.", "best_meeting: the cheapest meeting node found so far and its total cost, used to decide when it is safe to stop."]

Pseudocode

function BidirectionalAStar(start, goal):
    OPEN_f = {start};  OPEN_b = {goal}
    g_f[start] = 0;     g_b[goal] = 0
    CLOSED_f = {};      CLOSED_b = {}
    best = infinity;    meet = none

    while OPEN_f not empty and OPEN_b not empty:
        # top f-value on each side
        if OPEN_f.min_f() + OPEN_b.min_f() >= best:
            break                      # no cheaper crossing possible -> done
        expand cheaper side (say forward):
            n = pop lowest f from OPEN_f;  add n to CLOSED_f
            for each neighbour m of n:
                relax g_f[m]; set parent; push m to OPEN_f
                if m in CLOSED_b and g_f[m] + g_b[m] < best:
                    best = g_f[m] + g_b[m];  meet = m
        # (backward side is symmetric, using reversed moves)
    return reconstruct(meet)           # forward half + reversed backward half

At a glance

Complete?Complete (with caveats): if a path exists it will be found, as long as moves are reversible so the backward search is valid, the goal is explicitly known, and the graph is finite (or costs are well behaved). Break those assumptions and completeness can fail.

Optimal?Optimal only if you use the right stopping rule and consistent, compatible heuristics for both directions. A naive 'stop at first touch' is NOT optimal; you must keep searching until no cheaper meeting is possible. With admissible/consistent heuristics and the proper termination test, it returns a shortest path.

TimeAbout O(b^(d/2)) in the good case, where b is the branching factor and d is the solution depth. Each side explores depth d/2 instead of d, so b^(d/2) + b^(d/2) is far smaller than b^d. Real speedup depends on the heuristic and how well the frontiers align.

SpaceAbout O(b^(d/2)) as well: you store OPEN and CLOSED for both searches. Fewer nodes overall than one-directional A* on hard problems, but you now maintain two frontiers instead of one.

👍 When to use it

The goal state is explicitly known (you can search backward from it).
Moves are reversible, so the backward search can legitimately walk the graph in reverse.
The search space is large and a single A* explores too many nodes (deep or wide problems).
You have a good heuristic and want the meet-in-the-middle speedup, e.g. road-network / map routing.

⚠️ Watch out for

Do NOT stop at the first time the frontiers touch. That first meeting is often not the shortest path; use the proper termination test.
Needs a known goal and reversible moves. Many problems (e.g. one-way state changes, or 'find any goal that satisfies a property') don't qualify.
Getting the two heuristics to cooperate (front-to-back consistency) is subtle; a mismatched pair can break optimality.
Managing two frontiers plus the meeting logic is fiddly to implement correctly, and bugs hide in the stitching and stopping conditions.
If the frontiers keep missing each other (poor heuristics), the promised speedup shrinks.