Assignment : Uninformed Search

Table of Contents
1. Core Characteristics of Uninformed Search
2. Breadth-First Search (BFS)
3. Depth-First Search (DFS)
4. Depth-Limited Search (DLS)
5. Iterative Deepening Depth-First Search (IDDFS)
6. Uniform Cost Search (UCS)
7. Bidirectional Search
8. Comparative Summary of Uninformed Search Strategies
9. Common Mistakes and Exam Traps
10. Algorithm Selection Guidelines
View more

Uninformed search strategies, also called blind search or brute-force search, explore the search space systematically without using any domain-specific knowledge about the problem. These algorithms have no information about which states are more promising than others. They differ only in the order in which they explore nodes. Understanding these foundational algorithms is critical for solving pathfinding, puzzle-solving, and game-playing problems in artificial intelligence.

1. Core Characteristics of Uninformed Search

Uninformed search methods operate without heuristic guidance. They rely purely on the problem definition and the structure of the search tree or graph.

• No Domain Knowledge: These algorithms do not use any information about goal proximity or solution quality beyond what is provided in the problem definition itself.
• Systematic Exploration: They explore the search space following a predetermined strategy (depth-first, breadth-first, etc.).
• Completeness: An algorithm is complete if it guarantees finding a solution when one exists.
• Optimality: An algorithm is optimal if it guarantees finding the least-cost solution (usually shortest path).
• Performance Metrics: Evaluated using time complexity (number of nodes generated), space complexity (maximum nodes stored in memory), completeness, and optimality.

1.1 Problem Formulation Components

Before applying uninformed search, the problem must be formally defined with these elements:

1. Initial State: The starting configuration of the problem.
2. Actions: The set of possible operations that can be performed in each state.
3. Transition Model: Describes the result of applying an action to a state.
4. Goal Test: Determines whether a given state is the goal state.
5. Path Cost: Assigns a numeric cost to each path (often uniform cost of 1 per step).

1.2 Search Tree vs Search Graph

• Search Tree: Nodes may be revisited multiple times. Same state can appear in different branches. No cycle detection mechanism.
• Search Graph: Each state appears at most once. Uses a closed list or explored set to track visited states. Prevents redundant exploration and infinite loops.
• Trade-off: Graph search saves time by avoiding repeated states but requires additional memory to store the explored set.

2. Breadth-First Search (BFS)

Breadth-First Search expands the shallowest unexpanded node first. It explores all nodes at depth d before exploring nodes at depth d+1.

2.1 Implementation Strategy

• Data Structure: Uses a FIFO queue (First-In-First-Out) to store the frontier of unexpanded nodes.
• Expansion Order: Root node → all nodes at depth 1 → all nodes at depth 2 → and so on.
• Mechanism: Dequeue the first node, expand it by generating all its successors, enqueue all children at the end of the queue.

2.2 Performance Analysis

Let b = branching factor (maximum number of successors of any node), d = depth of the shallowest goal node.

• Time Complexity: O(b^d) - must explore all nodes up to depth d.
• Space Complexity: O(b^d) - must store all nodes at the current level in memory simultaneously.
• Completeness: Yes (complete) - will always find a solution if one exists and the branching factor is finite.
• Optimality: Yes (optimal) - only when all step costs are identical (uniform cost). Finds the shallowest goal first.

2.3 Advantages and Limitations

• Advantage: Guaranteed to find the shortest path in terms of number of steps when step costs are equal.
• Limitation - Memory Intensive: Requires exponential space. For b=10 and d=10, must store approximately 10 billion nodes.
• Limitation - Slow for Deep Solutions: When the goal is deep in the tree, BFS wastes time exploring many shallow nodes.

3. Depth-First Search (DFS)

Depth-First Search expands the deepest unexpanded node first. It explores one branch completely before backtracking to explore other branches.

3.1 Implementation Strategy

• Data Structure: Uses a LIFO stack (Last-In-First-Out) or recursion to store the frontier.
• Expansion Order: Follows a path from root to leaf, then backtracks to the nearest unexplored branch.
• Mechanism: Pop the most recently added node, expand it, push all children onto the stack (children are explored in reverse order of addition).

3.2 Performance Analysis

Let m = maximum depth of the search tree (may be infinite).

• Time Complexity: O(b^m) - in the worst case, explores the entire tree up to maximum depth.
• Space Complexity: O(bm) - only needs to store nodes along the current path plus unexpanded siblings at each level.
• Completeness: No (not complete) in infinite-depth spaces or spaces with loops. Complete only in finite tree-search spaces.
• Optimality: No (not optimal) - may find a deeper goal before a shallower one.

3.3 Advantages and Limitations

• Advantage - Memory Efficient: Requires linear space O(bm), much less than BFS exponential space.
• Advantage - Fast for Dense Solution Spaces: If solutions are plentiful and deep, DFS can find one quickly.
• Limitation - Infinite Loops: Can get stuck in infinite branches or cycles without graph-search variant.
• Limitation - Non-Optimal: First solution found is often not the shortest path.
• Trap Alert: DFS without cycle detection can loop infinitely in graphs with cycles. Always use an explored set for graph search.

4. Depth-Limited Search (DLS)

Depth-Limited Search is a variant of DFS that imposes a predetermined depth limit l. The algorithm treats nodes at depth l as if they have no successors.

4.1 Key Characteristics

• Depth Limit l: Algorithm explores only up to depth l from the root. Prevents infinite descent.
• Cutoff vs Failure: Returns "cutoff" if the shallowest remaining node is at the depth limit. Returns "failure" if no solution exists within the limit.
• Use Case: Useful when the depth of the solution is known or can be estimated.

4.2 Performance Analysis

• Time Complexity: O(b^l) - explores nodes up to depth l.
• Space Complexity: O(bl) - same linear space benefit as DFS.
• Completeness: No (not complete) - fails if the goal is deeper than l.
• Optimality: No (not optimal) - does not guarantee shortest path.
• Trap Alert: Choosing the wrong depth limit makes DLS useless. Too shallow misses the goal; too deep becomes expensive.

5. Iterative Deepening Depth-First Search (IDDFS)

Iterative Deepening DFS combines the space efficiency of DFS with the optimality and completeness of BFS. It repeatedly performs depth-limited search with increasing depth limits: 0, 1, 2, ..., until the goal is found.

5.1 Algorithm Mechanism

1. Perform DLS with limit l = 0.
2. If goal not found, increment l to 1 and repeat DLS.
3. Continue incrementing l and repeating until goal is found.
4. Each iteration explores the entire tree up to the current depth limit.

5.2 Performance Analysis

For a goal at depth d:

• Time Complexity: O(b^d) - appears to repeat work, but overhead is minimal because most nodes are at the deepest level.
• Space Complexity: O(bd) - same linear space as DFS.
• Completeness: Yes (complete) - guaranteed to find the shallowest goal.
• Optimality: Yes (optimal) when step costs are uniform - finds the shallowest solution like BFS.

5.3 Redundant Node Generation Analysis

IDDFS appears wasteful because it regenerates nodes multiple times. However, the redundancy is acceptable:

• Nodes at depth d are generated once.
• Nodes at depth d-1 are generated twice.
• Nodes at depth d-2 are generated three times.
• Total nodes generated: (d)b^d + (d-1)b^d-1 + ... + (1)b¹ ≈ O(b^d) when b > 1.
• The exponential growth means the bottom level dominates, so repeated shallow levels add negligible overhead.

5.4 Why IDDFS is Preferred

• Best of Both Worlds: Combines BFS optimality and completeness with DFS memory efficiency.
• Practical Choice: Often the preferred uninformed search method for large spaces with unknown solution depth.
• No Memory Explosion: Unlike BFS, IDDFS can solve problems with very large branching factors without running out of memory.

6. Uniform Cost Search (UCS)

Uniform Cost Search expands the node with the lowest path cost g(n), where g(n) is the cost from the start node to node n. It generalizes BFS to handle non-uniform step costs.

6.1 Implementation Strategy

• Data Structure: Uses a priority queue ordered by path cost g(n). The node with the smallest g(n) is expanded first.
• Goal Test Timing: Goal test is applied when a node is expanded (popped from queue), not when it is generated.
• Mechanism: Expand the cheapest node, generate successors, insert them into the priority queue with their cumulative path costs.

6.2 Performance Analysis

Let C* = cost of the optimal solution, ε = minimum step cost.

• Time Complexity: O(b^{1 + ⌊C*/ε⌋}) - explores all nodes with path cost less than the optimal cost.
• Space Complexity: O(b^{1 + ⌊C*/ε⌋}) - must store all frontier nodes in the priority queue.
• Completeness: Yes (complete) if step costs are positive (ε > 0).
• Optimality: Yes (optimal) - guaranteed to find the least-cost solution.

6.3 Comparison with BFS

• BFS as Special Case: When all step costs are equal, UCS reduces to BFS.
• Cost-Based Expansion: UCS explores based on total path cost, not depth. A shallow but expensive path is expanded after a deep but cheap path.
• Trap Alert: UCS can get stuck in infinite loops if step costs can be zero. Always ensure ε > 0.

7. Bidirectional Search

Bidirectional Search runs two simultaneous searches: one forward from the initial state and one backward from the goal state. The search terminates when the two frontiers meet.

7.1 Core Mechanism

• Forward Search: Starts from the initial state, expands towards the goal.
• Backward Search: Starts from the goal state, expands towards the initial state (requires the ability to generate predecessors).
• Termination: Stops when a node appears in both frontiers, indicating a connection.
• Prerequisite: Goal state must be explicitly known and unique. Predecessor generation must be feasible.

7.2 Performance Analysis

Assuming both searches are BFS with branching factor b and solution at depth d:

• Time Complexity: O(b^d/2 + b^d/2) = O(b^d/2) - each search explores half the depth.
• Space Complexity: O(b^d/2) - must store both frontiers.
• Completeness: Yes (complete) if both component searches are complete (e.g., both BFS).
• Optimality: Yes (optimal) if both searches are BFS and step costs are uniform.
• Speedup: Reduces exponential complexity dramatically. For b=10, d=6: unidirectional explores 10⁶ = 1,000,000 nodes; bidirectional explores 2 × 10³ = 2,000 nodes.

7.3 Limitations and Challenges

• Requirement for Predecessors: Not all problems allow easy computation of predecessor states (e.g., cryptographic hash functions).
• Multiple Goals: Ineffective when there are many possible goal states. Backward search does not know which goal to start from.
• Frontier Intersection Check: Requires efficient checking to detect when nodes from both searches meet. Typically implemented using hash tables.

8. Comparative Summary of Uninformed Search Strategies

Notation: b = branching factor, d = depth of shallowest goal, m = maximum depth of tree, l = depth limit, C* = optimal solution cost, ε = minimum step cost.

9. Common Mistakes and Exam Traps

• Trap - BFS is Not Always Optimal: BFS is optimal only when all step costs are identical. With varying costs, use UCS instead.
• Trap - DFS Completeness: DFS is not complete in infinite state spaces or graphs with cycles. Always specify whether the space is finite or if cycle detection is used.
• Trap - Goal Test in UCS: In UCS, the goal test must be applied when a node is expanded, not when generated. Testing at generation can lead to suboptimal solutions.
• Trap - IDDFS Efficiency Misconception: Students often think IDDFS wastes too much time regenerating nodes. In reality, the overhead is negligible because exponential growth means the deepest level dominates.
• Trap - Bidirectional Search Applicability: Bidirectional search requires a single, known goal state and the ability to generate predecessors. It fails when there are multiple goals or predecessor generation is infeasible.
• Trap - Space Complexity Confusion: BFS and UCS have exponential space complexity, making them impractical for deep solutions. DFS, DLS, and IDDFS have linear space complexity, which is a critical advantage.

10. Algorithm Selection Guidelines

• Use BFS when: Solution is shallow, all step costs are equal, and memory is not a constraint.
• Use DFS when: Solutions are deep and plentiful, memory is limited, or exploring all paths is required (e.g., backtracking problems).
• Use IDDFS when: Solution depth is unknown, memory is limited, and you need optimality with uniform costs.
• Use UCS when: Step costs vary, and you need the least-cost solution.
• Use Bidirectional when: The goal is unique and known, predecessor generation is easy, and exponential speedup is critical.
• Avoid DFS for: Infinite state spaces or when optimality is required.

Mastering uninformed search algorithms provides the foundation for understanding more advanced search techniques. These algorithms demonstrate fundamental trade-offs between time, space, completeness, and optimality. In practice, informed search methods (using heuristics) often outperform uninformed approaches, but understanding the uninformed baselines is essential for algorithm design, problem-solving, and theoretical analysis in artificial intelligence.