A* Search

The core mechanism of A* is the evaluation function f(n) = g(n) + h(n). This function determines the priority of nodes in the open set (frontier).

• g(n) is the exact, known cost from the start node to node n.
• h(n) is the heuristic function, estimating the cost from n to the goal.
• The algorithm always expands the node with the lowest f(n) value first, balancing the certainty of the path taken with the promise of the path ahead.

A* is guaranteed to find a cost-optimal path if its heuristic function h(n) is admissible. An admissible heuristic never overestimates the true cost to reach the goal. For example, in pathfinding on a grid, the Manhattan distance is admissible if movement is only allowed horizontally and vertically.

If h(n) is admissible, A* is optimally efficient for a given heuristic—no other optimal algorithm using the same heuristic is guaranteed to expand fewer nodes.

A stronger property than admissibility is consistency (or monotonicity). A heuristic is consistent if for every node n and its successor n', the estimated cost satisfies the triangle inequality: h(n) ≤ cost(n, n') + h(n'). This also means h(goal) = 0.

A consistent heuristic guarantees that A* finds an optimal path without ever needing to re-expand a node from the closed set, making the algorithm more efficient. All consistent heuristics are admissible, but not all admissible heuristics are consistent.

A* is complete on finite graphs with non-negative edge costs and a reasonable branching factor. This means it will always find a solution if one exists. Its completeness stems from its systematic exploration, similar to Uniform-Cost Search, but guided by the heuristic to improve speed.

If no path exists, A* will exhaust the reachable state space and terminate, reporting failure.

The worst-case time and space complexity of A* is O(b^d), where b is the branching factor and d is the depth of the optimal solution. This is exponential, as it may need to explore most of the search space.

In practice, a good heuristic dramatically reduces the effective branching factor, pruning large parts of the tree. The primary memory constraint is the open set (typically a priority queue) and the closed set (for tracking visited nodes), which can grow large for complex problems.

A* occupies a specific point in the search algorithm design space:

• vs. Greedy Best-First Search: Uses only h(n). Faster but not optimal.
• vs. Uniform-Cost Search (Dijkstra's): Uses only g(n). Optimal but explores uniformly in all directions.
• vs. IDA*: Uses iterative deepening with an f-cost threshold. Memory-efficient but can suffer from overhead in state regeneration.

A*'s balance of g(n) and h(n) makes it the de facto standard for informed pathfinding and graph traversal where an informative heuristic is available.

A heuristic function, denoted h(n), is the core estimation mechanism that guides A* and other informed search algorithms. It provides an admissible (never overestimates) and ideally consistent estimate of the cost from a given node n to the nearest goal.

• Purpose: To prioritize exploration of the most promising paths, drastically reducing the search space compared to uninformed methods.
• Key Property - Admissibility: For A* to guarantee optimality, h(n) must be admissible—it must never overestimate the true cost to the goal. A common example is the straight-line distance in pathfinding.
• Impact on Performance: The more accurate the heuristic (closer to the true cost without overestimating), the fewer nodes A* will expand, making search exponentially more efficient.

Uniform-Cost Search is an uninformed search algorithm and a direct precursor to A*. It expands the node with the lowest path cost from the start, g(n), guaranteeing optimality in weighted graphs.

• Relationship to A*: A* can be viewed as Uniform-Cost Search plus a heuristic. UCS uses only g(n) in its evaluation function f(n) = g(n). A* adds h(n) to form f(n) = g(n) + h(n).
• Trade-off: Without a heuristic, UCS blindly expands in all directions based on cost, leading to a larger, more circular search frontier. A* uses h(n) to "pull" the search directly toward the goal.
• Guarantee: Both algorithms are optimal when all step costs are non-negative, but A* achieves this with far fewer node expansions when a good heuristic is available.

Greedy Best-First Search is an informed search algorithm that expands the node judged to be closest to the goal, based solely on the heuristic function h(n).

• Evaluation Function: Uses f(n) = h(n). It ignores the cost incurred to reach the node (g(n)).
• Comparison with A*: While often very fast, Greedy Search is neither optimal nor complete. It can get stuck in infinite loops or choose a fast but expensive path because it doesn't account for the path cost. A* balances the known cost (g(n)) with the estimated future cost (h(n)), ensuring optimality.
• Use Case: Useful for quick, approximate solutions where optimality is not critical, or as part of more complex algorithms like Beam Search.

Iterative Deepening A* is a memory-efficient variant of A* that combines its heuristic guidance with the space efficiency of Iterative Deepening Depth-First Search.

• Mechanism: Instead of maintaining a large priority queue (open set), IDA* performs a series of depth-first searches with an increasing cost threshold for f(n) = g(n) + h(n). It explores all nodes where f(n) is less than or equal to the current threshold.
• Advantage: It uses linear space O(bd) in the depth of the solution, compared to A*'s exponential space requirement O(b^d) for storing the frontier. This makes it suitable for problems with enormous state spaces.
• Trade-off: Nodes may be re-expanded multiple times as the threshold increases, leading to higher time complexity than standard A*, but the massive memory savings are often worth it.

Beam Search is a heuristic search algorithm that explores a graph by expanding the most promising nodes in a limited set, called the beam width β, at each depth level.

• Memory Management: It is an optimization of Best-First Search or Breadth-First Search that drastically reduces memory usage by only keeping the top-β nodes at each step, pruning the rest.
• Comparison with A*: Unlike A*, which is optimal and complete, Beam Search is neither due to its aggressive pruning. It can discard the path that leads to the optimal solution.
• Primary Use: Extremely effective in domains like natural language generation (for decoding sequences from language models) and very large search spaces where storing the entire frontier is impossible, and a good, fast heuristic is available to rank nodes.

Dijkstra's Algorithm is a foundational graph algorithm for finding the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights.

• Core Similarity: A* and Dijkstra's share a fundamental structure: both use a priority queue to select the next node to expand based on a cost. For Dijkstra's, this cost is the known shortest distance from the source, g(n).
• Key Difference: Dijkstra's is uninformed; it expands nodes in a wavefront based solely on g(n). A* is informed, using f(n) = g(n) + h(n) to direct the wavefront toward the goal. When h(n) = 0 for all nodes, A* behaves identically to Dijkstra's Algorithm.
• Practical Implication: For single-pair shortest path problems (one start, one goal), A* is almost always faster than Dijkstra's if a good heuristic exists. Dijkstra's is essential for all-pairs or single-source analyses.