Manav Goyal

Uninformed Searching - Artificial Intelligence

Breadth First Search (BFS)
- Uninformed, Blind, Brute-force
- FIFO => Using Queue
- Shallowest Node => Level order
- Complete => Will always give answer
- Gives optimal path for similar Cost
- Time Complexity = O(V+E) = O(Branching factor^Depth)
- Algorithm
  - Push Start node in Queue
  - Till Queue is Empty
    - Pop a Node and check if it is Goal node
      - If goal then return path
    - Go to all its adjacent elements and push in Queue if not already visited
Uniform Cost Search
- Basic
  - Complete
  - Optimal
- Algorithm
  - Expand least cost unexpanded node
Depth First Search (DFS)
- Uninformed, Blind, Brute-force
- LIFO => Using Stack
- Deepest Node
- Incomplete => Will not always give answer
  - Due to Cycles or infinite search space in one side
- Doesn't gives optimal path
- Time Complexity = O(V+E) = O(Branching factor^Depth)
- Algorithm
  - Push Start node in Stack
  - Till Stack is Empty
    - Pop a Node and check if it is Goal node
    - Go to all its adjacent elements and push in Stack if not already visited
Depth Limited Search
- Basic
  - DFS with depth limit
- Algorithm
  - Nodes at depth L has no successors
Bidirectional Search Algorithm
- Two simultaneous search from an initial node to goal and backward from goal to initial, stopping when two meets
- Time Complexity = O(2 * Branching factor^Depth/2)
- Complete in BFS, Not in DFS
Iterative Deepening Search
- Basic
  - Complete
  - Optimal
- Algorithm
  - Start from depth 0 then keep on increasing depth limit and do DLS
Problems
- 8-Puzzle Problem without Heuristic
  - Worst Case Time Complexity = 3²⁰
  - Average Branching Factor = 2.6 ≈ 3
- 15-Puzzle Problem without Heuristic
  - Worst Case Time Complexity = 10¹³
- 24-Puzzle Problem without Heuristic
  - Worst Case Time Complexity = 10²⁴