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

Outline & Objectives
---
- 5 different uninformed search algorithms
- Breadth-First Search
- Uniform-cost Search
- Understand the trade-offs in properties between these algorithms
- Use these algorithms to solve a search problem

Search Strategies
---
A search strategy is defined by picking the order of node expansion.
This can be implemented using different types of queue structures to represent the frontier. Different queue structures correspond to different search strategies since each defines a different way to remove a node from the frontier.

Order of node expansion = Adding / Removal sequence in queue

Breadth-First Search
---
General Idea: Expand the shallowest unexpanded node
Implementation: Using a FIFO queue

### Steps:
1. Initialize frontier. Queue: a
2. Check node for goal state. Queue: ~~a~~ (pop a).
3. If it's not the goal state, expand node based on strategy. Queue: ~~a~~, ab, ac
4. Check next node for goal state. Queue: ~~a, ab~~, ac (pop b)
5. If it's still not the goal state, continue expanding the nodes. Queue: ~~a, ab~~, ac, abd, abe
6. Check node for goal state. Queue: ~~a,ab, ac~~, abd, abe
7. and so on until the node is found, where we will return the tree path. If the searched node is not found, return `None`.

### Algorithm

### Properties
- Completeness: Yes (if b is finite)
- Optimality: Yes (if cost = 1 per step -- unweighted graph). But not optimal in general.
- Time complexity: $1+b+b^2+\ldots+b^d=O(b^d)$, where b is the branching factor and d is the depth of the optimal solution. Each iteration leads to visiting $b^i$ nodes
- Space complexity: $O(b^d)$ every node needs to be kept in the memory

### Issues with BFS
- Memory requirements are a bigger problem for BFS than execution time.
- Exponential complexity search problems cannot be solved by uninformed methods for any but the smallest instances.


- If step cost is non-uniform (if graph is weighted), BFS will not return an optimal solution.

Uniform Cost Search
---
###### Question: In this example, are all edges supposed to have the same weights?
General Idea: Expand unexpanded node n with the lowest path (path so far + next step) cost g(n)
Implementation: Using a priority queue ordered by path cost g.

In this example, nodes will be visited in the order of: {a,b,d,i,e,h,c,...}

### Algorithm
Most of the steps are the same as BFS, just with different queue DS. Main difference is the additional shortest path comparison and the goal test is done after popping the node from the frontier.
The shortest path comparison at the end (last 2 lines) is to replace the path to the node in the frontier with a shorter path to the node. This is similar to relaxation step in graph problems.

The reason why goal test is done after popping the node is because if the goal state is a neighbor to the initial node, the algorithm will return the immediate path to the goal state despite it not being the most optimal path.

### Properties
###### Question: Explain time and space complexity calculation
- Completeness: Yes (If step cost > ε, some positive constant) (no negative weights)
- Optimality: Yes
- Time complexity: $O(b^{C^*/\epsilon})$ Given C* = cost of optimal solution. If graph is unweighted, this will have the same complexity as BFS.
- Space complexity: $O(b^{C^*/\epsilon})$