State Space Formalism & Uninformed Search Strategies
“Problem formulation, BFS, DFS, Uniform Cost Search (Dijkstra), and Iterative Deepening (IDS) performance bounds.”
1.State Space Search Problem Formulation
§ 1.1.In classical artificial intelligence, an agent achieves its objectives by finding a sequence of actions that transforms an initial state into a desired goal state within an abstract state space.
A formal search problem consists of five formal components:
1. Initial State: The starting state the agent occupies (e.g. s_0 = In(Arad)).
2. Action Set Actions(s): The set of legal moves available to the agent in state s.
3. Transition Model Result(s, a): The deterministic state resulting from executing action a in state s.
4. Goal Test IsGoal(s): A Boolean predicate determining whether state s satisfies the target condition.
5. Path Cost c(s, a, s'): The non-negative numerical cost of executing action a to reach s' from s. The total path cost is the additive sum of individual step costs.
2. Master Comparison of Uninformed Search Strategies
Comparative theoretical criteria for the five classical uninformed search algorithms across branching factor b, shallowest goal depth d, and maximum path depth m:
| Feature / Aspect | Criterion | Breadth-First (BFS) |
|---|---|---|
| Frontier Data Structure | FIFO Queue | LIFO Stack |
| Time Complexity | O(b^d) | O(b^m) |
| Space Complexity | O(b^d) (Exponential) | O(b * m) (Linear) |
| Completeness | Yes (if b is finite) | No (fails on infinite/loops) |
| Optimality | Yes (if step costs equal) | No (finds leftmost path) |
3.Uniform-Cost Search (UCS) & The Goal Test Timing Rule
§ 1.3.Uniform-Cost Search (equivalent to Dijkstra's algorithm on directed graphs) expands nodes in increasing order of cumulative path cost g(n) from the start node.
The Critical Timing Rule for Optimality:
In BFS, an agent can terminate the search the moment a goal node is generated (inserted into the FIFO queue) because all nodes at depth d are generated before any node at depth d+1.
However, in UCS, the agent MUST NOT terminate when a goal is merely generated. A goal node might be generated via a high-cost path first, while a cheaper path to the same goal (or another goal) is still pending expansion on the priority queue. Therefore, UCS must test for the goal condition ONLY WHEN A NODE IS SELECTED FOR EXPANSION (popped from the priority queue).
• BFS applies Goal Test at GENERATION time (saves 1 layer of node expansions). • UCS and A* apply Goal Test at EXPANSION time (mandatory to guarantee optimal cost path).
4.Iterative Deepening Search (IDS): Combining Completeness with Linear Memory
§ 1.4.Breadth-First Search is memory-constrained: for branching factor b = 10 and depth d = 6, BFS stores ~1,000,000 nodes in RAM. Depth-First Search is memory-efficient (stores only b * m nodes) but can plunge down an infinite path.
Iterative Deepening Search (IDS) resolves this fundamental dilemma by running Depth-Limited Search (DLS) repeatedly with increasing depth limits L = 0, 1, 2, ... d:
Number of Generated Nodes in IDS:
$N(IDS) = (d + 1) b^0 + d b^1 + (d - 1) b^2 + ... + 1 b^d = O(b^d)$
The root node is generated d+1 times, while the deepest level nodes (which constitute the vast majority of the search space, (b - 1)/b of all nodes) are generated only once! Thus, IDS achieves asymptotic time O(b^d) with linear space O(b \cdot d).
5. GATE Worked Numerical: Node Expansion Counts in IDS vs BFS
Remember that the bottom level nodes in IDS are generated exactly ONCE, whereas the root is generated d + 1 times!
Problem (Original Practice Problem · Modeled on GATE DA Pattern):
A state space has a uniform branching factor b = 4. The shallowest goal state lies at depth d = 4.
Calculate: (a) Total nodes generated by Breadth-First Search (BFS) assuming goal test at generation, and (b) Total nodes generated by Iterative Deepening Search (IDS) up to depth d = 4.
Step 1: Compute BFS Node Generation Count:
BFS generates all nodes from level 0 up to level d:
Level 0: 4^0 = 1 node.
Level 1: 4^1 = 4 nodes.
Level 2: 4^2 = 16 nodes.
Level 3: 4^3 = 64 nodes.
Level 4: In the worst case (goal is the last node generated at depth 4), BFS generates all 4^4 = 256 nodes.
Total BFS Nodes = 1 + 4 + 16 + 64 + 256 = 341 nodes.
Step 2: Compute IDS Node Generation Count:
Formula: N(IDS) = sum_{k=0}^{d} (d - k + 1) * b^k
Here d = 4, b = 4:
k = 0 (Depth 0): (4 - 0 + 1) 4^0 = 5 1 = 5 nodes.
k = 1 (Depth 1): (4 - 1 + 1) 4^1 = 4 4 = 16 nodes.
k = 2 (Depth 2): (4 - 2 + 1) 4^2 = 3 16 = 48 nodes.
k = 3 (Depth 3): (4 - 3 + 1) 4^3 = 2 64 = 128 nodes.
k = 4 (Depth 4): (4 - 4 + 1) 4^4 = 1 256 = 256 nodes.
Total IDS Nodes = 5 + 16 + 48 + 128 + 256 = 453 nodes.
Step 3: Analyze Overhead:
Ratio = 453 / 341 ≈ 1.328 (only ~33% extra node generations, but BFS requires storing 256 nodes simultaneously, whereas IDS stores at most b d = 4 4 = 16 nodes in the call stack!).
Conclusion: BFS generates 341 nodes; IDS generates 453 nodes with 94% memory reduction.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.