Advanced Search Algorithms in AI

Understanding Node Expansion in Graph Search

In any graph‑search algorithm, a node represents a distinct state of the problem. Expanding a node means generating all of its successors and evaluating them for further exploration. When the same node is expanded more than once, the algorithm may waste valuable time recomputing information that has already been processed. This redundancy creates duplicate subtrees, which multiply the total amount of work and lead to an exponential blow‑up in the search effort.

Key points to remember:

• Duplicate subtrees cause the search tree to grow faster than necessary.
• Each repeated expansion recomputes g (path cost) and h (heuristic) values for the same state.
• Effective graph‑search implementations use closed lists or visited sets to avoid re‑expansion.

Greedy Best‑First Search: Evaluation Function and Completeness

What does f(n) represent?

Greedy Best‑First Search (GBFS) relies on a simple evaluation function:

f(n) = h(n), where h(n) is an estimate of the remaining cost from node n to the goal. GBFS ignores the cost already incurred (g(n)) and selects the node that appears closest to the goal according to the heuristic.

Why GBFS is not complete in general

Because GBFS follows the heuristic blindly, it can become trapped in loops or dead‑ends that the heuristic does not recognize as undesirable. If the heuristic leads the search into a region of the state space with no path to the goal, the algorithm may keep expanding nodes indefinitely, exhausting memory or time without ever reaching a solution.

Best practices to improve completeness include:

• Using a tie‑breaking strategy that prefers nodes with lower g(n) when h(n) values are equal.
• Combining GBFS with a depth limit or a fallback to uniform‑cost search.

A* Search: Optimality, Heuristics, and Contours

Heuristic requirements for optimal A*

For A* to guarantee optimal solutions in graph search, the heuristic must be consistent (monotonic). Consistency means that for every node n and each successor n' generated by an action with cost c(n,n'), the following inequality holds:

h(n) ≤ c(n,n') + h(n'). Consistency implies admissibility and ensures that the f-value (f(n)=g(n)+h(n)) never decreases along a path, allowing A* to expand nodes in non‑decreasing order of f.

Heuristic dominance in the 8‑Puzzle

Given two admissible heuristics h₁ and h₂ where h₂(n) ≥ h₁(n) for every state n, h₂ is said to dominate h₁. A dominating heuristic is more informed; it provides a tighter lower bound on the true cost to the goal. Consequently, A* using h₂ will generally expand fewer nodes than A* using h₁, leading to faster convergence while preserving optimality.

Understanding the contour i in A*

In the analysis of A*, a contour groups together all nodes that share the same f-value. The i‑th contour consists of every node whose f-value equals the i‑th smallest distinct f-cost encountered during the search. Visualize the search frontier as layered shells: the first contour contains nodes with the lowest f, the second contour the next higher f, and so on. This concept is useful for proving properties such as optimality and for designing memory‑bounded variants of A*.

Consistent Heuristics and Monotonic f‑Values

A consistent heuristic guarantees that the f-value of a node never decreases along any path. Formally, if n expands to n', then f(n) ≤ f(n'). This monotonicity has two important consequences:

• Once a node is removed from the open list, the best path to that node has been found, eliminating the need for re‑expansion.
• The algorithm can safely use a closed list without risking the loss of optimal solutions.

In practice, many classic heuristics—such as the Manhattan distance for sliding‑tile puzzles—are both admissible and consistent, making them ideal choices for A* implementations.

Simulated Annealing: Temperature and Acceptance Probability

Simulated Annealing (SA) is a stochastic optimization technique inspired by the physical process of annealing metals. The central control parameter is the temperature T. At each iteration, SA proposes a move to a neighboring solution. If the move improves the objective, it is always accepted. If the move worsens the objective, it is accepted with probability exp(-ΔE / T), where ΔE is the increase in cost.

Higher temperatures increase the likelihood of accepting worse moves, allowing the algorithm to escape local minima early in the search. As T gradually cools, the acceptance probability drops, and the search becomes more greedy, converging toward a (potentially) global optimum.

Key guidelines for effective SA:

• Choose an initial temperature that yields an acceptance rate of roughly 80‑90%.
• Define a cooling schedule (e.g., geometric decay T_{k+1}=αT_k with 0<α<1).
• Terminate when the temperature falls below a predefined threshold or when improvements cease.

Putting It All Together: A Practical Study Guide

When preparing for exams or interviews on advanced search algorithms, focus on the following interconnected concepts:

• Node re‑expansion: Understand why duplicate subtrees cause exponential growth and how closed lists prevent it.
• Greedy Best‑First Search: Remember that f(n)=h(n), why the algorithm is fast but not complete, and strategies to mitigate incompleteness.
• A* optimality: Master the definition of consistency, its relationship to monotonic f-values, and how it ensures that the first goal node found is optimal.
• Heuristic dominance: Be able to compare two admissible heuristics and explain why the larger (more informed) one reduces node expansions.
• Contours in A*: Visualize search layers by distinct f-values and use this mental model when analyzing algorithmic complexity.
• Simulated Annealing: Articulate the role of temperature, the acceptance probability formula, and the importance of a well‑designed cooling schedule.

By linking each quiz question to these broader themes, you will develop a deep, transferable understanding of why advanced search algorithms behave the way they do, and you will be prepared to apply this knowledge to novel AI problems.