Is this the same as front-to-front search?

No. Front-to-front methods use estimates between states on opposing search frontiers, rather than only to fixed endpoints.

Must the graph be undirected?

No, but predecessor generation, costs and heuristic direction must be handled correctly.

Does the phrase identify one named algorithm?

No. It describes a family of heuristic information and search approaches, including algorithms with different theoretical and practical properties.

AI Glossary / Graphs and symbolic AI / Advanced

Front-to-end

Definition

Front-to-end describes a bidirectional heuristic-search approach in which each search estimates distance to its opposite fixed endpoint. The forward search estimates cost to the goal, while the backward search estimates cost from the start to its current state.

What it means

Bidirectional search explores from both the start and the goal. The two searches can meet to produce a complete route, but they still need guidance about which states to examine.

In a front-to-end approach, the heuristic target remains an endpoint rather than the changing opposite frontier. This can make heuristic evaluation relatively straightforward when good start-distance and goal-distance estimates are available.

The term classifies the information used by the heuristic. It does not specify a complete algorithm, dictate equal effort in both directions or guarantee that the searches meet halfway. Different algorithms combine endpoint estimates with different priorities and stopping conditions.

How it works

Let gF(u) be the cost of a discovered path from start to u. A forward endpoint heuristic hF(u) estimates the remaining cost from u to goal. A conventional directional estimate is fF(u) = gF(u) + hF(u).

For backward search at v, gB(v) represents a discovered path cost from v to the goal in the original problem. The backward endpoint heuristic hB(v) estimates the cost from the start to v. Their sum provides the corresponding directional estimate.

In directed graphs, backward search follows predecessor relationships while retaining original forward-edge costs. It must not silently substitute the cost of a reverse journey. When the searches connect, the resulting path supplies an upper bound on the optimum. Proving optimality requires the algorithm's lower-bound stopping test, not merely noticing that a connection exists.

Three practical examples

Route planning: Two searches use distance estimates toward the fixed origin and destination while exploring a road graph.
Puzzle solving: Forward and backward searches use heuristics to their respective target configurations.
Search research: Developers compare algorithms that use only endpoint heuristic information with methods that estimate distances between frontier pairs.

Think of it this way

Think of two survey teams starting at opposite ends of a proposed route. Each has a map estimating distance to the other team's starting point, even as both teams move. The analogy explains fixed targets; a correct graph algorithm also tracks costs, duplicate states and a justified termination condition.

Worked example

Consider the directed graph with edges S→A costing 2, A→G costing 4, S→B costing 4 and B→G costing 3. The two complete routes cost 6 through A and 7 through B.

Suppose the forward search has reached A with gF(A) = 2 and uses hF(A) = 3. Its directional estimate is fF(A) = 5. The estimate is admissible because the true remaining cost from A to G is 4.

Suppose the backward search has reached B from G along the reversed search representation of B→G. Its stored cost is gB(B) = 3, representing the original route B→G. If hB(B) = 3, then fB(B) = 6; that heuristic is also admissible because the true S→B cost is 4.

These estimates point toward fixed endpoints. Neither hF(A) nor hB(B) is an estimate of the distance from A to B. In fact, the displayed graph contains no A→B route at all.

If the searches first connect through B, they discover a path of cost 7. They must not conclude that 7 is optimal while the cost-6 route through A remains possible. This example illustrates the distinction between finding a connection and establishing the best path; it does not prescribe one universal bidirectional stopping formula.

Illustrative case study

Fictional case: Alder Routes prototypes a bidirectional planner for a directed delivery-network simulation. Its first implementation reuses a heuristic designed for travel from the destination to each node as the backward heuristic.

A review identifies the direction mismatch: the required estimate concerns travel from the start to the backward-search node, while the backward path cost represents travel from that node to the destination. One-way links make those quantities different.

The team corrects the definitions and validates returned path costs against a trusted baseline on small graphs. It also adds a case where the first connection is suboptimal. Performance comparisons then measure heuristic cost and search effort under the same graph semantics. The case illustrates implementation checks rather than reporting a production routing result.

Common misconceptions and mistakes

Front-to-end means the searches do not meet. They still connect; the term describes their heuristic targets.
Backward search uses the cost of traveling backward in the real problem. It can traverse reversed search arcs while accounting for original forward costs.
Meeting guarantees optimality. A separate stopping argument is needed.
Two directions automatically halve the work. Heuristic strength, graph structure and coordination overhead determine the result.

Business use

Front-to-end heuristics can be attractive when endpoint estimates are cheap and accurate enough to guide search. They avoid requiring a new pairwise distance estimate for every relationship between two growing frontiers.

For an application, define each directional quantity precisely and verify the assumptions behind optimality claims. Benchmark against a good unidirectional method as well as other bidirectional approaches. Count heuristic evaluations, memory and runtime alongside expanded nodes; an algorithm with a favorable expansion bound may still incur substantial implementation overhead.

Check your understanding

A backward search is at node V. In the original graph, its stored gB value represents a path from V to the goal. What does its front-to-end heuristic estimate?

Answer: The remaining connection from the start to V, in the original direction of the problem.

Related terms

Bidirectional search
Front-to-front
Admissible heuristic
Shortest Paths
consistent heuristic
search frontier
lower bound
shortest path
A* search

Learn next

Add a one-way edge to the worked graph and list the predecessors needed by backward search. Then write each g and h quantity as an explicit start-to-node or node-to-goal path statement before calculating its value.

Sources

Kaindl and colleagues explain endpoint heuristics and directed-cost conventions: https://www.ijcai.org/Proceedings/99-2/Papers/072.pdf

Chen and colleagues analyze a front-to-end algorithm with near-optimal node-expansion properties under stated assumptions: https://arxiv.org/abs/1703.03868

Siag and colleagues compare front-to-end and front-to-front heuristic information: https://ojs.aaai.org/index.php/SOCS/article/view/27296

The directed graph and Alder Routes case are original illustrations; no universal performance advantage is asserted.

Previous: Frisch - Waugh - Lovell theorem Next: Front-to-front