Heuristic Function

An admissible heuristic never overestimates the true cost to reach the goal. This is the most critical property for guaranteeing that the A* search algorithm will find an optimal path. Formally, for all states n, h(n) ≤ h*(n), where h*(n) is the true optimal cost to the goal.

• Example: In pathfinding on a grid, the Manhattan distance (sum of horizontal and vertical steps) is admissible if movement is only allowed in four cardinal directions, as it is a straight-line lower bound.
• Consequence: If a heuristic is admissible, A* is guaranteed to be optimal.

A consistent heuristic satisfies the triangle inequality. For every node n and its successor n' generated by action a with cost c(n, a, n'), the heuristic estimate must obey: h(n) ≤ c(n, a, n') + h(n'). This implies that the estimated cost from n to the goal is no greater than the step cost to a successor plus the estimated cost from there.

• Key Implication: Consistency is a stronger condition than admissibility. All consistent heuristics are admissible, but not all admissible heuristics are consistent.
• Benefit: If a heuristic is consistent, A* never needs to re-expand a node after it is placed in the closed set, making it more efficient.

Given two admissible heuristics h1 and h2 for the same problem, h2 dominates h1 if h2(n) ≥ h1(n) for all states n. A dominating heuristic provides a tighter, more accurate estimate of the true cost.

• Effect on Search: A dominating heuristic will typically cause A* to expand fewer nodes because it provides better guidance, pruning the search space more effectively.
• Example: For the 8-puzzle, the Manhattan distance heuristic dominates the simpler misplaced tiles heuristic, as it provides a higher (but still admissible) estimate, leading to faster search.

Informedness refers to how accurately a heuristic estimates the true cost. A perfectly informed heuristic h(n) = h*(n) would lead the search directly to the goal with no exploration. In practice, heuristics balance computational cost of evaluation with accuracy.

• Trade-off: A more informed heuristic (e.g., solving a relaxed version of the problem) may be more expensive to compute per node. The optimal choice minimizes total search time: (Nodes Expanded) * (Cost per Node Evaluation).
• Engineering Principle: The best heuristic is often problem-specific, leveraging domain knowledge to provide strong guidance without prohibitive computational overhead.

A heuristic must be computationally inexpensive to evaluate. It is called millions of times during a search, so its runtime is a primary factor in overall algorithm performance.

• Fast Approximations: Heuristics are often simple, closed-form functions (like Euclidean distance) or the solution to a relaxed problem that can be computed quickly (like ignoring certain constraints in planning).
• Pitfall: An extremely accurate heuristic that is too slow to compute can result in worse overall performance than a simpler, faster, slightly less informed heuristic.

A powerful method for designing admissible heuristics is problem relaxation. By removing constraints from the original problem, the resulting solution cost serves as a perfect admissible heuristic for the harder problem.

• Classic Example: For the 8-puzzle, relaxing the rule that a tile can only move into an adjacent empty square (allowing tiles to move to any adjacent square) yields the Manhattan distance heuristic.
• Systematic Design: This approach provides a formal methodology: define a relaxed version of your problem that is easy to solve optimally, and use its solution cost as h(n).

A class of algorithms that use a heuristic function to guide exploration toward the most promising regions of a vast state space. Unlike uninformed searches (e.g., BFS, DFS), they prioritize nodes based on an estimated cost to the goal.

• A* is the canonical example, combining the path cost from the start with the heuristic estimate to guarantee an optimal solution if the heuristic is admissible.
• Greedy Best-First Search uses only the heuristic, making it faster but not optimal.
• These algorithms are fundamental to automated planning systems and agentic cognitive architectures where computational resources are limited.

A broader term for any function that assigns a numerical score to a game state or partial solution. While a heuristic function estimates cost-to-goal, an evaluation function can estimate overall utility, desirability, or likelihood of winning.

• In game-playing AI like chess, an evaluation function might combine material advantage, board control, and king safety.
• It is the core of the minimax algorithm with alpha-beta pruning, where it scores non-terminal states to drive adversarial search.
• Distinction: All heuristic functions are evaluation functions, but not all evaluation functions are admissible heuristics.

A best-first, heuristic search algorithm that combines tree search with random sampling. It does not use a traditional heuristic function but employs a rollout policy and the Upper Confidence Bound for Trees (UCT) formula to balance exploration and exploitation.

• UCT acts as a dynamic, statistics-based heuristic, guiding the search toward nodes with high average reward or high uncertainty.
• Famously used in AlphaZero to achieve superhuman performance in games.
• It is particularly effective in domains where a good heuristic function is difficult to design, relying instead on repeated simulation.

A heuristic function that never overestimates the true cost to reach the goal from any given node. This property is critical for guaranteeing the optimality of algorithms like A*.

• Example: In pathfinding on a grid, the straight-line (Euclidean) distance is admissible if movement cost is at least that distance.
• If a heuristic is admissible and consistent (monotonic), A* is optimally efficient.
• Designing a strong admissible heuristic that is as close as possible to the true cost without exceeding it is a key challenge in search problem formulation.

A heuristic search algorithm that explores a graph by expanding only the most promising nodes at each depth, limited by a parameter called the beam width. It uses a heuristic or evaluation function to rank and prune nodes.

• It is a greedy, breadth-first variant that sacrifices completeness and optimality for memory efficiency.
• Widely used in natural language processing for sequence generation (e.g., machine translation, text summarization) where the state space is the space of possible word sequences.
• The beam width controls the trade-off between search quality and computational cost.

The set of all possible configurations or situations that an agent or system can be in. A heuristic function operates on this space, estimating the distance from any given state to a goal state.

• The size and structure of the state space determine the necessity and effectiveness of heuristic guidance. Exponentially large spaces require informed search.
• In Tree-of-Thought reasoning, each "thought" or reasoning step is a node in a mental state space that the agent explores.
• Search algorithms systematically explore this space, and heuristics act as a compass to navigate it efficiently.