Informed Search

Informed search is a class of search algorithms that use problem-specific knowledge — encoded in a heuristic function — to guide exploration toward the goal more efficiently than uninformed search methods. Where Dijkstra's algorithm and breadth-first search explore uniformly, informed search uses an estimate of proximity to the goal to direct attention, transforming exhaustive traversal into targeted exploration. The canonical example is A* search, which combines the completeness of uniform-cost search with the directional efficiency of greedy best-first search.

The Epistemology of Informed Search

The distinction between informed and uninformed search is not merely algorithmic; it is epistemological. An uninformed search algorithm treats the search space as a terrain whose structure is entirely unknown — it must map every path to find the shortest. An informed search algorithm treats the search space as a landscape whose contours are partially known — it uses this partial knowledge to avoid mapping regions that are unlikely to contain the goal. The heuristic is not a speedup; it is a claim about the structure of the world.

This claim need not be correct. It need only be conservatively wrong. An admissible heuristic never overestimates the true cost; it promises that the goal is at least as far as it appears. This is the same logical structure that underlies interval arithmetic, branch-and-bound optimization, and conservative estimation in scientific inference. The informed search algorithm does not require omniscience. It requires only that its ignorance be structured.

From Algorithms to Cognition

The informed search framework generalizes beyond graph algorithms. In game tree search, the heuristic is an evaluation function that estimates position strength. In motion planning for robotics, it is a Euclidean distance through configuration space. In sequence alignment, it is a statistical model of evolutionary divergence. In each case, the structure is identical: a precisely defined goal, a vast space of candidates, and a heuristic that compresses the space by exploiting domain regularities.

This structure is also the structure of bounded rationality. A chess grandmaster does not evaluate all possible continuations; they use pattern recognition as a heuristic, pruning the search tree to manageable size. A foraging animal does not explore its entire territory; it follows gradient cues that function as heuristics. The cognitive heuristics studied by Kahneman and Tversky — availability, representativeness, anchoring — are heuristics of a different kind, operating on probability judgments rather than path costs. But the underlying structure is the same: an intractable problem is rendered tractable by partial knowledge that sacrifices optimality for feasibility.

The Informed Search Family

Informed search algorithms form a continuum defined by how they balance exploitation of the heuristic against exploration of the space.

Greedy best-first search exploits the heuristic maximally: at each step, it expands the node that appears closest to the goal, ignoring the cost already incurred. It is fast but incomplete — the heuristic may lead it into dead ends or local optima.

A* search balances exploitation and exploration: it expands the node that minimizes the sum of cost-so-far and heuristic estimate. With an admissible heuristic, it is both complete and optimal. With an inadmissible heuristic, it degrades gracefully toward greedy behavior.

Best-first search is the general family that includes both: any algorithm that expands nodes based on an evaluation function that estimates desirability. The evaluation function may be the heuristic alone, the cost-so-far alone, or a weighted combination.

The choice between these algorithms is not merely a technical decision. It is a decision about how much to trust the heuristic. Greedy search trusts it completely; A* distrusts it just enough to preserve optimality; uniform-cost search distrusts it entirely. The algorithm reflects an epistemic stance.

The real insight of informed search is not that knowledge speeds up search. It is that the right kind of partial knowledge — structured, conservative, domain-specific — can transform problems that are intractable in principle into problems that are solvable in practice. This is not merely an algorithmic principle. It is an epistemic principle, and it applies as much to scientific discovery, economic planning, and human cognition as it does to pathfinding in graphs. The heuristic is not a shortcut around rationality. It is rationality operating under the constraint that the world is too large to know in full.