Repository navigation
Module 3a: Informed Search
Search algorithms in Artificial Intelligence are broadly categorized into uninformed (blind) search and informed (heuristic) search based on whether the algorithm possesses domain-specific knowledge beyond the basic problem definition.
-
Uninformed Search Paradigms:
- Algorithms such as Breadth-First Search (BFS), Depth-First Search (DFS), and Uniform Cost Search (UCS) navigate the state space systematically without any estimation of how far a given state is from the goal.
- For example, Uniform Cost Search expands frontier nodes strictly in order of accumulated path cost
$g(n)$ from the start state$n_{\text{start}}$ . While UCS guarantees finding an optimal path, it explores nodes uniformly in all directions (concentric spheres of increasing cost), leading to exponential time and space complexity$O(b^d)$ or$O\left(b^{1 + \left\lfloor \dfrac{C^*}{\epsilon} \right\rfloor}\right)$ , where$b$ is the branching factor,$d$ is the depth,$C^*$ is the optimal path cost, and$\epsilon$ is the minimum action cost.
-
Informed Search Paradigms:
- Informed search algorithms inject domain knowledge into the search process through a heuristic function
$h(n)$ . - Instead of exploring state space blindly and uniformly, an informed search agent prioritizes frontier states that appear most promising—specifically those estimated to be closer to a goal state.
- By leveraging heuristics, informed search dramatically prunes the effective search space, reducing node expansions by orders of magnitude compared to uninformed search.
- Informed search algorithms inject domain knowledge into the search process through a heuristic function
A heuristic function, denoted as
where
Key operational characteristics of
-
Quick Computation: A heuristic must be computationally inexpensive to calculate at runtime; if evaluating
$h(n)$ takes as long as searching the state space itself, the efficiency gain is lost. -
Correlation with True Remaining Cost: A quality heuristic tracks the actual remaining path cost
$h^*(n)$ , where$h^*(n)$ denotes the true cost of the optimal path from node$n$ to$n_{\text{goal}}$ . -
Guidance Mechanism: The value of
$h(n)$ acts as a quantitative ranking function to sort candidate nodes in the search frontier (priority queue).
The formulation of
-
Route Planning & GPS Navigation:
-
In a road network graph where states represent physical coordinates
$\overrightarrow{x}_n = (x_n, y_n)^T$ , a common heuristic is the Euclidean Distance (straight-line distance) to the destination coordinates$\overrightarrow{x}_{\text{goal}} = (x_{\text{goal}}, y_{\text{goal}})^T$ :$$h_{\text{Euclidean}}(n) = \left| \overrightarrow{x}_n - \overrightarrow{x}_{\text{goal}} \right|_2 = \sqrt{(x_n - x_{\text{goal}})^2 + (y_n - y_{\text{goal}})^2}$$ -
Alternatively, in grid-based road maps restricted to cardinal movements (North, South, East, West), the Manhattan Distance is utilized:
$$h_{\text{Manhattan}}(n) = \left| \overrightarrow{x}_n - \overrightarrow{x}_{\text{goal}} \right|_1 = |x_n - x_{\text{goal}}| + |y_n - y_{\text{goal}}|$$
-
-
Game of Chess:
- A heuristic in adversarial board games estimates board favorability and winning potential.
- In chess,
$h(n)$ can measure positional control, such as center square control (counting the number of central squares$d4, d5, e4, e5$ controlled by the agent's pieces) or material balance evaluations. A state that controls the center squares receives a lower remaining cost estimate (higher priority) than a peripheral state.
-
8-Tile Puzzle:
-
In a
$3 \times 3$ sliding tile puzzle, a baseline heuristic is the Misplaced Tiles Count, denoted as$h_1(n)$ :$$h_1(n) = \sum\limits_{i=1}^{8} \mathbb{I}(\text{tile}_i \text{ is not in its goal position})$$ where
$\mathbb{I}(\cdot)$ is the indicator function returning$1$ if true and$0$ if false. -
A more informative heuristic is the sum of Manhattan distances for all tiles to their respective target grid coordinates, denoted as
$h_2(n)$ :$$h_2(n) = \sum\limits_{i=1}^{8} \left( |x_i - x_{i,\text{goal}}| + |y_i - y_{i,\text{goal}}| \right)$$
-
In informed search algorithms, candidate nodes are evaluated and sorted in the search frontier using an evaluation function (also referred to as an objective function), denoted as
The general structure of
where:
-
$g(n)$ is the accumulated path cost incurred to travel from the start state$n_{\text{start}}$ to node$n$ . -
$h(n)$ is the heuristic estimate of the remaining path cost from node$n$ to$n_{\text{goal}}$ . -
$f(n)$ represents the total estimated cost of the cheapest path constrained to pass through node$n$ from$n_{\text{start}}$ to$n_{\text{goal}}$ .
Comparing search paradigms by objective function structure:
-
Uniform Cost Search (UCS):
$f(n) = g(n)$ (purely historical cost, no forward estimate). -
Greedy Best-First Search:
$f(n) = h(n)$ (purely forward heuristic estimate, ignores historical cost). -
$A^*$ Search Algorithm:$f(n) = g(n) + h(n)$ (balances historical path cost and forward heuristic estimate).
To preserve sound search mechanics and mathematical guarantees, any heuristic function
-
Goal State Boundary Condition:
$$h(n_{\text{goal}}) = 0$$ -
Mathematical & Physical Meaning: The estimated remaining cost at any goal state must evaluate precisely to zero, as no additional cost is required once the destination is reached. As an agent moves closer to
$n_{\text{goal}}$ , the heuristic value$h(n)$ monotonically decreases toward$0$ .
-
Mathematical & Physical Meaning: The estimated remaining cost at any goal state must evaluate precisely to zero, as no additional cost is required once the destination is reached. As an agent moves closer to
-
Non-Negativity Constraint:
$$\forall n \in S, \quad h(n) \ge 0$$ -
Mathematical & Physical Meaning: Edge costs
$c(n, a, n')$ in state space graphs are non-negative ($c(n, a, n') \ge 0$ ). Consequently, estimated path costs cannot be negative, preventing artificial inflation of node priorities.
-
Mathematical & Physical Meaning: Edge costs
A heuristic function
-
Formal Mathematical Definition: Let
$h^*(n)$ denote the true optimal path cost from node$n$ to$n_{\text{goal}}$ . A heuristic$h(n)$ is admissible if and only if:$$\forall n \in S, \quad 0 \le h(n) \le h^*(n)$$ -
Intuition:
- An admissible heuristic acts as an optimistic lower bound on the remaining path cost.
- Because
$h(n)$ is always lower bound optimistic ($h(n) \le h^*(n) $ ), search algorithms relying on admissible heuristics (such as$A^*$ Tree Search) will never prematurely discard or bypass a true optimal path in favor of an apparently cheaper suboptimal one. -
Example: Straight-line Euclidean distance
$h_{\text{Euclidean}}(n)$ between two spatial coordinates is strictly admissible for physical road navigation because no physical driving path can be shorter than a straight line. Thus,$h_{\text{Euclidean}}(n) \le h^*(n)$ holds universally.
A heuristic function
-
Formal Mathematical Definition: For every node
$n$ and every successor$n'$ generated by taking an action$a$ with step cost$c(n, n')$ , consistency requires:$$h(n) \le c(n, n') + h(n')$$ -
Triangle Inequality Intuition:
- In geometric terms, the estimated distance from
$n$ directly to$n_{\text{goal}}$ ($h(n) $ ) cannot exceed the cost of taking a step to an intermediate neighbor$n'$ ($c(n, n') $ ) plus the estimated distance from$n'$ to$n_{\text{goal}}$ ($h(n') $ ).
- In geometric terms, the estimated distance from
-
Mathematical Proof: Monotonic Non-Decreasing Sequence of
$f(n)$ : When a heuristic is consistent, the evaluated total cost$f(n)$ along any path is guaranteed to be non-decreasing. We derive this algebraic property below:
-
Algebraic Conclusion:
$f(n') \ge f(n)$ holds for all successor steps.
-
Impact on Search Execution & Node Reopening:
- Consistency is a stronger condition than admissibility (every consistent heuristic with
$h(n_{\text{goal}}) = 0$ is guaranteed to be admissible, but not all admissible heuristics are consistent). -
Elimination of Node Reopening: When an
$A^*$ Graph Search algorithm uses a consistent heuristic, the first time$A^*$ selects and expands a node$n$ from the open list, the accumulated path cost$g(n)$ is guaranteed to be the true minimal optimal cost to$n$ . - As a result, once a node is placed on the closed list (explored set),
$A^*$ will never discover a shorter path to it later. Node reopening is completely eliminated, optimizing memory and execution efficiency.
- Consistency is a stronger condition than admissibility (every consistent heuristic with
Greedy Best-First Search is an informed search strategy that evaluates nodes using solely a heuristic estimate of the remaining cost from node
where
Unlike Uniform-Cost Search, which minimizes accumulated past path cost
Greedy Best-First Search can be formulated in two distinct algorithmic variants depending on how candidate states are tracked: Tree Search (which maintains only an Open List) and Graph Search (which maintains both an Open List and a Closed List). The standard operational protocol for the Graph Search variant relies on two primary data structures:
-
Open List (Frontier): A priority queue ordered strictly in ascending order of heuristic values
$h(n)$ . The node at the head of the queue possesses the smallest$h(n)$ value. - Closed List (Explored Set): A hash set storing state identifiers of previously expanded nodes to prevent cyclic re-expansions in graph search.
The operational expansion loop for Graph Search proceeds as follows:
-
Selection: Pop node
$n$ with the minimal$h(n)$ from the Open List. -
Goal Test: Evaluate whether
$n$ satisfies the goal condition ($h(n) = 0$ ). If true, terminate and reconstruct the solution trajectory. -
Exploration: Insert
$n$ into the Closed List. -
Successor Generation: For each child node
$n'$ generated by valid actions at node$n$ :- If
$n'$ is neither in the Closed List nor already in the Open List, calculate$h(n')$ and insert$n'$ into the Open List. - If
$n'$ is already in the Open List, retain the existing entry (since$h(n')$ is state-dependent and invariant to path cost).
- If
To track node state transitions throughout the execution trace, the following visual color convention is utilized across all Mermaid diagrams:
- Active / Currently Expanded Node: Yellow
- Expanded Node (Closed List): Light Blue
- Frontier Node (Open List): Orange
- Goal Node: Green
Consider a search graph with Start state
$h(S) = 10$ -
$h(A) = 3$ ,$c(S, A) = 5$ -
$h(B) = 8$ ,$c(S, B) = 1$ -
$h(C) = 2$ ,$c(A, C) = 6$ -
$h(G) = 0$ ,$c(A, G) = 10$ ,$c(B, G) = 2$
Node
graph TD
classDef active fill:#fff2cc,stroke:#d6b656,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
classDef unvisited fill:#ffffff,stroke:#333333,stroke-width:1px;
S["S (h=10)"]:::active
A["A (h=3)"]:::frontier
B["B (h=8)"]:::frontier
C["C (h=2)"]:::unvisited
G["G (h=0)"]:::unvisited
S -- "c=5" --> A
S -- "c=1" --> B
A -- "c=6" --> C
A -- "c=10" --> G
B -- "c=2" --> G
-
Open List:
$[A(h=3), B(h=8)]$ -
Closed List:
${S}$
Node
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef active fill:#fff2cc,stroke:#d6b656,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
classDef goal fill:#d5e8d4,stroke:#82b366,stroke-width:2px;
S["S (h=10)"]:::expanded
A["A (h=3)"]:::active
B["B (h=8)"]:::frontier
C["C (h=2)"]:::frontier
G["G (h=0)"]:::frontier
S -- "c=5" --> A
S -- "c=1" --> B
A -- "c=6" --> C
A -- "c=10" --> G
B -- "c=2" --> G
-
Open List:
$[G(h=0), C(h=2), B(h=8)]$ -
Closed List:
${S, A}$
Node
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
classDef goal fill:#d5e8d4,stroke:#82b366,stroke-width:2px;
S["S (h=10)"]:::expanded
A["A (h=3)"]:::expanded
B["B (h=8)"]:::frontier
C["C (h=2)"]:::frontier
G["G (h=0)"]:::goal
S -- "c=5" --> A
S -- "c=1" --> B
A -- "c=6" --> C
A -- "c=10" --> G
B -- "c=2" --> G
-
Returned Path:
$S \to A \to G$ -
Total Path Cost:
$g(G) = c(S, A) + c(A, G) = 5 + 10 = 15$
The trace above highlights the core vulnerability of Greedy Best-First Search:
-
Suboptimality: The algorithm chose path
$S \to A \to G$ with a cost of$15$ because$h(A) = 3$ appeared more promising than$h(B) = 8$ . However, the optimal path is$S \to B \to G$ with a total cost of$c(S, B) + c(B, G) = 1 + 2 = 3$ . -
Local Optima Traps: If
$h(n)$ provides inaccurate guidance (e.g., in a maze with a dead-end wall that physically points toward the target location), Greedy Best-First Search blindly follows decreasing$h(n)$ values into dead-ends. -
Absence of Cost-Based Backtracking: Because
$g(n)$ is ignored, accumulated travel expenses cannot force the algorithm to re-evaluate alternative branches until all lower-$h(n)$ paths are fully exhausted.
The completeness of Greedy Best-First Search depends critically on whether the Tree Search or Graph Search formulation is employed:
-
Tree Search Formulation (No Closed List): Incomplete. In state spaces whose underlying state graph contains cycles or infinite paths, Greedy Best-First Tree Search can enter infinite loops. Because it lacks a Closed List to track visited states, cyclic paths in the state graph unroll into infinite branches in the search tree (e.g., oscillating endlessly between states
$A$ and$B$ if$h(A)$ and$h(B)$ remain lower than alternative frontier nodes). - Graph Search Formulation (With Closed List): Complete in finite state spaces. By maintaining a Closed List (Explored Set) of previously expanded state identifiers, duplicate state expansions are detected and pruned. This guarantees that the algorithm will not loop endlessly on cycles and will eventually examine all reachable states if a solution exists.
Let
-
Worst-Case Time Complexity:
$O(b^m)$ . If the heuristic function is misleading, the search expands the entire search tree down to maximum depth$m$ . -
Worst-Case Space Complexity:
$O(b^m)$ . All generated nodes must reside in memory within the Open List or Closed List. -
Best-Case Complexity:
$O(b \cdot d)$ , where$d$ is the depth of the optimal path. With an accurate heuristic, the search proceeds directly along the goal path, expanding$O(d)$ nodes with$b$ successors per level.
- Sensitivity: Search efficiency is entirely dependent on heuristic quality. Minor errors in relative heuristic rankings can cause exponential increases in node expansions.
-
Relation to Beam Search: Beam Search is a memory-constrained variant of Greedy Best-First Search. Instead of retaining all generated nodes in the Open List, Beam Search restricts the Open List capacity to a fixed number
$k$ (the "beam width"). Successors exceeding rank$k$ are permanently discarded, trading completeness for strict$O(k \cdot b)$ memory bounds.
The
The overall evaluation function
where:
-
$g(n): S \to \mathbb{R}_{\ge 0}$ represents the exact accumulated path cost incurred from the start node$s_0$ to node$n$ . -
$h(n): S \to \mathbb{R}_{\ge 0}$ represents the estimated remaining cost from node$n$ to the closest goal state$g_{\text{goal}}$ . -
$f(n)$ estimates the total cost of the complete solution path constrained to pass through node$n$ .
By incorporating
-
Open List (Frontier): A min-priority queue containing all generated but unexpanded nodes, ordered strictly in ascending order of their total estimated evaluation cost
$f(n)$ . If two nodes share identical$f(n)$ values, ties are typically broken by selecting the node with the smaller$h(n)$ value (or larger$g(n)$ value) to prioritize nodes closer to the goal. - Closed List (Explored Set): A hash set storing state identifiers of nodes that have already been expanded. In Graph Search, once a node is placed in the Closed List under a consistent heuristic, the algorithm guarantees that the optimal path to that node has been finalized, preventing redundant re-expansions.
The operational execution loop of
-
Selection: Extract the node
$n$ with the minimal$f(n)$ value from the Open List. -
Goal Test: Evaluate whether
$n$ satisfies the goal condition ($h(n) = 0$ ).- Critical Rule: The goal test is performed upon node selection (extraction from the Open List), NOT upon successor generation. Testing at generation time can return a suboptimal path because a cheaper path to the goal might remain unexpanded in the Open List.
-
Exploration: Insert node
$n$ into the Closed List. -
Successor Generation: For each child
$n'$ produced by legal actions at$n$ with edge cost$c(n, n')$ :- Calculate tentative path cost:
$g_{\text{tentative}}(n') = g(n) + c(n, n')$ . - Calculate total estimated cost:
$f_{\text{tentative}}(n') = g_{\text{tentative}}(n') + h(n')$ . -
State Update Rules:
-
Case A (Unvisited State): If
$n'$ is neither in the Open List nor the Closed List, record its parent$n$ , store$g(n')$ and$f(n')$ , and insert$n'$ into the Open List. -
Case B (State in Open List): If
$n'$ is already in the Open List and$g_{\text{tentative}}(n') < g_{\text{existing}}(n')$ , update$n'$ 's parent pointer to$n$ , update$g(n')$ and$f(n')$ , and decrease its key in the priority queue. -
Case C (State in Closed List): If
$n'$ is in the Closed List, under a consistent heuristic$h(n)$ ,$g_{\text{tentative}}(n') \ge g_{\text{existing}}(n')$ is guaranteed. Thus, the node in the Closed List is ignored and never reopened.
-
Case A (Unvisited State): If
- Calculate tentative path cost:
To directly compare
$h(S) = 10$ -
$h(A) = 3$ ,$c(S, A) = 5 \implies f(A) = 5 + 3 = 8$ -
$h(B) = 8$ ,$c(S, B) = 1 \implies f(B) = 1 + 8 = 9$ -
$h(C) = 2$ ,$c(A, C) = 6 \implies f(C) = (5 + 6) + 2 = 13$ -
$h(G) = 0$ ,$c(A, G) = 10 \implies f(G_{\text{via } A}) = (5 + 10) + 0 = 15$ -
$h(G) = 0$ ,$c(B, G) = 2 \implies f(G_{\text{via } B}) = (1 + 2) + 0 = 3$
Node
graph TD
classDef active fill:#fff2cc,stroke:#d6b656,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
classDef unvisited fill:#ffffff,stroke:#333333,stroke-width:1px;
S["S (g=0, h=10, f=10)"]:::active
A["A (g=5, h=3, f=8)"]:::frontier
B["B (g=1, h=8, f=9)"]:::frontier
C["C (g=?, h=2, f=?)"]:::unvisited
G["G (g=?, h=0, f=?)"]:::unvisited
S -- "c=5" --> A
S -- "c=1" --> B
A -- "c=6" --> C
A -- "c=10" --> G
B -- "c=2" --> G
-
Open List:
$[A(f=8), B(f=9)]$ -
Closed List:
${S}$
Node
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef active fill:#fff2cc,stroke:#d6b656,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
classDef goal fill:#d5e8d4,stroke:#82b366,stroke-width:2px;
S["S (g=0, h=10, f=10)"]:::expanded
A["A (g=5, h=3, f=8)"]:::active
B["B (g=1, h=8, f=9)"]:::frontier
C["C (g=11, h=2, f=13)"]:::frontier
G["G (g=15, h=0, f=15)"]:::frontier
S -- "c=5" --> A
S -- "c=1" --> B
A -- "c=6" --> C
A -- "c=10" --> G
B -- "c=2" --> G
-
Open List:
$[B(f=9), C(f=13), G(f=15)]$ -
Closed List:
${S, A}$
Node
$g_{\text{tentative}}(G) = g(B) + c(B, G) = 1 + 2 = 3$ $f_{\text{tentative}}(G) = 3 + 0 = 3$
Since
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef active fill:#fff2cc,stroke:#d6b656,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
classDef goal fill:#d5e8d4,stroke:#82b366,stroke-width:2px;
S["S (g=0, h=10, f=10)"]:::expanded
A["A (g=5, h=3, f=8)"]:::expanded
B["B (g=1, h=8, f=9)"]:::active
C["C (g=11, h=2, f=13)"]:::frontier
G["G (g=3, h=0, f=3)"]:::frontier
S -- "c=5" --> A
S -- "c=1" --> B
A -- "c=6" --> C
A -- "c=10" --> G
B -- "c=2" --> G
-
Open List:
$[G(f=3), C(f=13)]$ -
Closed List:
${S, A, B}$
Node
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
classDef goal fill:#d5e8d4,stroke:#82b366,stroke-width:2px;
S["S (g=0, h=10, f=10)"]:::expanded
A["A (g=5, h=3, f=8)"]:::expanded
B["B (g=1, h=8, f=9)"]:::expanded
C["C (g=11, h=2, f=13)"]:::frontier
G["G (g=3, h=0, f=3)"]:::goal
S -- "c=5" --> A
S -- "c=1" --> B
A -- "c=6" --> C
A -- "c=10" --> G
B -- "c=2" --> G
-
Returned Optimal Path:
$S \to B \to G$ -
Total Optimal Cost:
$g(G) = 3$
-
Greedy Best-First Search Comparison: GBFS selected path
$S \to A \to G$ with cost 15 because it ignored$g(n)$ and chased$h(A) = 3$ . In contrast,$A^*$ initially expanded$A$ because$f(A) = 8$ , but because$g(A) = 5$ was accumulated,$f(G_{\text{via } A}) = 15$ proved unpromising. This allowed$f(B) = 9$ to be selected next, discovering the true optimal path cost$g(G) = 3$ . -
Uniform-Cost Search Comparison: UCS explores strictly in order of
$g(n)$ , expanding nodes in expanding concentric circles of cost.$A^*$ uses$h(n)$ to focus expansions toward$G$ , reaching the goal while expanding far fewer total nodes than UCS.
This lower bound
A heuristic
where
If
Let
Let
Since
In Graph Search, state duplicates are tracked via the Closed List. Admissibility alone is insufficient to prevent reopening nodes in Graph Search unless path costs are monotonic.
A heuristic
We prove that consistency forces the evaluation function
Since
Because
To evaluate
-
Start State (
$X$ ): Located in the upper-left corner$(0, 0)$ . -
Goal State (
$X$ ): Located in the lower-right corner$(19, 19)$ . - Obstacles: Wall blocks requiring navigation around non-direct pathways.
-
Heuristic Function: Manhattan Distance
$h(n) = |x_n - x_{\text{goal}}| + |y_n - y_{\text{goal}}|$ (which is admissible and consistent for 4-connected grid movement).
The lecture visualizes node expansions using a heat map where darker colors represent early expansions near the Start node and lighter colors represent later expansions near the Goal node:
-
Node Expansion Behavior: Early dark-colored expansions radiate outward from
$(0, 0)$ . As the search encounters obstacles, the frontier widens horizontally across the grid as alternative paths are evaluated. - Final Solution Trajectory: Represented by small white dots proceeding vertically down the left edge, cutting horizontally across the obstacle gap, and proceeding vertically to the Goal.
-
Quantitative Results:
- Path Length: 39 nodes in the final optimal path.
- Frontier Node Count: 213 total nodes added to the Open List in memory.
In a head-to-head empirical comparison on a modified obstacle grid of the same dimensions:
| Metric |
|
Greedy Best-First Search |
|---|---|---|
| Path Length (Solution Quality) | 39 nodes (Optimal) | 57 nodes (Suboptimal) |
| Expanded Node Count | 151 nodes | 158 nodes |
| Optimality Guarantee | Guaranteed via Admissible/Consistent |
None |
| Obstacle Handling | Efficiently redirects via accumulated |
Easily trapped in obstacle pockets |
This empirical case study demonstrates that Greedy Best-First Search not only found a path that was 46% longer than the optimal path found by
Despite its theoretical elegance,
-
Memory Usage:
$A^*$ must retain every generated node in memory within either the Open List or the Closed List to maintain search order and prevent duplicate expansions. -
Space Complexity:
$O(b^d)$ , where$b$ is the effective branching factor and$d$ is the solution depth. -
Practical Failure Mode: In large state spaces (e.g.,
$100 \times 100$ routing grids, 15-puzzle, 3D robotic motion planning),$A^*$ exhausts available system RAM long before finding a solution, generating millions of unexpanded frontier nodes that take up memory without contributing to the final path.
This memory wall motivates advanced
While
Iterative Deepening
Unlike standard Iterative Deepening Search (IDS)—which increments search limits strictly by depth levels—
The core operational loop of
-
Initial Threshold Setting: Set the initial
$f$ -cost threshold$Threshold_0$ equal to$f(S) = g(S) + h(S) = h(S)$ , where$S$ is the start state. -
Recursive Depth-First Traversal: Perform a recursive DFS starting from
$S$ . For each visited node$n$ :- Calculate
$f(n) = g(n) + h(n)$ . -
Threshold Check: If
$f(n) > Threshold$ , prune the branch immediately. Do not expand$n$ further during the current iteration. Record$f(n)$ to help compute the cutoff threshold for the subsequent pass. -
Goal Test: If
$n$ is a goal state and$f(n) \le Threshold$ , terminate the search and return the optimal solution path. -
Successor Expansion: If
$f(n) \le Threshold$ , recursively explore each valid successor$n'$ of$n$ .
- Calculate
-
Threshold Update Protocol: If an iteration finishes without locating a goal state, set the new threshold
$Threshold_{next}$ to the minimum$f$ -value among all nodes pruned (i.e., nodes whose$f$ -cost exceeded the previous threshold) during that iteration:
-
Iterative Progression: Repeat the depth-first search with
$Threshold_{next}$ .
Consider a state space tree with Start state
-
$S$ :$g(S) = 0$ ,$h(S) = 4 \implies f(S) = 4$ -
$A$ :$g(A) = 2$ ,$h(A) = 3 \implies f(A) = 5$ -
$B$ :$g(B) = 1$ ,$h(B) = 6 \implies f(B) = 7$ - Successors of
$A$ :-
$A_1$ :$g(A_1) = 4$ ,$h(A_1) = 1 \implies f(A_1) = 5$ -
$G$ :$g(G) = 6$ ,$h(G) = 0 \implies f(G) = 6$
-
We utilize the below visual color conventions across all execution diagrams:
- Active / Currently Expanded Node: Yellow
- Expanded Node: Light Blue
- Frontier Node: Orange
- Pruned Node (Threshold Exceeded): Light Red
- Goal Node: Green
The search begins at
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef pruned fill:#f8cecc,stroke:#b85450,stroke-width:2px;
S["S (f=4)"]:::expanded
A["A (f=5)"]:::pruned
B["B (f=7)"]:::pruned
S -- "g=2" --> A
S -- "g=1" --> B
-
Pruned Set
$f$ -values:${5, 7}$ -
New Threshold:
$Threshold_1 = \min(5, 7) = 5$
The search restarts from
-
$S$ ($f(S)=4 \le 5$ ) expands to$A$ and$B$ . - Node
$A$ ($f(A)=5 \le 5$ ) is explored. Node$B$ ($f(B)=7 > 5$ ) is pruned. - Node
$A$ generates$A_1$ ($f(A_1)=5 \le 5$ ) and$G$ ($f(G)=6$ ). -
$A_1$ is visited ($f(A_1)=5 \le 5$ ).$G$ exceeds the threshold ($f(G)=6 > 5$ ) and is pruned.
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef pruned fill:#f8cecc,stroke:#b85450,stroke-width:2px;
classDef active fill:#fff2cc,stroke:#d6b656,stroke-width:2px;
S["S (f=4)"]:::expanded
A["A (f=5)"]:::expanded
B["B (f=7)"]:::pruned
A1["A1 (f=5)"]:::active
G["G (f=6)"]:::pruned
S -- "g=2" --> A
S -- "g=1" --> B
A -- "g=2" --> A1
A -- "g=4" --> G
-
Pruned Set
$f$ -values:${7, 6}$ -
New Threshold:
$Threshold_2 = \min(7, 6) = 6$
The search restarts from
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef goal fill:#d5e8d4,stroke:#82b366,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
S["S (f=4)"]:::expanded
A["A (f=5)"]:::expanded
B["B (f=7)"]:::frontier
A1["A1 (f=5)"]:::expanded
G["G (f=6)"]:::goal
S -- "g=2" --> A
S -- "g=1" --> B
A -- "g=2" --> A1
A -- "g=4" --> G
-
Returned Optimal Path:
$S \to A \to G$ -
Final Path Cost:
$g(G) = 6$
-
Space Complexity:
$O(b \cdot d)$ , where$b$ is the maximum branching factor and$d$ is the search depth. Because$IDA^*$ operates via recursive depth-first traversal, memory consumption is restricted strictly to the current call stack, holding only the active branch and its immediate siblings. -
Optimality: Guaranteed, provided that the underlying heuristic function
$h(n)$ is admissible ($0 \le h(n) \le h^*(n) $ ) for tree search, or consistent for graph search. Because$IDA^*$ increases$f$ -thresholds strictly to the minimal over-threshold cost, it never skips the optimal path cost$C^*$ . -
Time Complexity & Overhead:
$O(b^d)$ in the worst case. While earlier iterations re-examine top-level nodes, the overhead is typically negligible in state spaces with high branching factors ($b \ge 2$ ), as the number of nodes at depth$d$ vastly outweighs the cumulative nodes generated across all prior depths. -
Limitation in Continuous/Real-Valued Costs: In domains where edge costs or heuristic estimates take unique real values (e.g., Euclidean distance), every expanded node may yield a slightly larger
$f$ -cost. Consequently,$IDA^*$ may only increase its threshold by tiny increments per iteration, expanding only one new node per pass and deteriorating time complexity to$O(N^2)$ , where$N$ is total node count.
In large-scale pathfinding, executing exact
Weighted
The evaluation function for Weighted
The weight parameter
-
Case
$w = 1$ : Reduces identically to standard$A^*$ search ($f(n) = g(n) + h(n) $ ) , providing absolute cost optimality. -
Case
$w > 1$ : Amplifies the heuristic contribution. The algorithm treats remaining distance estimates as$w$ times more significant than accumulated travel expenses$g(n)$ , forcing the priority queue to aggressively favor nodes closer to the destination. -
Case
$w \to \infty$ : As$w$ increases relative to$g(n)$ , the influence of$g(n)$ becomes negligible, causing Weighted$A^*$ to degenerate into Greedy Best-First Search ($f(n) \approx w \cdot h(n) $ ).
To illustrate how increasing
-
Path 1 (Optimal Path):
$S \to A \to G$ $c(S, A) = 2, h(A) = 4 \implies g(A) = 2$ $c(A, G) = 4, h(G) = 0 \implies g(G) = 6$
-
Path 2 (Suboptimal Path with Low Initial Heuristic):
$S \to B \to G$ $c(S, B) = 5, h(B) = 1 \implies g(B) = 5$ $c(B, G) = 3, h(G) = 0 \implies g(G) = 8$
Let us evaluate the node expansion footprints across different weight settings
$f(A) = g(A) + 1.0 \cdot h(A) = 2 + 4 = 6$ $f(B) = g(B) + 1.0 \cdot h(B) = 5 + 1 = 6$ - Node
$A$ is selected first (or tie-broken), leading to$G$ via Path 1 with cost$g(G) = 6$ . -
Nodes Expanded:
$S, A$ . Optimal path found:$S \to A \to G$ (Cost:$6$ ).
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
classDef goal fill:#d5e8d4,stroke:#82b366,stroke-width:2px;
S["S"]:::expanded
A["A"]:::expanded
B["B"]:::frontier
G["G"]:::goal
S -- "g=2" --> A
S -- "g=5" --> B
A -- "g=6" --> G
B -. "g=8" .-> G
$f_{1.5}(A) = g(A) + 1.5 \cdot h(A) = 2 + 1.5(4) = 8.0$ $f_{1.5}(B) = g(B) + 1.5 \cdot h(B) = 5 + 1.5(1) = 6.5$ - Node
$B$ is expanded first because$f_{1.5}(B) = 6.5 < f_{1.5}(A) = 8.0$ . - Node
$B$ generates$G$ with path cost$g(G) = 8$ .$f_{1.5}(G) = 8 + 0 = 8.0$ . - Since
$f_{1.5}(G) = 8.0 \le f_{1.5}(A) = 8.0$ , Goal$G$ is reached directly via Path 2. -
Nodes Expanded:
$S, B$ . Suboptimal path found:$S \to B \to G$ (Cost:$8$ ).
graph TD
classDef expanded fill:#dae8fc,stroke:#6c8ebf,stroke-width:2px;
classDef frontier fill:#ffe6cc,stroke:#d79b00,stroke-width:2px;
classDef goal fill:#d5e8d4,stroke:#82b366,stroke-width:2px;
S["S"]:::expanded
A["A"]:::frontier
B["B"]:::expanded
G["G"]:::goal
S -. "g=2" .-> A
S -- "g=5" --> B
A -. "g=6" .-> G
B -- "g=8" --> G
$f_{2.5}(A) = 2 + 2.5(4) = 12.0$ $f_{2.5}(B) = 5 + 2.5(1) = 7.5$ - Search aggressively pushes down
$B$ 's branch, reaching goal$G$ with minimal state exploration. -
Suboptimality Bound Verification: Returned path cost
$C = 8$ . Optimal path cost$C^* = 6$ . The solution satisfies$C = 8 \le w \cdot C^* = 2.5 \cdot 6 = 15$ .
4.2.4. Theoretical Properties: Completeness, Bounded Suboptimality ($C \le w \cdot C^* $ ), and Speedup
-
Completeness: Guaranteed on finite graphs (with positive edge costs
$c(n, n') \ge \epsilon > 0$ ). -
Bounded Suboptimality Theorem: Let
$C^*$ denote the optimal path cost from start to goal, and let$C$ denote the cost of the path returned by Weighted$A^*$ using an admissible heuristic$h(n)$ . The solution cost$C$ is strictly upper-bounded by:
-
Computational Speedup: By increasing
$w$ , Weighted$A^*$ prunes large portions of the search space that standard$A^*$ would otherwise explore to prove optimality. In empirical search domains, values of$w \in [1.2, 2.0]$ often yield order-of-magnitude reductions in node expansions while returning paths with$5\%$ to$10\%$ cost increase comparing to the optimal cost.
The table below synthesizes the structural, computational, and theoretical properties of all informed search strategies covered in Module 3a:
| Search Strategy | Evaluation Function |
Space Complexity | Time Complexity | Complete? | Optimal? | Primary Use Case / Characteristics |
|---|---|---|---|---|---|---|
| Greedy Best-First Search | Tree: No Graph: Yes |
No | Extremely fast execution when heuristic is accurate; vulnerable to local optima and severe suboptimality. | |||
| Yes | Yes (Admissible/Consistent |
Benchmark optimal search; severely constrained by exponential memory consumption in large state spaces. | ||||
| Iterative Deepening |
|
Yes | Yes (Admissible/Consistent |
Memory-constrained optimal search; eliminates |
||
| Weighted |
|
|
Yes | Bounded Suboptimal ( |
High-performance search balancing speed and solution quality; drastically reduces node expansions in massive domains. |