Heuristic Evaluation

An admissible heuristic never overestimates the true cost to reach the goal from any given node. Formally, for all nodes n, h(n) ≤ h*(n), where h*(n) is the true optimal cost to the goal. This is the fundamental property required for A search* to guarantee an optimal solution. A common example is the straight-line distance in a pathfinding problem, which is always less than or equal to the actual road distance.

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 must obey: h(n) ≤ c(n, a, n') + h(n'). This implies that the estimated cost to the goal from n is no greater than the step cost to its successor plus the estimated cost from there. Consistency is a stronger condition than admissibility; all consistent heuristics are admissible, and consistency ensures A* finds an optimal path without needing to re-expand nodes.

Given two admissible heuristics h1 and h2 for the same problem, h1 dominates h2 if h1(n) ≥ h2(n) for all nodes n. A dominating heuristic provides a tighter, more accurate estimate of the true cost. This leads to a more informed search, as the algorithm will expand fewer nodes. For example, in the 8-puzzle, the Manhattan distance heuristic dominates the misplaced tiles heuristic, making it more efficient for guiding the search.

A heuristic must be computationally inexpensive to evaluate. The primary purpose of a heuristic is to provide a quick estimate to guide the search; if computing h(n) is as expensive as solving the problem itself, the heuristic offers no benefit. The trade-off is between the informedness of the heuristic (how many nodes it prunes) and the time spent calculating it at each node. Effective heuristics, like pattern databases for puzzles, pre-compute costs for subproblems to provide fast, informative estimates during search.

The informedness of a heuristic refers to how closely its estimate approximates the true cost h*(n). A perfectly informed heuristic (h(n) = h*(n)) would lead the search directly to the goal. Greater informedness typically reduces the branching factor and the number of nodes expanded. However, increasing informedness often comes at the cost of higher computational overhead. The design of a heuristic involves balancing this accuracy with the efficiency property.

Effective heuristics are derived from a relaxed version of the original problem. By removing constraints, you create a problem that is easier to solve, and the cost of the solution to the relaxed problem serves as an admissible heuristic. Common relaxation methods include:

• Ignoring constraints (e.g., allowing tiles to move through each other).
• Decomposing the problem into independent subproblems.
• Using a precomputed pattern database for state-space subsets. This formal approach, known as deriving heuristics from relaxed models, guarantees admissibility and provides a systematic way to create strong heuristics.

A heuristic function (often denoted h(n)) is a problem-specific, approximate function used in search algorithms to estimate the cost from a given node to the goal state. It provides a 'rule of thumb' to guide the search toward promising areas without performing an exhaustive calculation.

• Key Property: Must be admissible (never overestimates the true cost) to guarantee optimality in algorithms like A*.
• Example: In pathfinding on a grid, the Manhattan distance is a common heuristic for the number of moves required to reach a target.
• Role: Converts raw state data into a single numerical score, enabling algorithms to prioritize node expansion.

A Search* is a best-first graph traversal and pathfinding algorithm that finds the lowest-cost path by combining the actual cost to reach a node, g(n), with the heuristic estimate to the goal, h(n). Its evaluation function is f(n) = g(n) + h(n).

• Optimality: Guaranteed to find an optimal solution if the heuristic is admissible and the graph is finite.
• Efficiency: More efficient than Dijkstra's algorithm because the heuristic focuses the search.
• Use Case: Foundational for robotics navigation, game AI pathfinding, and puzzle solvers (e.g., 15-puzzle).

Best-First Search is a family of graph search algorithms that select the next node to expand based solely on an evaluation function, typically a heuristic h(n). It prioritizes nodes that appear closest to the goal.

• Greedy Best-First Search: A specific variant that uses only the heuristic (f(n) = h(n)). It is fast but not optimal and can get stuck in loops.
• Frontier Management: Uses a priority queue to always expand the most promising node first.
• Contrast with A*: Unlike A*, it does not consider the cost incurred so far (g(n)), which can lead to suboptimal paths.

Monte Carlo Tree Search (MCTS) is a heuristic search algorithm for optimal decision-making in sequential decision processes, like games. It builds a search tree by performing random simulations (playouts) from leaf nodes and uses the results to guide future exploration toward promising branches.

• Four Steps: Selection, Expansion, Simulation, Backpropagation.
• Heuristic Role: The Upper Confidence Bound for Trees (UCT) formula balances exploration of less-visited nodes and exploitation of high-value nodes.
• Famous Application: Core algorithm behind AlphaGo and other game-playing AI systems that defeated human champions.

These are critical mathematical properties of a heuristic function that guarantee the optimality and efficiency of search algorithms like A*.

• Admissible Heuristic: Never overestimates the true cost to reach the goal. This property is required for A* to guarantee an optimal solution.
• Consistent (Monotonic) Heuristic: For every node n and its successor n', the estimated cost of reaching the goal from n is not greater than the step cost to n' plus the estimated cost from n'. Formally: h(n) ≤ c(n, n') + h(n'). A consistent heuristic is always admissible.
• Impact: Consistency ensures that A* finds the optimal path without needing to re-expand nodes, improving efficiency.

Local Search algorithms are optimization techniques that iteratively improve a candidate solution by exploring its immediate neighborhood in the state space. They use heuristic evaluation to decide which neighboring state to move to next.

• Hill Climbing: Moves to the neighboring state with the best heuristic value, getting stuck in local optima.
• Simulated Annealing: Allows moves to worse states with a probability that decreases over time, helping escape local optima.
• Tabu Search: Uses memory (a tabu list) to avoid recently visited states, forcing exploration.
• Application: Used for NP-hard problems like scheduling, vehicle routing, and circuit design where the complete state space is too large to search exhaustively.