Informed Search Strategies - AI Algorithms

What is Informed Search?

Informed search strategies use domain-specific knowledge—encoded as heuristic functions—to guide the exploration of the search space toward the goal. Unlike uninformed (blind) search that expands nodes without preference, informed search prioritizes nodes that appear more promising, often dramatically reducing the number of nodes explored.

The key insight is simple: if you have a way to estimate how far a node is from the goal, you can expand closer-looking nodes first. This estimate is called a heuristic function h(n), and the quality of this function determines how efficiently the search proceeds.

Informed search encompasses several algorithms: Greedy Best-First Search, A* Search, IDA* (Iterative Deepening A*), Recursive Best-First Search (RBFS), and Simplified Memory-Bounded A* (SMA*). The most important are Greedy Best-First Search and A*, which we'll study in depth.

Heuristic Functions

A heuristic function h(n) estimates the cost from node n to the nearest goal state. It encodes problem-specific knowledge that the search algorithm itself cannot derive from the graph structure alone.

Properties of Good Heuristics

Admissibility: h(n) ≤ h*(n) for all n, where h*(n) is the true optimal cost to the goal. An admissible heuristic never overestimates. This property guarantees optimality for A*.

Consistency (Monotonicity): h(n) ≤ cost(n, n') + h(n') for every successor n' of n. Consistent heuristics are always admissible, and they ensure A* never re-expands nodes.

Dominance: Heuristic h₂ dominates h₁ if h₂(n) ≥ h₁(n) for all n (both admissible). A dominant heuristic is always more efficient—it expands fewer nodes.

Example: 8-Puzzle Heuristics

Consider the 8-puzzle (sliding tiles):

Manhattan distance dominates misplaced tiles: h₂(n) ≥ h₁(n) for all states. In practice, h₂ explores far fewer nodes.

Greedy Best-First Search

Greedy Best-First Search (GBFS) expands the node with the lowest heuristic value h(n). It ignores the cost already paid to reach the node—only looking at estimated remaining cost.

Algorithm

Worked Example

Graph with heuristic values (straight-line distance to goal G):

Properties

• Complete: No (can loop without graph-search). With explored set: Yes in finite spaces.
• Optimal: No (ignores path cost g(n))
• Time: O(b^m) worst case, but good heuristics reduce this dramatically
• Space: O(b^m) — stores entire frontier

GBFS is fast but suboptimal. It's the "greedy" approach—looks locally best but may miss globally optimal paths.

A* Search

A* combines the actual cost to reach a node g(n) with the heuristic estimate h(n):

f(n) = g(n) + h(n)

This evaluation function estimates the total cost of the cheapest solution through node n. A* expands nodes in order of increasing f(n).

Why A* is Optimal

With an admissible heuristic, A* never expands a node whose f-value exceeds the optimal solution cost C*. Any goal node with g(goal) > C* will have f(goal) > C* and won't be expanded before the optimal goal.

Detailed Trace

IDA* (Iterative Deepening A*)

IDA* applies iterative deepening to A*. Instead of a depth limit, it uses an f-cost limit:

IDA* uses O(bd) memory (like DFS) while maintaining A*'s optimality. It's the preferred algorithm when memory is limited—common in game AI where millions of states exist.

Heuristic Design Techniques

Relaxed Problems

Remove constraints from the original problem. The optimal solution to the relaxed problem is an admissible heuristic for the original.

• 8-puzzle: Remove "can't move through other tiles" → Manhattan distance
• TSP: Remove "must visit each city once" → Minimum spanning tree cost
• Route planning: Remove "must follow roads" → Straight-line distance

Pattern Databases

Pre-compute exact solution costs for subproblems and store them in a lookup table. For the 15-puzzle, solving just tiles {1,2,3,4,5,6,7,8} gives an admissible heuristic for the full puzzle.

Combining Heuristics

Given multiple admissible heuristics h₁, h₂, ..., hₖ:

• h(n) = max(h₁(n), h₂(n), ..., hₖ(n)) is admissible and dominates each individual heuristic.

Comparison: Informed vs. Uninformed

Key Takeaways

1. Heuristic quality determines efficiency: Better heuristics = fewer expanded nodes
2. Admissibility guarantees optimality for A* — always underestimate
3. Greedy is fast but suboptimal — useful when any solution suffices
4. **A* is the gold standard** for optimal informed search
5. **IDA* saves memory** at the cost of re-expansion — preferred for large state spaces