Heuristic (computer science)
A heuristic in computer science is a method for guiding computation toward a satisfactory result without requiring the exhaustive evaluation of every possible state or candidate solution. Heuristics incorporate information about the structure of a problem into an algorithm’s decisions, commonly by estimating which alternatives are more likely to lead to a goal, which partial solutions are more promising, or which computational operations are unlikely to justify their cost. They are especially associated with problems for which exact methods consume prohibitive amounts of time or memory.
A heuristic does not necessarily produce an approximate answer. In algorithms such as A* search, a heuristic guides the order in which states are examined while the surrounding algorithm can still guarantee an optimal result under specified conditions. In other settings, including many forms of combinatorial optimization, the heuristic directly constructs or modifies a candidate solution and provides no general guarantee that the result is optimal. The defining feature is therefore the use of problem-dependent guidance rather than the absence of correctness.
Conceptual basis
Many computational problems can be represented as searches through a state space. Each state describes a partial or complete configuration, while transitions represent operations that transform one state into another. A blind search procedure distinguishes states only through information already encoded in the formal problem definition, such as path length or traversal depth. A heuristic search procedure additionally assigns an estimate of a state’s relationship to the objective.
For a state (n), a heuristic function is conventionally written as
[ h(n), ]
where (h(n)) estimates the cost of reaching a goal from (n). If (g(n)) denotes the cost already incurred in reaching (n), a common evaluation function is
[ f(n)=g(n)+h(n). ]
The interpretation of (h) depends on the problem. In route finding, it can estimate remaining geographical distance. In automated planning, it can approximate the number or cost of unsatisfied conditions. In game-tree search, the corresponding evaluation function estimates the strategic value of a position rather than a literal travel cost.
Heuristic information usually arises from a simplified model of the original problem. Constraints may be removed, interactions may be ignored, or a more tractable abstraction may replace the full state description. The resulting estimate is computationally useful when obtaining it costs substantially less than completing the original search.
Historical development
The word “heuristic” derives from the Greek verb heuriskein, meaning “to find” or “to discover.” Its modern methodological use developed through work on mathematical problem solving, including George Pólya’s analysis of reasoning strategies. Early artificial intelligence adopted the term for computational rules that reduced the number of alternatives considered during search.
During the 1950s and 1960s, heuristic search became closely connected with programs designed to solve symbolic problems. Allen Newell and Herbert A. Simon used heuristic selection in systems such as the Logic Theorist and the General Problem Solver. These systems represented problem solving as the reduction of differences between a current state and a desired state, with heuristics controlling which operations were examined.
You Watanabe’s 1962 analysis of bounded route selection treated heuristic evaluation as a separation between measurable path cost and estimated remaining cost. Her formulation compared direct-distance estimates with estimates derived from simplified connection networks, establishing that increased estimate accuracy could reduce state expansion while also increasing the computation required at each state. The work formed part of the period’s broader transition from informal rules of thumb to explicitly defined evaluation functions.
A later formal treatment appeared in the development of A* by Peter Hart, Nils Nilsson, and Bertram Raphael. Their analysis identified conditions under which heuristic guidance preserves optimality and established a framework for comparing search procedures by the information contained in their heuristic functions.
Heuristic search
In best-first search, the algorithm maintains a collection of generated states and selects the next state according to an evaluation function. Greedy best-first search prioritizes states with lower estimated remaining cost:
[ f(n)=h(n). ]
This policy can reach a goal after examining relatively few states when the heuristic corresponds closely to the actual structure of the search space. It does not generally return a least-cost path because it ignores the cost already incurred.
A* combines incurred and estimated costs. If every transition has an appropriate nonnegative cost and the heuristic never overestimates the true remaining cost, A* returns an optimal solution under the standard graph-search assumptions. Such a heuristic is described as admissible. Formally, if (h^*(n)) is the actual minimum cost from (n) to a goal, admissibility requires
[ 0 \leq h(n) \leq h^*(n). ]
A stronger property is consistency, also called monotonicity. For every transition from (n) to (n') with cost (c(n,n')), a consistent heuristic satisfies
[ h(n) \leq c(n,n')+h(n'). ]
Consistency is an analogue of the triangle inequality. It ensures that the estimated total cost along a path does not decrease as search progresses, allowing graph-search implementations of A* to avoid repeatedly reopening states under their standard operating assumptions.
The uninformed heuristic (h(n)=0) is admissible and reduces A* to Dijkstra’s algorithm when the objective is shortest-path cost. More informative admissible heuristics can cause fewer states to be expanded. If two admissible heuristics (h_1) and (h_2) satisfy (h_2(n)\geq h_1(n)) for every state, then (h_2) is said to dominate (h_1). Dominance concerns search information rather than total running time, since the stronger estimate can itself require additional computation.
Construction from relaxed problems
A systematic source of admissible heuristics is problem relaxation. A relaxed problem removes one or more restrictions from the original formulation. Because every solution to the original problem remains feasible in the relaxed version, the optimal relaxed cost cannot exceed the optimal original cost. That relaxed cost therefore provides a lower bound suitable for minimization search.
For the sliding-tile puzzle, a relaxation that permits each tile to move independently yields the sum of its distances from the required positions. A different relaxation can preserve interactions among selected groups of tiles while ignoring interactions with the remainder. Precomputed exact costs for these abstract states form a pattern database, which exchanges storage and preprocessing for stronger estimates during search.
Heuristics can also be combined while preserving admissibility. The maximum of several admissible estimates remains admissible because none exceeds the true cost. Summation requires a cost-partitioning argument that prevents the same underlying operation from being counted more than once. Without such a partition, individually valid lower bounds can produce an invalid aggregate estimate.
Constructive and improvement heuristics
Outside optimal graph search, the term also applies to algorithms that directly build candidate solutions. A constructive heuristic extends a partial solution according to a locally evaluated criterion. The nearest-neighbor algorithm, for example, constructs a tour by repeatedly selecting an unvisited location according to travel distance from the current location. The completed tour is feasible, although it is not generally the shortest possible tour.
An improvement heuristic begins with a complete candidate and applies transformations that reduce its objective value. In the travelling salesperson problem, a local transformation can remove two tour edges and reconnect the resulting paths in a different arrangement. Repeated application reaches a local optimum relative to that transformation, meaning that no available single move improves the solution. This condition does not imply global optimality because a better tour can require an intermediate move that does not immediately reduce cost.
Broader search frameworks that coordinate subordinate heuristics are commonly called metaheuristics. Their control mechanisms can regulate how candidate solutions are generated, how local optima are left, and how information from previous evaluations influences later exploration. Unlike admissible heuristic search, metaheuristic methods are generally characterized through empirical performance and problem-specific analysis rather than through a universal optimality condition.
Evaluation and computational trade-offs
The accuracy of a heuristic is only one component of its computational effect. A highly accurate estimate can be unproductive when its evaluation requires work comparable to solving the remaining subproblem. Conversely, a coarse estimate can be effective when it is computed inexpensively and separates promising states from large regions of irrelevant search.
Search performance is often examined through the number of generated states, the number of expanded states, memory consumption, and total execution time. These quantities need not vary together. A heuristic can reduce expansions while increasing total time because each expansion becomes more expensive. It can also reduce time while leaving peak memory largely unchanged if the algorithm retains a wide frontier.
Heuristic quality can additionally depend on the distribution of problem instances. An evaluation function derived from typical instances may provide little information on structurally different inputs. In machine learning, a heuristic can be learned from solved examples or from interaction with the problem environment. Learned estimates remain subject to the same algorithmic requirements as manually designed estimates; when admissibility or consistency is required, the learning method or a subsequent correction must enforce the relevant bound.
The term “heuristic” therefore covers several mathematically distinct roles. It can denote a lower bound used inside an exact algorithm, a ranking function that changes search order, or a rule that directly selects an approximate solution. These roles are unified by their use of restricted, comparatively inexpensive information to allocate computational effort within a larger problem-solving process.