Lecture 03.3: Advanced Uninformed Search

Breadth-First Search (BFS) and Depth-First Search (DFS) are foundational, but they have major flaws. BFS uses too much memory, and DFS can get stuck in infinite loops and isn't optimal. To solve these issues, we look to advanced uninformed search strategies.

1. Uniform Cost Search (UCS)

A breadth-first search finds the shallowest goal state. This is only guaranteed to be the cheapest solution if the path cost is a function of the depth (i.e., every step costs the same). If step costs vary, BFS fails to find the optimal path.

Uniform Cost Search (UCS) remedies this by expanding the lowest-cost node on the fringe, rather than the shallowest node.

Why UCS matters: A Shortest Path Example

Consider finding the shortest route from Start ($S$) to Goal ($G$):

• BFS approach: BFS might expand $A$ first (cost 1). Seeing $G$ as a successor of $A$, it finds the path $S \rightarrow A \rightarrow G$ with a total cost of $11$. It stops, assuming it found the best path because it reached $G$ in 2 steps.
• UCS approach: UCS expands the lowest cost node currently available.
  1. Starts at $S$. Queue: $A(1), B(5), C(15)$.
  2. Expands $A$. Finds $G$ with cost $11$. Queue: $B(5), G(11), C(15)$.
  3. Crucially, UCS does not stop yet! $B(5)$ is cheaper than $G(11)$.
  4. Expands $B$. Finds $G$ through $B$ with cost $5 + 5 = 10$. Queue: $G(10), G(11), C(15)$.
  5. Expands $G(10)$ and returns the optimal path $S \rightarrow B \rightarrow G$.

---

2. Depth-Limited Search (DLS)

The biggest problem with DFS is its unbounded nature; it can traverse down an infinite path forever.

Depth-Limited Search (DLS) resolves this by supplying DFS with a pre-determined depth limit $l$. Nodes at depth $l$ are treated as if they have no successors.

• Completeness: Solves the infinite-path problem, but introduces incompleteness if $l < d$ (where $d$ is the depth of the shallowest goal).
• Optimality: Non-optimal if $l > d$.
• Time Complexity: $O(b^l)$
• Space Complexity: $O(bl)$

(Note: Standard DFS is simply a special case of DLS where $l = \infty$).

---

3. Iterative Deepening Search (IDS)

The problem with DLS is deciding on a suitable depth parameter $l$. Iterative Deepening Search (IDS) avoids this by gradually increasing the depth limit—first 0, then 1, then 2, and so on—until a goal is found.

This guarantees finding the goal when the depth limit finally reaches $d$.

How IDS Works

• Iteration 0: Limit=0. Expand $A$. No goal.
• Iteration 1: Limit=1. Expand $A$, $B$, $C$. No goal.
• Iteration 2: Limit=2. Expand $A$, $B$, $D$, $E$, $C$, $F$, $G$. Goal found!

Is IDS Wasteful?

Generating states multiple times seems wasteful. However, in a search tree with a consistent branching factor, the vast majority of nodes are in the bottom level.

• The nodes on the bottom level are generated once.
• The nodes on the next-to-bottom level are generated twice.
• Only the children of the root are generated $d$ times.

Properties of IDS:

• Complete? Yes.
• Optimal? Yes (if step cost = 1).
• Time: $(d+1)b^0 + d b^1 + (d-1)b^2 + ... + b^d = O(b^d)$
• Space: $O(bd)$ (linear space, just like DFS!).

IDS combines the benefits of DFS (low memory) and BFS (complete and optimal).

---

4. Bidirectional Search

Bidirectional search operates by simultaneously searching forward from the initial state and backward from the goal state. The searches expand until they meet in the middle.

• Advantage: Can be significantly faster. It reduces the search space because $b^d$ becomes $2 \times b^{d/2}$.
  • Example: If $b=10$ and $d=10$, bidirectional search can be up to 50,000 times faster.
• Challenges: The goal state must be known a priori. Memory consumption can be high, as it maintains two search trees.

---

Summary of Search Algorithms

Legend: $b$ = branching factor, $d$ = depth of shallowest solution, $m$ = max depth of the search tree, $l$ = depth limit, $C^*$ = cost of optimal solution, $\epsilon$ = minimum step cost.