Search Algorithms in Artificial Intelligence: A Comprehensive Course
Understanding how machines explore problem spaces is a cornerstone of artificial intelligence (AI). This course breaks down the most frequently tested concepts from a typical AI search quiz, turning multiple‑choice questions into clear, SEO‑friendly explanations. Whether you are preparing for an exam, a certification, or simply want to deepen your knowledge, the sections below cover everything from greedy best‑first search to alpha‑beta pruning in game playing.
Greedy Best‑First Search vs. A* Search
Both algorithms belong to the family of informed (heuristic‑driven) searches, but they differ fundamentally in the evaluation function they use.
- Greedy best‑first search evaluates a node n with f(n) = h(n), where h(n) is the estimated cost from n to the goal. It ignores the cost already incurred (g(n)).
- A* search combines both the path cost so far and the heuristic estimate: f(n) = g(n) + h(n). This balance allows A* to guarantee optimality when the heuristic is admissible and consistent.
The key distinction is that greedy search pursues the node that looks closest to the goal, while A* pursues the node that looks cheapest overall. Because greedy search does not account for g(n), it can be fast but may miss the optimal solution.
Heuristic Consistency and Optimality in A*
For A* to remain optimal, the heuristic must be consistent (also called monotonic). Consistency means that for every node n and each successor n' generated by an action with step cost c(n,n'), the following inequality holds:
h(n) ≤ c(n,n') + h(n')
When this condition is satisfied, the f‑values (g + h) never decrease along a path. Consequently, once a node is expanded, the algorithm has already found the cheapest path to that node, preventing later expansions from producing a cheaper solution. This property is essential for A*'s optimality in graph search, where nodes can be revisited via different routes.
Admissible Heuristics and Dominance
An admissible heuristic never overestimates the true cost to reach the goal. When you have two admissible heuristics h₁ and h₂ such that h₂(n) ≥ h₁(n) for every node n, h₂ is said to dominate h₁. Dominance implies that A* using h₂ will expand **fewer or equal** nodes compared to using h₁, because the larger heuristic values provide tighter lower bounds, guiding the search more directly toward the goal.
It is important to note that dominance does **not** affect admissibility: if both heuristics are admissible, the dominating one remains admissible.
Why Greedy Best‑First Search Can Be Incomplete
Greedy best‑first search can become incomplete on certain maps because it lacks a built‑in mechanism to avoid revisiting the same states. If the heuristic leads the algorithm into a loop—e.g., a set of states where each appears to be closer to the goal than the last—the search may cycle forever without ever reaching the goal. Adding a closed list (a record of already expanded nodes) or switching to a more robust algorithm like A* resolves this issue.
Effective Branching Factor (b*) in A*
The effective branching factor, denoted b*, provides a single‑number summary of how "wide" the search behaved. It answers the question:
What uniform tree would contain exactly the same number of nodes as the A* search actually expanded?
Mathematically, if N nodes were generated and the solution depth is d, b* satisfies the equation:
N ≈ 1 + b* + (b*)² + … + (b*)^d
Solving for b* yields a value that captures the overall efficiency of the search. A lower b* indicates that the heuristic was highly informative, reducing the effective width of the search tree.
Simulated Annealing: Escaping Local Optima
Simulated annealing is a probabilistic optimization technique inspired by the cooling of metal. Its power to escape local optima stems from the acceptance of worsening moves with a probability that depends on a temperature parameter T:
P(accept) = exp(-ΔE / T)
When T is high, the algorithm is willing to accept large increases in the objective function (ΔE > 0), allowing it to jump out of local minima. As the temperature gradually decreases, the acceptance probability drops, and the search becomes more greedy, converging toward a (hopefully) global optimum.
Genetic Algorithms: The Role of the Crossover Operator
In a genetic algorithm (GA), a population of candidate solutions evolves over successive generations. The crossover operator is the primary mechanism for combining genetic material from two parent chromosomes to produce offspring. By mixing traits, crossover encourages the exploration of new regions of the search space while preserving high‑quality building blocks discovered by the parents.
Other GA operators include mutation (randomly flipping bits) and selection (choosing the fittest individuals). However, without crossover, a GA would behave more like a random search, losing the advantage of recombining useful sub‑solutions.
Alpha‑Beta Pruning in Game Tree Search
Alpha‑beta pruning is an optimization for the minimax algorithm used in two‑player zero‑sum games. When evaluating a MAX node, the algorithm maintains two bounds:
- α (alpha): the best value that the MAX player can guarantee so far.
- β (beta): the best value that the MIN player can guarantee.
A branch can be pruned when the value of a child node is **less than the current α bound**. In that case, the MAX player already has a better alternative, so exploring the remaining children of that branch cannot improve the final decision. This "floor" analogy—α as the floor that MAX will never go below—helps visualize why the branch is irrelevant.
Pruning at a MIN node works symmetrically: if a child’s value exceeds β, the branch is cut because MIN already has a better (lower) option.
Putting It All Together: Choosing the Right Search Strategy
When designing an AI system, the choice of search algorithm depends on several factors:
- Optimality requirement: Use A* with a consistent, admissible heuristic.
- Memory constraints: Greedy best‑first or iterative deepening A* may be preferable.
- Problem landscape: For large, noisy spaces, stochastic methods like simulated annealing or genetic algorithms can find good solutions when exact optimality is infeasible.
- Game playing: Combine minimax with alpha‑beta pruning to achieve deep look‑ahead while keeping computation tractable.
By mastering the concepts outlined above—evaluation functions, heuristic properties, branching factors, and pruning techniques—you will be equipped to select, adapt, and explain the most effective search algorithm for any AI challenge.
Key Takeaways
- Greedy best‑first uses f(n)=h(n); A* uses f(n)=g(n)+h(n).
- Heuristic consistency guarantees non‑decreasing f‑values, a prerequisite for A* optimality.
- A dominating admissible heuristic expands fewer nodes.
- Greedy search can loop indefinitely without a closed list.
- The effective branching factor b* translates actual node expansion into an equivalent uniform tree size.
- Simulated annealing escapes local optima by occasionally accepting worse moves.
- Crossover in genetic algorithms merges parent solutions to explore new regions.
- Alpha‑beta pruning cuts a MAX branch when its value is less than α, saving computation.
These principles form the backbone of modern AI search techniques and are essential knowledge for students, practitioners, and interview candidates alike.
