Module 2b ‐ Uninformed Search Demo and Comparison, BFS, DFS, Uniform Cost - hellochishing/Intelligent-Agents-and-Search-Algorithms GitHub Wiki

1. Introduction to Uninformed Search Algorithms

1.1. Definition of Uninformed (Blind) Search

In artificial intelligence, a search algorithm is a systematic method by which an agent explores potential sequences of actions to transition from an initial state to a desired goal state.

An uninformed search algorithm—frequently referred to as a blind search—is defined by the fundamental constraint that the agent possesses no domain-specific knowledge or heuristic estimate regarding how close a given state is to the goal, or whether a specific action is superior to another. The agent operates exclusively with the explicit problem formulation.

Key characteristics include:

  • Domain Ignorance: The algorithm cannot evaluate the remaining distance or remaining cost to the goal state from an intermediate node.
  • Systematic Exploration: Because decisions cannot be guided by domain heuristics, the agent must explore the state space systematically according to a fixed, algorithmic strategy (e.g., level-by-level or branch-by-branch).

1.2. Problem Formulation and State Space Exploration

To apply search algorithms, an AI problem must be formally defined. A classical search problem formulation consists of four core elements:

  1. Initial State (Start State): The initial configuration or starting condition of the agent, denoted mathematically as $s_0 \in S$, where $S$ represents the set of all possible states (the state space).
  2. Action Set: A function $\text{Actions}(s)$ that returns the set of executable actions available to the agent in a given state $s$. Transitioning via an action $a \in \text{Actions}(s)$ yields a successor state $s' = \text{Result}(s, a)$.
  3. Goal Test: A deterministic function or condition $\text{Goal-Test}(s) \to {\text{True}, \text{False}}$ that checks whether a candidate state $s$ satisfies the target goal criteria.
  4. Path Cost: A numerical function $c(s, a, s')$ assigning a step cost to taking action $a$ from state $s$ to state $s'$. The total path cost $g(n)$ of a node $n$ is the cumulative sum of step costs from the initial state $s_0$ to $n$:

$$g(n) = \sum\limits_{i=1}^{k} c(s_{i-1}, a_i, s_i)$$

For instance, if the average step cost across $k$ steps is $\bar{c}$, the total path cost ratio relative to unit steps can be written using fractions as:

$$\text{Cost Ratio} = \dfrac{g(n)}{k}$$

1.3. Search Tree Representation and Visual Color-Coding Scheme

Search algorithms explore the state space by constructing an explicit search tree over the underlying state space graph.

1.3.1. States vs. Nodes

It is critical to distinguish between a state and a search node:

  • State: A physical or abstract configuration of the world (e.g., city location, puzzle configuration).
  • Node: A data structure forming part of the search tree. A node $n$ contains the state it represents, a pointer to its parent node, the action that generated it, the depth of the node, and the cumulative path cost $g(n)$.

1.3.2. Search Terminology: Frontier and Expanded Sets

  • Frontier (Open List): The set of all generated leaf nodes that are currently pending expansion.
  • Expanded Set (Explored / Closed List): The set of nodes that have already been selected and expanded (i.e., had their successor actions generated).

1.3.3. Visual Color-Coding Scheme in Lecture Demos

Throughout the lecture demonstrations for BFS, DFS, and UCS, nodes in the search tree are visually distinguished using a strict three-color convention:

  • Red (Active Node): Represents the node currently being popped from the frontier and actively expanded or evaluated by the search algorithm.
  • Blue (Expanded Nodes): Represents nodes that have completed expansion (all child nodes have been generated) and belong to the explored set.
  • Orange (Frontier Nodes): Represents newly generated child nodes that have been placed into the frontier data structure waiting to be expanded.

2. Breadth-First Search (BFS)

2.1. Mechanics and Queue (FIFO) Data Structure

Breadth-First Search (BFS) is an uninformed search strategy that systematically explores a search space by expanding the shallowest unexpanded node first before moving deeper into the search tree. Conceptually, BFS operates like a ripple spreading outward from the initial start state, sweeping across the state space level by level.

2.1.1. Core Operating Principle

The primary defining characteristic of BFS is its expansion order: all nodes at depth $d$ in the search tree are expanded before any nodes at depth $d+1$ are expanded. This uniform, level-by-level progression ensures that the search tree is explored comprehensively in concentric layers centered at the root node.

2.1.2. Queue (FIFO) Data Structure

To maintain a strict level-by-level exploration order, BFS implements the Frontier (also referred to as the fringe or open set) using a First-In, First-Out (FIFO) Queue data structure.

  1. Insertion (Enqueue): When a node is expanded, its generated child nodes are added (enqueued) to the back of the queue.
  2. Removal (Dequeue): The next node selected for expansion is always dequeued from the front of the queue.
  3. Behavioral Consequence: Because nodes generated at depth $d$ are added to the back of the queue, they are naturally processed after all previously enqueued nodes at depth $d$, and strictly before any child nodes at depth $d+1$ that are generated later.

2.2. Step-by-Step Level-by-Level Execution Demo

To build intuitive clarity on Breadth-First Search (BFS), we examine a simplified binary tree search problem with branching factor $b = 2$. The search space consists of root node $A$, intermediate nodes $B, C, D, E, F$, and target goal node $G$.

2.2.1. Visual Color-Coding Scheme

Following the lecture convention, nodes during search tree traversal are categorized using a visual color model:

  • Active Node (Red): The node currently dequeued from the front of the queue and undergoing expansion.
  • Expanded Set (Blue): Nodes that have already been dequeued and whose child successors have been generated.
  • Frontier Queue (Orange): Nodes that have been generated and are waiting in the First-In, First-Out (FIFO) queue.
  • Goal Node (Green): The designated target node.

2.2.2. Simplified Search Tree Representation

Below is the complete search space representation showing the traversal order $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7$ across tree levels:

graph TD
    classDef expanded fill:#66b2ff,stroke:#004080,stroke-width:2px,color:#ffffff;
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef goal fill:#2ecc71,stroke:#1e8449,stroke-width:2px,color:#ffffff;

    A[Node A - Step 1]:::expanded
    B[Node B - Step 2]:::expanded
    C[Node C - Step 3]:::expanded
    D[Node D - Step 4]:::frontier
    E[Node E - Step 5]:::frontier
    F[Node F - Step 6]:::frontier
    G[Goal Node G - Step 7]:::goal

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

2.2.3. Step-by-Step Trace and FIFO Queue Mechanics

BFS explores nodes strictly level-by-level using a First-In, First-Out (FIFO) Queue data structure. The detailed execution state at each step is traced below:

Step 1: Initialization (Level 0)

  • Active Node: Node $A$ (Dequeued)
  • Action: Goal test on $A$ fails. Expand $A$ and enqueue its child successors $B$ and $C$ to the back of the queue.
  • Frontier Queue (FIFO): $[B, C]$
  • Expanded Set: ${A}$
graph TD
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef unvisited fill:#ffffff,stroke:#333333,stroke-width:1px,color:#000000;

    A[Node A - Active]:::active
    B[Node B]:::frontier
    C[Node C]:::frontier
    D[Node D]:::unvisited
    E[Node E]:::unvisited
    F[Node F]:::unvisited
    G[Node G]:::unvisited

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

Step 2: Level 1 Left Expansion

  • Active Node: Node $B$ (Dequeued from front of FIFO queue $[B, C]$)
  • Action: Goal test on $B$ fails. Expand $B$ and enqueue children $D$ and $E$.
  • Frontier Queue (FIFO): $[C, D, E]$
  • Expanded Set: ${A, B}$
graph TD
    classDef expanded fill:#66b2ff,stroke:#004080,stroke-width:2px,color:#ffffff;
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef unvisited fill:#ffffff,stroke:#333333,stroke-width:1px,color:#000000;

    A[Node A]:::expanded
    B[Node B - Active]:::active
    C[Node C]:::frontier
    D[Node D]:::frontier
    E[Node E]:::frontier
    F[Node F]:::unvisited
    G[Node G]:::unvisited

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

Step 3: Level 1 Right Expansion

  • Active Node: Node $C$ (Dequeued from front of FIFO queue $[C, D, E]$)
  • Action: Goal test on $C$ fails. Expand $C$ and enqueue children $F$ and $G$.
  • Frontier Queue (FIFO): $[D, E, F, G]$
  • Expanded Set: ${A, B, C}$
graph TD
    classDef expanded fill:#66b2ff,stroke:#004080,stroke-width:2px,color:#ffffff;
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef goal fill:#2ecc71,stroke:#1e8449,stroke-width:2px,color:#ffffff;

    A[Node A]:::expanded
    B[Node B]:::expanded
    C[Node C - Active]:::active
    D[Node D]:::frontier
    E[Node E]:::frontier
    F[Node F]:::frontier
    G[Goal Node G]:::frontier

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

Step 4–6: Level 2 Left-to-Right Dequeuing

  • Step 4: Dequeue Node $D$, goal test fails, no children to enqueue. Queue becomes $[E, F, G]$.
  • Step 5: Dequeue Node $E$, goal test fails, no children to enqueue. Queue becomes $[F, G]$.
  • Step 6: Dequeue Node $F$, goal test fails, no children to enqueue. Queue becomes $[G]$.

Step 7: Goal Node Reach and Termination

  • Active Node: Node $G$ (Dequeued from front of FIFO queue $[G]$)
  • Action: Goal test on $G$ succeeds! Search halts immediately.
  • Optimal Solution Path: $A \rightarrow C \rightarrow G$
  • Path Cost: $g(G) = d(G) = 2$ transitions.

2.2.4. Summary Table of Search State Operations

Step Active Node (Dequeued) Goal Test Result Generated Successors Enqueued Frontier Queue State (FIFO) Expanded Set
0 - - $A$ $[A]$ $\emptyset$
1 $A$ Fail $B, C$ $[B, C]$ ${A}$
2 $B$ Fail $D, E$ $[C, D, E]$ ${A, B}$
3 $C$ Fail $F, G$ $[D, E, F, G]$ ${A, B, C}$
4 $D$ Fail None $[E, F, G]$ ${A, B, C, D}$
5 $E$ Fail None $[F, G]$ ${A, B, C, D, E}$
6 $F$ Fail None $[G]$ ${A, B, C, D, E, F}$
7 $G$ Success - - ${A, B, C, D, E, F, G}$

2.3. Theoretical Properties and Performance Evaluation

The performance of search algorithms is evaluated across four fundamental criteria: Completeness, Optimality, Time Complexity, and Space Complexity. Let $b$ represent the branching factor (maximum number of successors per node) and $d$ represent the depth of the shallowest goal node.

2.3.1. Completeness

BFS is Complete. If a solution exists at a finite depth $d$ and the branching factor $b$ is finite, BFS is guaranteed to find it. Because BFS explores every level exhaustively before descending deeper, it cannot get trapped indefinitely in an infinite path or deep non-goal branch.

2.3.2. Optimality

BFS is Optimal if and only if all step costs are equal (or non-decreasing functions of node depth, e.g., $c(s, a, s') = 1$ for all transitions).

  • Under uniform step costs, path cost is directly proportional to path depth: $g(n) = d(n)$.
  • Because BFS expands nodes in strictly non-decreasing order of depth, the first goal node encountered is guaranteed to be at the minimum possible depth $d$, and thus has the minimum total path cost.
  • If step costs vary arbitrarily (e.g., in weighted graphs), BFS is not optimal, as a deeper path with smaller step costs could have a lower total path cost than a shallower path with larger step costs.

2.3.3. Time Complexity

To determine the total number of nodes generated in the worst-case scenario, we sum the nodes generated at each level from depth level 0 up to depth level $d$:

$$ \begin{alignat*}{4} && N_{total} &= \sum\limits_{i=0}^{d} b^i && \ && &= b^0 + b^1 + b^2 + \dots + b^d && \text{Expand finite geometric series} \ && &= 1 + b + b^2 + \dots + b^d && \text{Simplify base term } b^0 = 1 \ && &= \dfrac{b^{d+1} - 1}{b - 1} && \text{Apply finite geometric series summation formula for } b > 1 \ && &= O(b^d) && \text{Extract dominant asymptotic term as } d \to \infty \end{alignat*} $$

If the goal test is applied when a node is expanded rather than when it is generated, the algorithm generates all nodes at depth $d+1$ before expanding the goal node at depth $d$, yielding a time complexity of $O(b^{d+1})$. Under the standard optimization where the goal test is applied upon node generation, the time complexity remains $O(b^d)$.

2.3.4. Space Complexity

Space complexity is the primary critical bottleneck for BFS. Because every generated node must be stored in memory within either the Frontier (FIFO Queue) or the Expanded Set, the memory footprint is proportional to the number of nodes stored at the deepest level searched.

  • At depth $d$, the frontier queue holds $O(b^d)$ nodes.
  • The expanded set contains all internal nodes up to depth $d-1$, totaling $\sum\limits_{i=0}^{d-1} b^i = \dfrac{b^d - 1}{b - 1} = O(b^d)$ nodes.

Combining both sets, the overall space complexity is:

$$ \begin{alignat*}{4} && S_{total} &= O(b^d) + O(b^{d-1}) && \ && &= O(b^d) && \text{Dominant memory footprint at depth } d \end{alignat*} $$

Mathematical Intuition for Space Bottleneck

In exponential search trees, the number of leaf nodes at level $d$ dwarfs the sum of all internal nodes at all previous levels combined. Specifically, for $b \ge 2$:

$$ \begin{alignat*}{4} && \sum\limits_{i=0}^{d-1} b^i &= \dfrac{b^d - 1}{b - 1} && \ && &\le b^d - 1 && \text{For all branching factors } b \ge 2 \end{alignat*} $$

This demonstrates that level $d$ contains more nodes than levels $0$ through $d-1$ combined. Consequently, BFS exhausts physical RAM memory long before it exhausts CPU computational processing time in real-world large-scale search problems.

3. Depth-First Search (DFS)

3.1. Mechanics and Stack (LIFO) Data Structure

Depth-First Search (DFS) is an uninformed search strategy that systematically explores a search space by pursuing a single path as deeply as possible before backtracking. Unlike Breadth-First Search (BFS), which expands nodes level-by-level in concentric ripples, DFS dives straight down to the deepest unexpanded node along a branch before retreating to explore alternative paths.

3.1.1. Core Operating Principle

The primary defining characteristic of DFS is its "deepest-first" expansion order: the node selected for expansion is always the deepest unexpanded node in the search tree. When the algorithm hits a dead end (a leaf node that is not the goal or a state with no unvisited successors), it backtracks up the tree to the nearest ancestor node that possesses unexplored child branches.

3.1.2. Stack (LIFO) Data Structure

To enforce a deepest-first expansion order, DFS manages its Frontier (also referred to as the open set or fringe) using a Last-In, First-Out (LIFO) Stack data structure.

  1. Insertion (Push): When a node is expanded, its generated child nodes are pushed onto the top of the stack.
  2. Removal (Pop): The next node selected for evaluation and expansion is popped from the top of the stack.
  3. Behavioral Consequence: Because newly generated child nodes are placed at the top of the stack, they are immediately popped and expanded before any older, shallower nodes waiting deeper down in the stack. This mechanics inherently forces the search to explore down a branch to its deepest leaf before returning to explore sibling branches.

3.2. Step-by-Step Branch-by-Branch Execution Demo and Backtracking

To illustrate the mechanics of DFS without unnecessary complexity, we utilize a simplified 3-level binary search tree with a branching factor of $b = 2$.

3.2.1. Simplified Search Space Overview

The search space consists of nodes $A$ through $G$:

  • Level 0 (Root): Node $A$
  • Level 1: Node $B$ (Left successor) and Node $C$ (Right successor)
  • Level 2: Nodes $D, E$ (children of $B$) and Nodes $F, G$ (children of $C$)
  • Goal State: Node $G$

When expanding a node, child nodes are pushed onto the stack in right-to-left order so that the left child sits at the top of the stack and is processed first (standard left-to-right DFS traversal).

3.2.2. Color-Coded Mermaid Visual Key

The dynamic search process is tracked using the standardized visual color-coding scheme:

  • Active Node (Red): — The node currently being evaluated and expanded.
  • Expanded Set (Blue): — Fully processed ancestor nodes whose children have been generated.
  • Frontier Stack (Orange): — Discovered nodes waiting inside the LIFO stack.
  • Goal Node (Green): — The target state.

3.2.3. Step-by-Step LIFO Execution and Backtracking Snapshots

Step 1: Initialization at Root Node A

The search begins at root $A$. $A$ is pushed onto the stack, popped as the Active Node (Red), evaluated against the goal test, and expanded to the Expanded Set (Blue). Its successors $C$ and $B$ are generated; $C$ is pushed first, followed by $B$, placing $B$ at the top of the LIFO stack.

graph TD
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef expanded fill:#66b2ff,stroke:#004080,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef goal fill:#2ecc71,stroke:#1e8449,stroke-width:3px,color:#ffffff;

    A[Node A]:::expanded
    B[Node B]:::frontier
    C[Node C]:::frontier
    D[Node D]
    E[Node E]
    F[Node F]
    G((Goal G)):::goal

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
  • Active Node: $A$
  • Frontier Stack (Top $\rightarrow$ Bottom): $[B, C]$
  • Expanded Set: ${A}$

Step 2: Diving Deep into Left Branch (Node B and Node D)

Node $B$ (top of stack) is popped as Active (Red), evaluated, and expanded to Blue. Its children $E$ and $D$ are generated and pushed onto the stack ($E$ first, then $D$). Next, $D$ sits at the top of the stack and is popped. $D$ is a leaf node with no children.

graph TD
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef expanded fill:#66b2ff,stroke:#004080,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef goal fill:#2ecc71,stroke:#1e8449,stroke-width:3px,color:#ffffff;

    A[Node A]:::expanded
    B[Node B]:::expanded
    C[Node C]:::frontier
    D[Node D]:::active
    E[Node E]:::frontier
    F[Node F]
    G((Goal G)):::goal

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
  • Active Node: $D$
  • Frontier Stack (Top $\rightarrow$ Bottom): $[E, C]$
  • Expanded Set: ${A, B, D}$

Step 3: Backtracking at Dead End D and Exploring Node E

Because node $D$ is a leaf node and not the goal, the algorithm hits a dead end along branch $A \rightarrow B \rightarrow D$. DFS automatically backtracks up to $B$ by popping the next deepest node from the stack, which is $E$. Node $E$ is evaluated and expanded. $E$ is also a leaf node with no successors.

graph TD
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef expanded fill:#66b2ff,stroke:#004080,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef goal fill:#2ecc71,stroke:#1e8449,stroke-width:3px,color:#ffffff;

    A[Node A]:::expanded
    B[Node B]:::expanded
    C[Node C]:::frontier
    D[Node D]:::expanded
    E[Node E]:::active
    F[Node F]
    G((Goal G)):::goal

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
  • Active Node: $E$
  • Frontier Stack (Top $\rightarrow$ Bottom): $[C]$
  • Expanded Set: ${A, B, D, E}$

Step 4: Backtracking to Root A and Exploring Right Branch (Node C and Node F)

Having exhausted all descendents of left branch $B$, DFS backtracks all the way up to root ancestor $A$ and pops node $C$ from the stack. Node $C$ is activated and expanded to Blue, pushing children $G$ and $F$ onto the stack ($G$ first, then $F$). Node $F$ (top of stack) is popped and evaluated.

graph TD
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef expanded fill:#66b2ff,stroke:#004080,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef goal fill:#2ecc71,stroke:#1e8449,stroke-width:3px,color:#ffffff;

    A[Node A]:::expanded
    B[Node B]:::expanded
    C[Node C]:::expanded
    D[Node D]:::expanded
    E[Node E]:::expanded
    F[Node F]:::active
    G((Goal G)):::frontier

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
  • Active Node: $F$
  • Frontier Stack (Top $\rightarrow$ Bottom): $[G]$
  • Expanded Set: ${A, B, D, E, C, F}$

Step 5: Backtracking to Node C and Goal Discovery at Node G

Node $F$ is a leaf node and not the goal. DFS backtracks to $C$ and pops $G$ from the top of the stack. Goal test on node $G$ evaluates to True. Search terminates successfully, returning path $A \rightarrow C \rightarrow G$.

graph TD
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef expanded fill:#66b2ff,stroke:#004080,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef goal fill:#2ecc71,stroke:#1e8449,stroke-width:3px,color:#ffffff;

    A[Node A]:::expanded
    B[Node B]:::expanded
    C[Node C]:::expanded
    D[Node D]:::expanded
    E[Node E]:::expanded
    F[Node F]:::expanded
    G((Goal G)):::goal

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
  • Active Node: $G$ (Goal Node)
  • Frontier Stack: $\emptyset$ (Empty)
  • Expanded Set: ${A, B, D, E, C, F, G}$

3.2.4. Summary Stack State Tracking Table

Step Active Node Goal Test LIFO Stack Push Operations LIFO Stack Contents (Top $\rightarrow$ Bottom) Expanded Set
0 $A$ False Push $C$, Push $B$ $[B, C]$ ${A}$
1 $B$ False Push $E$, Push $D$ $[D, E, C]$ ${A, B}$
2 $D$ False None (Leaf) $[E, C]$ ${A, B, D}$
3 $E$ False None (Leaf) $[C]$ ${A, B, D, E}$
4 $C$ False Push $G$, Push $F$ $[F, G]$ ${A, B, D, E, C}$
5 $F$ False None (Leaf) $[G]$ ${A, B, D, E, C, F}$
6 $G$ True None (Goal) $\emptyset$ ${A, B, D, E, C, F, G}$

3.3. Theoretical Properties and Performance Evaluation

The performance of Depth-First Search is analyzed across Completeness, Optimality, Time Complexity, and Space Complexity. Let $b$ denote the branching factor, $m$ denote the maximum depth of the state space (where $m \ge d$), and $d$ denote the depth of the shallowest goal node.

3.3.1. Completeness

DFS is Incomplete in general search spaces:

  • Infinite-Depth Spaces: In state spaces with infinite depth or infinite paths (e.g., recursive state generation without cyclic check), DFS can dive down an endless non-goal branch and never terminate or backtrack.
  • Graph Search vs. Tree Search: In graph spaces with loops/cycles (e.g., $A \rightarrow B \rightarrow A$), tree-search DFS will loop infinitely unless explicit visited-state checking is implemented.
  • Finite Spaces: DFS is complete only if the state space is finite AND graph search duplicate checking is enabled.

3.3.2. Optimality

DFS is Not Optimal:

  • DFS returns the first goal path it encounters during its deepest-first traversal.
  • If a goal node exists at a shallow depth (e.g., $d = 1$ on the right branch), but DFS dives deep into a long left branch containing another goal node at depth $m = 10$, DFS will return the deep, high-cost solution at depth 10 without ever discovering the shallower, optimal solution.
  • Even if all step costs are equal ($c = 1$), DFS does not guarantee finding the shortest path.

3.3.3. Time Complexity

In the worst-case scenario, DFS may explore every single node in the entire search tree up to the maximum tree depth $m$ before encountering the goal state (e.g., if the goal is located at the far-right leaf at depth $m$).

The total number of nodes generated across all levels up to maximum depth $m$ is calculated as:

$$\begin{alignat*}{4} && N_{total} &= \sum\limits_{i=0}^{m} b^i && \ && &= 1 + b + b^2 + \dots + b^m && \text{Expand finite geometric series up to max depth } m \ && &= \dfrac{b^{m+1} - 1}{b - 1} && \text{Apply finite geometric series formula for } b > 1 \ && &= O(b^m) && \text{Extract dominant asymptotic term as } m \to \infty \end{alignat*}$$

Key Comparison with BFS: While BFS time complexity is $O(b^d)$ (bounded by goal depth $d$), DFS time complexity is $O(b^m)$ (bounded by maximum state space depth $m$). If $m \gg d$, DFS can take substantially longer than BFS.

3.3.4. Space Complexity (Memory Efficiency)

Space complexity is the single greatest advantage of Depth-First Search over Breadth-First Search.

During search execution, the LIFO stack only needs to store the single active path from the root down to the current node, along with the unexpanded sibling nodes for each ancestor on that path.

  • At maximum depth $m$, the path contains $m$ ancestor nodes.
  • For each level along the path, at most $b-1$ unexpanded sibling nodes remain in the stack.
  • Total memory footprint required by the LIFO stack is:

$$\begin{alignat*}{4} && S_{total} &= b \cdot m + 1 && \ && &= O(b \cdot m) && \text{Linear memory requirement} \end{alignat*}$$

Mathematical Intuition for Memory Efficiency

Whereas BFS suffers from exponential space complexity $O(b^d)$ because it retains all generated nodes across an entire level in memory, DFS features linear space complexity $O(b \cdot m)$.

For example, in a search tree with branching factor $b = 10$ and depth $m = 10$:

  • BFS Space Requirement: $O(10^{10}) \approx 10,000,000,000$ nodes in memory simultaneously.
  • DFS Space Requirement: $O(10 \cdot 10) = 100$ nodes in memory simultaneously.

This drastic reduction in memory footprint makes DFS suitable for deep search spaces where storing the full frontier queue is physically impossible due to RAM constraints.

conflict resolution : I m middle management, top management want to implement a new policy that will substantially increase the work load of the front-line staff, and fornt-line staff think the new new policy not only increase their work load and has no added value to the company. what is the strategy to resolve ?

4. Uniform-Cost Search (UCS)

4.1. Mechanics and Priority Queue Data Structure

4.1.1. Core Operating Principle

Uniform-Cost Search (UCS) is an uninformed search algorithm that expands the node $n$ with the lowest path cost $g(n)$ first. While Breadth-First Search (BFS) measures path length strictly by the number of hops (edges), UCS accounts for arbitrary non-negative edge costs $c(n, a, n') \ge 0$. This ensures that search progression is guided strictly by cumulative path cost rather than graph depth.

4.1.2. Priority Queue Data Structure

To systematically expand nodes in order of non-decreasing path cost, UCS implements the Frontier using a Priority Queue ordered by $g(n)$:

  1. Path Cost Function $g(n)$: Represents the total cumulative cost from the start node $s_0$ to node $n$: $$g(n) = \sum\limits_{i=1}^{k} c(s_{i-1}, a_i, s_i)$$

  2. Insertion (Enqueue): When a node $n'$ is generated from expanding node $n$ via action $a$ with step cost $c(n, a, n')$, its path cost is calculated as: $$g(n') = g(n) + c(n, a, n')$$ The node $n'$ is inserted into the Priority Queue positioned according to $g(n')$.

  3. Removal (Dequeue/Pop): The node at the head of the Priority Queue—which is guaranteed to have the minimum $g(n)$ among all discovered unexpanded nodes—is selected for expansion.

  4. Redundant Path Handling: If a newly generated node already exists in the frontier with a higher path cost, the frontier entry is updated with the new lower-cost path.

4.2. Total Path Cost $g(n)$ and Step-by-Step Cost-Based Demo

4.2.1. Multi-Path Search Problem Setup

To illustrate how UCS guarantees finding the optimal path even when a shallower path exists, consider a search space with two competing routes from Start Node $S$ to Goal Node $G$:

  • Path 1 (Shallow / Direct, High Cost): $S \xrightarrow{c=5} A \xrightarrow{c=5} G$ (Total cost $g=10$, 2 edges).
  • Path 2 (Deeper, Low Cost): $S \xrightarrow{c=1} B \xrightarrow{c=2} C \xrightarrow{c=1} G$ (Total cost $g=4$, 3 edges).

While BFS would prematurely pick Path 1 because it takes fewer steps (2 edges vs 3 edges), UCS systematically explores Path 2 because its cumulative path cost is strictly smaller ($g=4 < 10$).

4.2.2. Visual Representation and Color Key

The search space and dynamic priority queue state are tracked using the standardized visual scheme:

  • 🔴 Active Node (Red): The node currently popped from the priority queue and being expanded.
  • 🔵 Expanded Set (Blue): Nodes already expa anded whose children have been generated.
  • 🟠 Frontier Priority Queue (Orange): Nodes stored in the priority queue ordered by $g(n)$.
  • 🟢 Goal Node (Green): The target state $G$.
graph TD
    classDef active fill:#ff6666,stroke:#990000,stroke-width:2px,color:#ffffff;
    classDef expanded fill:#66b2ff,stroke:#004080,stroke-width:2px,color:#ffffff;
    classDef frontier fill:#ffc266,stroke:#b36b00,stroke-width:2px,color:#000000;
    classDef goal fill:#2ecc71,stroke:#1e8449,stroke-width:2px,color:#ffffff;

    S((S: g=0)):::expanded
    A((A: g=5)):::frontier
    B((B: g=1)):::expanded
    C((C: g=3)):::active
    G((G: g=4)):::goal

    S -- c=5 --> A
    S -- c=1 --> B
    A -- c=5 --> G
    B -- c=2 --> C
    C -- c=1 --> G

4.2.3. Step-by-Step Priority Queue Trace

Step 1: Initialize at Start Node $S$

  • Pop Start Node $S$ ($g=0$) $\rightarrow$ Active (Red).
  • Goal test $S \neq G$. Move $S$ to Expanded Set (Blue).
  • Generate successors: $A$ ($g = 0 + 5 = 5$) and $B$ ($g = 0 + 1 = 1$).
  • Priority Queue: $[B(g=1), A(g=5)]$.

Step 2: Expand Node $B$ (Lowest Cost $g=1$)

  • Dequeue Node $B$ ($g=1$) $\rightarrow$ Active (Red).
  • Goal test $B \neq G$. Move $B$ to Expanded Set (Blue).
  • Generate successor: $C$ ($g = 1 + 2 = 3$).
  • Priority Queue: $[C(g=3), A(g=5)]$.

Step 3: Expand Node $C$ (Lowest Cost $g=3$)

  • Dequeue Node $C$ ($g=3$) $\rightarrow$ Active (Red).
  • Goal test $C \neq G$. Move $C$ to Expanded Set (Blue).
  • Generate successor: Goal Node $G$ via $C$ ($g = 3 + 1 = 4$).
  • Insert $G(g=4)$ into priority queue.
  • Priority Queue: $[G(g=4), A(g=5)]$.

Step 4: Dequeue Goal Node $G$ (Lowest Cost $g=4$)

  • Dequeue Goal Node $G$ ($g=4$) $\rightarrow$ Active (Red).
  • Goal Test Evaluated on Dequeue: $G = \text{Goal}$ $\rightarrow$ SUCCESS!
  • The algorithm terminates immediately, returning the optimal solution path $S \rightarrow B \rightarrow C \rightarrow G$ with total cost $g(G) = 4$. Note that $A(g=5)$ is never expanded.

4.2.4. Priority Queue State Tracking Summary

Step Active Node $g(\text{Active})$ Goal Test Successors Generated Priority Queue State $[n(g)]$ Expanded Set
1 Node $S$ $0$ Fail $A(g=5), B(g=1)$ $[B(1), A(5)]$ ${S}$
2 Node $B$ $1$ Fail $C(g=3)$ $[C(3), A(5)]$ ${S, B}$
3 Node $C$ $3$ Fail $G(g=4)$ $[G(4), A(5)]$ ${S, B, C}$
4 Node $G$ $4$ Pass None (Terminates) $[A(5)]$ ${S, B, C, G}$

4.3. Critical Rule: Frontier Addition vs. Goal Node Expansion

4.3.1. Why Goal Test on Enqueue Fails Optimality

A common algorithmic error is applying the goal test to a node when it is first generated and added (enqueued) to the frontier. In UCS, applying the goal test upon generation destroys optimality.

Suppose in our example we had an additional direct edge $S \xrightarrow{c=9} G$.

  • Upon expanding $S$ at Step 1, $G$ would be generated with cost $g(G)=9$ and enqueued into the priority queue.
  • If the goal test were performed on enqueue, the algorithm would prematurely terminate and return the sub-optimal path $S \rightarrow G$ with cost $9$.
  • By delaying the goal test until dequeue, $G(g=9)$ sits in the priority queue while UCS continues expanding cheaper nodes ($B$ at $g=1$, $C$ at $g=3$), eventually discovering the optimal path to $G$ with cost $4$.

4.3.2. Goal Test on Dequeue Guarantee

The fundamental theorem of Uniform-Cost Search states: Goal testing MUST be performed when a node is selected for expansion (dequeued/popped from the priority queue), NOT when it is generated/enqueued.

Because the priority queue strictly pops nodes in non-decreasing order of path cost ($g(n_1) \le g(n_2) \le \dots$), the first time a goal node is dequeued, it is mathematically guaranteed that no remaining node in the frontier or state space can reach a goal with a smaller total path cost.

4.4. Theoretical Properties and Performance Evaluation

4.4.1. Completeness

UCS is Complete if:

  1. The branching factor $b$ is finite.
  2. Every step cost is strictly positive and bounded away from zero by a constant $\epsilon > 0$ (i.e., $c(s, a, s') \ge \epsilon > 0$).

If zero-cost steps or negative-cost steps were permitted, UCS could enter an infinite loop expanding zero-cost cycles without making progress toward a goal state.

4.4.2. Optimality

UCS is Optimal under the condition that step costs are strictly positive ($\epsilon > 0$).

Because nodes are popped in strictly non-decreasing order of $g(n)$, when the optimal goal node $G^$ with path cost $C^$ is popped from the head of the priority queue, all other unexpanded nodes $n$ currently in the frontier satisfy $g(n) \ge C^*$. Hence, no lower-cost path to any goal state can exist.

4.4.3. Time and Space Complexity Analysis

Let $C^*$ denote the cost of the optimal solution path, and let $\epsilon > 0$ be the minimum step cost across all transitions.

The effective depth of the search tree in terms of cost steps is given by $\lfloor C^* / \epsilon \rfloor$. In the worst-case scenario where all step costs equal $\epsilon$, the algorithm explores the entire search space up to cost depth $C^*$:

$$\begin{alignat*}{4} && N_{UCS} &= \sum\limits_{i=0}^{\lfloor C^* / \epsilon \rfloor} b^i && \
&& &= 1 + b + b^2 + \dots + b^{\lfloor C^* / \epsilon \rfloor} && \text{Expand finite geometric series in terms of cost depth} \
&& &= \dfrac{b^{1 + \lfloor C^* / \epsilon \rfloor} - 1}{b - 1} && \text{Apply finite geometric series summation formula for } b > 1 \
&& &= O\left(b^{1 + \lfloor C^* / \epsilon \rfloor}\right) && \text{Extract dominant asymptotic term as } C^*/\epsilon \to \infty \end{alignat*}$$

Summary of UCS Complexities

  • Time Complexity: $O\left(b^{1 + \lfloor C^* / \epsilon \rfloor}\right)$
  • Space Complexity: $O\left(b^{1 + \lfloor C^* / \epsilon \rfloor}\right)$

When all step costs are equal ($c(s, a, s') = 1$), $C^* = d$ and $\epsilon = 1$, reducing $O\left(b^{1 + \lfloor C^* / \epsilon \rfloor}\right)$ directly to $O(b^d)$, showing that BFS is a special case of UCS when all edge weights are uniform.

5. Comparative Analysis and Summary

5.1. Side-by-Side Comparative Matrix (BFS vs. DFS vs. UCS)

To synthesize the core characteristics of uninformed search algorithms, the table below provides a side-by-side evaluation across theoretical parameters, data structures, and operational trade-offs.

Let $b$ represent the maximum branching factor, $d$ the depth of the shallowest goal node, $m$ the maximum depth of the search tree, $C^*$ the optimal solution path cost, and $\epsilon > 0$ the minimum step cost.

Evaluation Criterion Breadth-First Search (BFS) Depth-First Search (DFS) Uniform-Cost Search (UCS)
Frontier Data Structure First-In, First-Out (FIFO) Queue Last-In, First-Out (LIFO) Stack Priority Queue ordered by $g(n)$
Node Expansion Order Shallowest unexpanded node first Deepest unexpanded node first Lowest path cost $g(n)$ first
Completeness Yes (if $b$ is finite and solution at depth $d$) No (fails in infinite trees or cyclic state spaces) Yes (if $b$ is finite and step costs $c \ge \epsilon > 0$)
Optimality Yes (if step costs are equal, e.g., $c=1$) No (returns first path found regardless of cost) Yes (guaranteed if step costs $c \ge \epsilon > 0$)
Time Complexity $O(b^d)$ $O(b^m)$ $O\left(b^{1 + \lfloor C^* / \epsilon \rfloor}\right)$
Space Complexity $O(b^d)$ $O(b \cdot m)$ $O\left(b^{1 + \lfloor C^* / \epsilon \rfloor}\right)$
Primary Bottleneck Memory capacity (exponential frontier $O(b^d) $) Time (can get trapped in deep non-goal branches) Memory capacity (exponential frontier)
Goal Test Timing Upon generation (enqueue) or expansion Upon expansion (dequeue) Strictly upon expansion (dequeue/pop)

5.1.1. Detailed Trade-off Analysis

  1. Memory vs. Time Trade-off:

    • BFS and UCS are optimal and complete search strategies, but they suffer from severe exponential memory growth. Level $d$ in BFS or cost level $C^*/\epsilon$ in UCS holds more nodes than all previous levels combined. Consequently, BFS and UCS run out of memory (RAM) long before running out of CPU processing time.
    • DFS trades off completeness and optimality to achieve an extremely lightweight linear space complexity $O(b \cdot m)$. It only needs to store the current active path and unexpanded siblings on the stack.

  2. Cost-Awareness Trade-off:

    • BFS treats all graph edges uniformly (1 hop = 1 unit cost) and finds the shortest path in terms of edge count $d$.
    • UCS generalizes BFS to weighted graphs with arbitrary non-negative step costs $c \ge \epsilon > 0$. By ordering the priority queue strictly by $g(n)$, UCS guarantees finding the path with minimum total cost $C^*$.

5.2. Transition to Informed (Heuristic) Search

5.2.1. Limitations of Uninformed Search

Uninformed (blind) search algorithms rely purely on state space topology and problem formulation. They possess no domain-specific knowledge regarding the location or distance of the goal node relative to unexpanded states. As a result, uninformed search algorithms explore state space blindly in concentric circles (BFS/UCS) or deep tunnels (DFS), leading to exponential computational complexity in large-scale domain spaces.

5.2.2. Introducing Heuristic Evaluation Functions

To overcome the exponential space and time bottlenecks of uninformed search, Informed (Heuristic) Search incorporates domain-specific knowledge through an evaluation function $h(n)$:

  • Heuristic Function $h(n)$: Estimates the expected cost of the cheapest path from the current node $n$ to a goal state.
  • Property of $h(n)$: By definition, $h(\text{Goal}) = 0$.

5.2.3. Bridging Uninformed and Informed Search Paradigms

Informed search strategies combine the cost-so-far $g(n)$ from UCS with the heuristic estimate-to-goal $h(n)$:

  1. Greedy Best-First Search: Orders the priority queue strictly by heuristic estimate $f(n) = h(n)$, rapidly expanding nodes that appear closest to the goal.
  2. $A^*$ Search: Combines cumulative path cost $g(n)$ from UCS with heuristic estimate $h(n)$: $$f(n) = g(n) + h(n)$$ Here, $f(n)$ estimates the total cost of the cheapest solution path constrained to pass through node $n$. If $h(n)$ is admissible (never overestimates true cost) and consistent, $A^*$ achieves optimal search efficiency.

5.3. Foundations for Modern AI Methods

Uninformed search concepts serve as foundational building blocks for advanced classical and modern AI paradigms:

  1. Monte Carlo Tree Search (MCTS): Combines tree search expansion concepts with randomized rollout simulations and upper confidence bounds (UCB1) to navigate high-dimensional decision trees in complex games like Go and Chess.
  2. Rapidly-exploring Random Trees (RRTs): Extends state space search tree concepts to continuous domain spaces for robotic motion planning and autonomous vehicle pathfinding.
  3. Genetic Algorithms and Evolutionary Search: Treats candidate solutions as individual states and applies biological selection mechanisms to search non-linear optimization landscapes.