02_Uninformed_Search

Tags: #◇CSINTSY #◇Computational Thinking #◇Computer Science #◇Artificial Intelligence #◇Machine Learning #◇Intelligent Systems #◇Probability #◇Data Analysis

---

◇Overview

Uninformed Search (also called Blind Search) algorithms have no additional information about states beyond the problem definition. They can only di...

◇Details / Theory

2. Uninformed Search Reviewer

◇Overview

Uninformed Search (also called Blind Search) algorithms have no additional information about states beyond the problem definition. They can only distinguish a goal state from a non-goal state. They do not know if a non-goal state is "better" or "closer" to the goal than another.

◇Algorithms

1. Breadth-First Search (BFS)

Strategy: Explores the shallowest nodes first. It visits all neighbors of a node before moving to the next depth level. Data Structure: Queue (FIFO - First In, First Out). Order: Level by level ($L_0 \to L_1 \to L_2 \dots$). Properties:
Complete: Yes (if the branching factor is finite). It will find a solution if one exists.
Optimal: Yes, only if all step costs are equal (e.g., all edges have cost 1). It finds the path with the fewest edges.
Memory: High (Exponential). It needs to store all nodes at the current level to generate the next level.

2. Depth-First Search (DFS)

Strategy: Explores as far as possible along each branch before backtracking. It dives deep into the graph. Data Structure: Stack (LIFO - Last In, First Out). Order: Deepest unexpanded node first. Properties:
Complete: No. It can get stuck in infinite loops or infinite paths.
Optimal: No. It might find a long path to the goal before finding a shorter one.
Memory: Low (Linear). It only needs to store the current path and unexpanded siblings.

3. Iterative Deepening DFS (ID-DFS)

Strategy: Combines the benefits of BFS (completeness) and DFS (memory efficiency). It runs DFS with a depth limit ($L$), increasing the limit iteratively ($L=0, L=1, L=2, \dots$) until the goal is found. Sequence:
Run DFS with limit 0.
Run DFS with limit 1.
Run DFS with limit 2.
... Properties:
Complete: Yes.
Optimal: Yes (if step costs are equal).
Memory: Low (Linear), like DFS.

4. Uniform Cost Search (UCS)

Strategy: Expands the node with the lowest cumulative path cost $g(n)$ from the start node. Data Structure: Priority Queue (ordered by $g(n)$ ascending). Evaluation Function: $f(n) = g(n)$, where $g(n)$ is the cost from start to node $n$. Process:

1. Insert Start Node into Priority Queue with cost 0.
2. While queue is not empty:
   Pop node with lowest cost.
   Goal Test: Check if it is the goal. If yes, return solution.
   Expand node (generate children).
   Calculate cost for children: $g(child) = g(parent) + cost(parent, child)$.
   Insert children into Priority Queue. Properties:
   Complete: Yes (if step costs are positive).
   Optimal: Yes. It is guaranteed to find the cheapest path.
   Memory: High (Exponential).

5. Backtracking Search

Usage: Often used in Constraint Satisfaction Problems (CSPs) like N-Queens or Sudoku. Strategy: A variation of DFS. It builds a solution incrementally. Mechanism:
Choose a variable.
Assign a value.
Check constraints.
If constraints are violated, backtrack (undo assignment) and try a different value.
If all variables are assigned validly, return solution.

◇Comparison Table

◇Solved Example: BFS vs. DFS vs. UCS

Graph:
S -> A (Cost 1), S -> B (Cost 5) A -> C (Cost 2), A -> D (Cost 4) B -> G (Cost 5) C -> G (Cost 10) D -> G (Cost 2)

Goal: Reach G from S.

1. Breadth-First Search (BFS)

Queue (FIFO). Tie-breaking: Alphabetical.

1. Start: Queue = [S].
2. Pop S. Neighbors: A, B. Queue = [A, B].
3. Pop A. Neighbors: C, D. Queue = [B, C, D]. (A's children go to back)
4. Pop B. Neighbors: G. Queue = [C, D, G].
5. Pop C. Neighbors: G. Queue = [D, G, G].
6. Pop D. Neighbors: G. Queue = [G, G, G].
7. Pop G. Goal Found!
   Path: $S \to B \to G$ (found via B first in some implementations) or $S \to A \to \dots$ depending on when goal test is applied. Note: Standard BFS checks goal on generation.
   Expand S -> Generate A, B.
   Expand A -> Generate C, D.
   Expand B -> Generate G. Stop.
   Path: $S \to B \to G$. Cost: $5+5=10$. (Not optimal cost, but fewest steps: 2).

2. Depth-First Search (DFS)

Stack (LIFO). Tie-breaking: Alphabetical (push Z then A, so A pops first).

1. Start: Stack = [S].
2. Pop S. Push B, A. Stack = [B, A].
3. Pop A. Push D, C. Stack = [B, D, C].
4. Pop C. Push G. Stack = [B, D, G].
5. Pop G. Goal Found!
   Path: $S \to A \to C \to G$. Cost: $1+2+10 = 13$.

3. Uniform Cost Search (UCS)

Priority Queue (Cost).

1. Start: PQ = [(S, 0)].
2. Pop (S, 0).
   Add A (Cost 1). PQ = [(A, 1)].
   Add B (Cost 5). PQ = [(A, 1), (B, 5)].
3. Pop (A, 1).
   Add C (Cost 1+2=3). PQ = [(C, 3), (B, 5)].
   Add D (Cost 1+4=5). PQ = [(C, 3), (B, 5), (D, 5)].
4. Pop (C, 3).
   Add G (Cost 3+10=13). PQ = [(B, 5), (D, 5), (G, 13)].
5. Pop (B, 5).
   Add G (Cost 5+5=10). PQ = [(D, 5), (G, 10), (G, 13)].
6. Pop (D, 5).
   Add G (Cost 5+2=7). PQ = [(G, 7), (G, 10), (G, 13)].
7. Pop (G, 7). Goal Found!
   Path: $S \to A \to D \to G$. Cost: 7. (Optimal).

---

◇Common Pitfalls

Confusing completeness (will it find a solution?) with optimality (will it find the best one?). Using DFS when optimality is required — DFS is not optimal and may get stuck in infinite branches. Forgetting that UCS expands by lowest $g(n)$, not by depth — it’s optimal for non-negative costs. Not recognizing that Iterative Deepening combines BFS’s completeness with DFS’s memory efficiency.

◇Summary

TL;DR — Uninformed searches (BFS, DFS, IDDFS, UCS) explore without heuristics. BFS and UCS are complete and optimal (UCS for weighted graphs). DFS is memory-efficient but not optimal. IDDFS gets the best of both.

◇Links

Related: Source / Reference:

---

Made by 2ru17

Please contact me through discord or my the university email for any problems regarding the reviewer. Thanks!

◇References & Navigation

• Previous Topic: ◇State Based Model
• Next Topic: ◇Informed Search
• Related Notes: ◇Uniform Cost Search