Week 2b - Uninformed Search II
===
###### Source: [Lecture Video](https://www.dropbox.com/s/m4ckoe930gc7m3t/Week%202b%20-%20Uninformed%20Search%20II.mp4?dl=0)
{%hackmd theme-dark %}

Outline
---
- 5 different uninformed search algorithms
- ~~Breadth-First Search~~
- ~~Uniform cost search~~
- Depth-First Search
- Depth-limited search
- Iterative deepening search

## Depth-First Search

- General Idea: Expand the deepest unexpanded node
- Implementation: Using a LIFO queue

### Steps
1. Initialize frontier, queue: a
2. Check node for goal state
3. Not goal? Expand nodes based on strategy (e.g. largest alphabetical order). Queue: ab,ac,~~a~~ (For simplicity, items in queues will subsequently only contain the next nodes instead of the entire paths).
4. Check next node for goal state. Queue: ~~b~~,c
5. Not goal? Continue expanding nodes. Queue: d,e,c
6. Check next node for goal state. Queue: ~~d~~,e,c
7. Not goal? Continue expanding nodes. Queue: h,i,e,c
8. Check next node for goal state. Queue: ~~h~~,i,e,c
9. Not goal? Continue to the next node in the queue. Queue:: i,e,c
10. etc.

### Properties of DFS
- Completeness: No (if m is infinite, where m is the depth of the tree)
- Optimality: No (solution found might not be optimal, since it only goes through one path first)
- Time complexity: $O(b^m)$ (terrible if m > d by a lot)
- Space complexity: $O(bm)$

### Exercise: BFS vs DFS
- When is BFS preferred over DFS?
- When optimal solution is important
- When m is much greater than d (as DFS takes $O(b^m)$ time)
- When is DFS preferred over BFS?
- When space is important. DFS requires $O(bm)$, where BFS requires $O(b^d)$

## Depth-Limited Search

- General idea: DFS with predetermined depth limit l.
- Nodes at depth l have no successors (child nodes)
- Solves the infinite-path problem
- Completeness: No (if l < d)
- Optimality: No (if l > d)
- Time complexity: $O(b^l)$
- Space complexity: $O(bl)$

Incomplete Search

Unoptimal Solution (there might be other solutions at the deeper parts of the tree, but they're not optimal solutions)

## Iterative Deepening Search
- General idea: Use increasing Depth-Limited Search (DLS) to find the best depth limit l.
- use DLS with depth limit 1. If no solution, then increase depth limit to 2, ... until solution is found.
- Best of both BFS and DFS
- But is it wasteful to keep generating states with each increasing DLS?
- It's not too costly as most of the work (node expansion) happens at the lower depths.

### Properties
###### Question: How is this different from BFS, completeness and optimality wise?
- Completeness: Yes
- Optimality: Yes
- Time complexity: $O(b^d)$
- Space complexity: $O(bd)$