1. Introduction to Informed Search

1.1. Fundamentals of Informed Search & Heuristic Functions

1.1.1. Uninformed vs. Informed Search Paradigms

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.

1. 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.

2. 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.

1.1.2. Definition and Role of Heuristic Function $h(n)$

A heuristic function, denoted as $h(n)$, is a domain-specific mapping that estimates the cost of the cheapest path from state node $n$ to a goal state $n_{\text{goal}}$:

$$h(n): S \to \mathbb{R}_{\ge 0}$$

where $S$ represents the set of all valid state space nodes.

Key operational characteristics of $h(n)$ include:

• 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).

1.1.3. Concrete Domain Examples (Route Planning, Chess, 8-Puzzle)

The formulation of $h(n)$ depends directly on the physical or logical structure of the problem domain:

1. 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}}|$$

2. 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.

3. 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)$$

1.2. Evaluation Functions and Mathematical Properties of Heuristics

1.2.1. Structure of Evaluation Function $f(n) = g(n) + h(n)$

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 $f(n)$.

The general structure of $f(n)$ combines past performance with future predictions:

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

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).

1.2.2. Goal State Evaluation ($h(\text{goal}) = 0$) and Non-Negativity ($h(n) \ge 0$)

To preserve sound search mechanics and mathematical guarantees, any heuristic function $h(n)$ must adhere to two fundamental baseline constraints:

1. 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$.

2. 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.

1.2.3. Admissibility Property ($h(n) \le h^*(n) $)

A heuristic function $h(n)$ is defined as admissible if it never overestimates the true minimal cost required to reach a goal state from node $n$.

1. 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)$$

2. 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.

1.2.4. Consistency (Monotonicity) Property & Triangle Inequality ($h(n) \le c(n, n') + h(n') $)

A heuristic function $h(n)$ is defined as consistent (or monotone) if its estimates satisfy a local form of the triangle inequality across every edge in the state space graph.

1. 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')$$

2. 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') $).

3. 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:

$$\begin{alignat*}{4} && f(n') &= g(n') + h(n') && \text{By definition of evaluation function } f(n') && \ && &= g(n) + c(n, n') + h(n') && \because \text{Accumulated path cost } g(n') = g(n) + c(n, n') && \ && &\ge g(n) + h(n) && \because \text{Consistency condition } c(n, n') + h(n') \ge h(n) && \ && &= f(n) && \text{By definition of evaluation function } f(n) && \ \end{alignat*}$$

• Algebraic Conclusion: $f(n') \ge f(n)$ holds for all successor steps.

4. 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.

2. Greedy Best-First Search

2.1. Algorithm Mechanics and Evaluation Strategy

2.1.1. Objective Function $f(n) = h(n)$

Greedy Best-First Search is an informed search strategy that evaluates nodes using solely a heuristic estimate of the remaining cost from node $n$ to the closest goal state. Its evaluation function $f(n)$ is defined as:

$$f(n) = h(n)$$

where $h(n): S \to \mathbb{R}_{\ge 0}$ estimates the cost of the optimal path from node $n$ to a goal.

Unlike Uniform-Cost Search, which minimizes accumulated past path cost $g(n)$, Greedy Best-First Search sets $g(n) \equiv 0$ within its selection metric. The algorithm operates under a "myopic" or "greedy" policy: at every expansion step, it selects the node that appears closest to the goal state, regardless of the effort or path cost required to reach node $n$ from the start state.

2.1.2. Frontier Management and Pure Heuristic Selection

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:

1. Selection: Pop node $n$ with the minimal $h(n)$ from the Open List.
2. Goal Test: Evaluate whether $n$ satisfies the goal condition ($h(n) = 0$). If true, terminate and reconstruct the solution trajectory.
3. Exploration: Insert $n$ into the Closed List.
4. 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).

2.2. Step-by-Step Simple Graph Execution Trace (Mermaid Diagrams)

2.2.1. Standard Node Color Scheme Legend

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

2.2.2. Step-by-Step Traversal Trace on a Simplified State Graph

Consider a search graph with Start state $S$, intermediate nodes $A, B, C$, and Goal state $G$. The heuristic values $h(n)$ and actual edge costs $c(n, n')$ are specified as follows:

• $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$

Step 0: Initialization

Node $S$ is expanded (Active). Successors $A$ and $B$ are generated and inserted into the Open List (Frontier).

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}$

Step 1: Expansion of Node A

Node $A$ is selected from the Open List because $h(A) = 3 < h(B) = 8$. $A$ becomes Active, and its parent $S$ transitions to Expanded (Closed List). Successors $C$ and $G$ are added to the Open List.

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}$

Step 2: Goal Selection and Termination

Node $G$ is selected from the Open List because $h(G) = 0$. $G$ is identified as the goal state, terminating the search.

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$

2.2.3. Failure Analysis: Suboptimal Trajectories & Local Optima Traps

The trace above highlights the core vulnerability of Greedy Best-First Search:

1. 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$.
2. 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.
3. 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.

2.3. Theoretical Properties and Performance

2.3.1. Completeness in Finite Search Spaces

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.

2.3.2. Time and Space Complexity ($O(b^m)$ Worst-Case vs. Best-Case Linear)

Let $b$ denote the maximum branching factor and $m$ denote the maximum depth of the state space:

• 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.

2.3.3. Sensitivity to Heuristic Quality and Relation to Beam Search

• 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.

3. A* Search Algorithm

3.1. Core Framework and Operational Architecture

3.1.1. Combined Evaluation Function $f(n) = g(n) + h(n)$

The $A^*$ Search algorithm is an informed pathfinding strategy designed to achieve both completeness and cost-optimality. It achieves this by combining the historical path cost $g(n)$ used in Uniform-Cost Search with the predictive heuristic estimate $h(n)$ used in Greedy Best-First Search.

The overall evaluation function $f(n)$ assigns a total estimated cost to any candidate node $n$:

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

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 $g(n)$, $A^*$ penalizes long or expensive trajectories, preventing the algorithm from being tricked by misleadingly low $h(n)$ values along high-cost paths. By incorporating $h(n)$, $A^*$ directs search progress toward the goal state rather than expanding nodes uniformly in all directions.

3.1.2. Open List (Priority Queue) and Closed List Management

$A^*$ maintains two core data structures during execution:

• 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.

3.1.3. Node Expansion and Successor Generation Protocol

The operational execution loop of $A^*$ Graph Search proceeds through the following steps:

1. Selection: Extract the node $n$ with the minimal $f(n)$ value from the Open List.
2. 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.
3. Exploration: Insert node $n$ into the Closed List.
4. 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.

3.2. Step-by-Step Simple Graph Execution Trace (Mermaid Diagrams)

3.2.1. Step-by-Step $A^*$ Expansion Trace on a Simplified State Graph

To directly compare $A^*$ with Greedy Best-First Search, consider the identical state space graph from Section 2 with Start state $S$, intermediate nodes $A, B, C$, and Goal state $G$. The heuristic estimates $h(n)$ and edge costs $c(n, n')$ are:

• $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$

Step 0: Initialization

Node $S$ is expanded (Active). Successors $A$ and $B$ are inserted into the Open List.

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}$

Step 1: Expansion of Node A

Node $A$ is popped from the Open List because $f(A) = 8 < f(B) = 9$. $A$ becomes Active, $S$ transitions to Expanded. Successors $C$ and $G$ (via path $S \to A \to G$) are evaluated and placed in the Open List.

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}$

Step 2: Expansion of Node B & Key Path Update for Goal Node G

Node $B$ is popped from the Open List because $f(B) = 9 < f(C) = 13$. $B$ becomes Active. $B$'s successor $G$ is evaluated via path $S \to B \to G$:

• $g_{\text{tentative}}(G) = g(B) + c(B, G) = 1 + 2 = 3$
• $f_{\text{tentative}}(G) = 3 + 0 = 3$

Since $g_{\text{tentative}}(G) = 3 < g_{\text{existing}}(G) = 15$, $A^*$ updates node $G$'s parent pointer to $B$, sets its $g(G) = 3, f(G) = 3$, and updates its position in the priority queue.

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}$

Step 3: Selection of Goal Node G and Termination

Node $G$ is popped from the Open List because $f(G) = 3 < f(C) = 13$. The goal test succeeds, and $A^*$ terminates.

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$

3.2.2. Comparison with Greedy Selection & Uninformed Pathing

• 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.

3.3. Theoretical Foundations and Optimality Guarantees

3.3.1. Completeness Property

$A^*$ Search is complete on finite graphs provided that all step costs are strictly positive and bounded away from zero:

$$c(n, n') \ge \epsilon > 0$$

This lower bound $\epsilon$ ensures that infinite sequences of zero-cost actions cannot cause the search to loop endlessly without increasing $g(n)$.

3.3.2. Tree Search Optimality under Admissible Heuristics

A heuristic $h(n)$ is admissible if it never overestimates the true minimal cost to reach the goal state $g_{\text{goal}}$:

$$0 \le h(n) \le h^*(n) \quad \forall n \in S$$

where $h^*(n)$ denotes the true optimal path cost from node $n$ to $g_{\text{goal}}$.

Theorem

If $h(n)$ is admissible, $A^*$ Tree Search is guaranteed to return an optimal solution path.

Mathematical Derivation of Optimality

Let $C^*$ denote the cost of the optimal solution path to goal $G^*$. Suppose a suboptimal goal node $G_2$ exists with path cost $g(G_2) > C^*$. Assume $A^*$ is about to select $G_2$ from the Open List.

Let $n$ be an unexpanded node on the optimal path to $G^*$. We prove that $f(n) < f(G_2)$, ensuring $n$ will always be expanded before $G_2$:

$$\begin{alignat*}{4} && f(G_2) &= g(G_2) + h(G_2) && \text{By definition of } f(n) \ && &= g(G_2) && \because h(G_2) = 0 \text{ for goal states} \ && &> C^* && \text{By assumption that } G_2 \text{ is suboptimal} \ && &= g(G^*) && \text{Since } C^* \text{ is the optimal path cost} \ && &\ge g(n) + h^*(n) && \text{Since } n \text{ lies on the optimal path to } G^* \ && &\ge g(n) + h(n) && \because h(n) \le h^*(n) \text{ (Admissibility)} \ && &= f(n) && \text{By definition of } f(n) \end{alignat*}$$

Since $f(n) \le C^* < f(G_2)$, the node $n$ on the optimal path will always have a strictly smaller evaluation cost than any suboptimal goal $G_2$. Therefore, $A^*$ can never select a suboptimal goal state $G_2$ for expansion, guaranteeing optimality.

3.3.3. Graph Search Optimality under Consistent Heuristics (Elimination of Node Reopening)

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 $h(n)$ is consistent (or monotonic) if, for every node $n$ and every successor $n'$ generated by action $a$ with edge cost $c(n, n')$, it satisfies the triangle inequality:

$$h(n) \le c(n, n') + h(n')$$

Monotonicity Derivation ($f(n)$ is Non-Decreasing)

We prove that consistency forces the evaluation function $f(n)$ to be non-decreasing along any search path:

$$\begin{alignat*}{4} && f(n') &= g(n') + h(n') && \text{By definition of } f(n') \ && &= g(n) + c(n, n') + h(n') && \because g(n') = g(n) + c(n, n') \ && &\ge g(n) + h(n) && \because c(n, n') + h(n') \ge h(n) \text{ (Consistency)} \ && &= f(n) && \text{By definition of } f(n) \end{alignat*}$$

Since $f(n') \ge f(n)$, the sequence of $f$-values along any path expanded by $A^*$ is monotonically non-decreasing.

Elimination of Node Reopening

Because $f(n)$ is non-decreasing, when $A^*$ selects a node $n$ for expansion and places it in the Closed List, it has reached $n$ via the strict optimal path $g^*(n)$. No subsequent path can reach $n$ with a lower $g(n)$ value. Thus, consistent heuristics guarantee that nodes in the Closed List never need to be reopened, ensuring maximal computational efficiency.

3.4. Grid Pathfinding Empirical Case Study & Performance

3.4.1. 20x20 Grid Environment: Start/Goal Locations, Obstacles, and Manhattan Distance

To evaluate $A^*$ under realistic pathfinding conditions, the lecture analyzes a $20 \times 20$ grid environment with obstacles:

• 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).

3.4.2. Expansion Order Heat Map Analysis (213 Frontier Nodes vs. 39 Path Length)

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.

3.4.3. Quantitative Performance Comparison: $A^*$ vs. Greedy Best-First Search

In a head-to-head empirical comparison on a modified obstacle grid of the same dimensions:

Metric	$A^*$ Search	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 $h(n)$	None
Obstacle Handling	Efficiently redirects via accumulated $g(n)$	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 $A^*$, but it also required more total node expansions (158 vs. 151) because its myopic focus got stuck navigating obstacles.

3.4.4. Exponential Memory Bottleneck of $A^*$ in Large State Spaces

Despite its theoretical elegance, $A^*$ suffers from a severe practical limitation: exponential memory growth.

• 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 $A^*$ variants such as Iterative Deepening $A^*$ ($IDA^*$) and Weighted $A^*$, which manage memory bounds and trading speed for bounded suboptimality.

4. Memory-Bounded and Variant A* Algorithms

4.1. Iterative Deepening A* (IDA*)

4.1.1. Architectural Motivation: Resolving A*'s Memory Crisis

While $A^*$ search guarantees optimal paths under admissible heuristics, its practical applicability is severely constrained by its spatial requirement. $A^*$ stores every generated state in memory within either the Open List or the Closed List, resulting in an exponential space complexity of $O(b^d)$, where $b$ is the branching factor and $d$ is the goal depth. In complex real-world state spaces—such as high-dimensional automated planning, 15-puzzle configurations, or large-scale robotics—$A^*$ exhausts available RAM long before completing its search trajectory.

Iterative Deepening $A^*$ ($IDA^*$) resolves this spatial bottleneck by replacing the priority queue (Open List) of $A^*$ with a series of depth-first search (DFS) iterations. By leveraging the linear memory profile of depth-first traversal while using $f$-cost bounds to control search depth, $IDA^*$ achieves optimal search behavior within a linear space complexity of $O(b \cdot d)$.

4.1.2. f-Cost Thresholding Mechanics and Recursive Depth-First Exploration

Unlike standard Iterative Deepening Search (IDS)—which increments search limits strictly by depth levels— $IDA^*$ cuts off exploration using a threshold based on the total estimated cost $f(n) = g(n) + h(n)$.

The core operational loop of $IDA^*$ proceeds as follows:

1. 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.
2. 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$.
3. 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:

$$Threshold_{next} = \min\limits_{n \in \text{Pruned}} f(n)$$

4. Iterative Progression: Repeat the depth-first search with $Threshold_{next}$.

4.1.3. Step-by-Step Simple Tree Execution Trace (Diagrams for f-bound Progression)

Consider a state space tree with Start state $S$, child states $A$ and $B$, and goal state $G$. The path costs $g(n)$, heuristic estimates $h(n)$, and total costs $f(n) = g(n) + h(n)$ are defined as follows:

• $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

Iteration 1: Initial Cutoff $Threshold_0 = f(S) = 4$

The search begins at $S$ ($f(S)=4 \le 4$). $S$ generates child nodes $A$ ($f(A)=5$) and $B$ ($f(B)=7$). Because both $f(A) > 4$ and $f(B) > 4$, both branches exceed the current threshold and are pruned immediately.

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$

Iteration 2: Cutoff $Threshold_1 = 5$

The search restarts from $S$.

1. $S$ ($f(S)=4 \le 5$) expands to $A$ and $B$.
2. Node $A$ ($f(A)=5 \le 5$) is explored. Node $B$ ($f(B)=7 > 5$) is pruned.
3. Node $A$ generates $A_1$ ($f(A_1)=5 \le 5$) and $G$ ($f(G)=6$).
4. $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$

Iteration 3: Cutoff $Threshold_2 = 6$

The search restarts from $S$ with $Threshold_2 = 6$. The recursive path $S \to A \to G$ is explored. Node $G$ has $f(G) = 6 \le 6$. $G$ satisfies the goal condition ($h(G)=0$), and the search terminates successfully, returning path $S \to A \to G$.

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$

4.1.4. Space Complexity ($O(b \cdot d)$ Linear Stack) and Time/Optimality Guarantees

• 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.

4.2. Weighted A* Search

4.2.1. Architectural Motivation: Accelerating Search via Bounded Suboptimality

In large-scale pathfinding, executing exact $A^*$ search until absolute optimality is established often requires expanding millions of state nodes, consuming prohibitive time and memory. In many real-world applications—such as video game pathfinding, automated driving route generation, and high-degree-of-freedom robotic motion planning—a user prefers a near-optimal route delivered in milliseconds rather than a strictly optimal route that takes several minutes to compute.

Weighted $A^*$ addresses this operational trade-off by introducing a scaling weight factor $w \ge 1$ to the heuristic function. By intentionally biasing the evaluation function toward the goal, Weighted $A^*$ accelerates search performance while maintaining a mathematically guaranteed bound on solution quality.

4.2.2. Modified Objective Function $f(n) = g(n) + w \cdot h(n)$ ($w > 1$ )

The evaluation function for Weighted $A^*$ is formulated as:

$$f_w(n) = g(n) + w \cdot h(n), \quad \text{where } w \ge 1$$

The weight parameter $w$ alters the search behavior along a continuum:

• 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) $).

4.2.3. Step-by-Step Simple Graph Execution Trace (Footprint Comparison across $w = 1, 2, 2.5, 3$)

To illustrate how increasing $w$ collapses the search footprint (the total number of expanded nodes), consider a graph where Start state $S$ branches into two distinct paths to Goal $G$:

• 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 $w$:

Footprint Comparison across Weights

1. Standard $A^*$ ($w = 1.0$)

• $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

2. Moderate Weight ($w = 1.5$)

• $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

3. Heavy Weight ($w = 2.5$)

• $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:

$$C \le w \cdot C^*$$

Derivation of the Suboptimality Bound

$$ \begin{alignat*}{4} && C &= f_w(G) && \text{Upon goal selection, } h(G) = 0 \implies f_w(G) = g(G) = C \ && &\le f_w(n) && \text{For any node } n \text{ on the optimal path residing on the Open List} \ && &= g(n) + w \cdot h(n) && \text{By definition of } f_w(n) \ && &\le w \cdot g(n) + w \cdot h(n) && \because w \ge 1 \implies g(n) \le w \cdot g(n) \text{ for } g(n) \ge 0 \ && &= w \cdot (g(n) + h(n)) && \text{Factor out } w \ && &\le w \cdot (g(n) + h^*(n)) && \because h(n) \le h^*(n) \text{ (Admissibility)} \ && &= w \cdot C^* && \because g(n) + h^*(n) = C^* \text{ along the optimal path} \end{alignat*} $$

• 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.

4.3. Comprehensive Comparative Analysis

The table below synthesizes the structural, computational, and theoretical properties of all informed search strategies covered in Module 3a:

Search Strategy	Evaluation Function $f(n)$	Space Complexity	Time Complexity	Complete?	Optimal?	Primary Use Case / Characteristics
Greedy Best-First Search	$f(n) = h(n)$	$O(b^m)$	$O(b^m)$	Tree: NoGraph: Yes	No	Extremely fast execution when heuristic is accurate; vulnerable to local optima and severe suboptimality.
$A^*$ Search	$f(n) = g(n) + h(n)$	$O(b^d)$	$O(b^d)$	Yes	Yes (Admissible/Consistent $h$)	Benchmark optimal search; severely constrained by exponential memory consumption in large state spaces.
Iterative Deepening $A^*$ ($IDA^*$)	$f(n) = g(n) + h(n)$ with $f$-threshold	$O(b \cdot d)$	$O(b^d)$	Yes	Yes (Admissible/Consistent $h$)	Memory-constrained optimal search; eliminates $A^*$'s Open/Closed list RAM overhead via linear depth-first recursion.
Weighted $A^*$ Search	$f(n) = g(n) + w \cdot h(n)$, $w > 1$	$O(b^d)$	$O(b^d)$ (Much smaller constant)	Yes	Bounded Suboptimal ($C \le w \cdot C^*$)	High-performance search balancing speed and solution quality; drastically reduces node expansions in massive domains.