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

Outline & Objectives
---
- Learn about two different informed search algorithms
- Greedy Best-First Search
- A* Search
- Understand the role that heuristic plays in these algorithms
- Being able to use Greedy Best-First Search and A* Search to solve a search problem

## Improvement to Uniform Cost Search
- UCS: Expand unexpanded node n with the lowest path cost g(n). Formally, this is via an evaluation function f(n) = g(n).
- UCS Implementation: Use a priority queue ordered by path cost g(n).
- Evaluation function f(n)
- For UCS, path cost measures how far a node is from the initial state
- Is this effective? Does a shorter path from the initial state mean we're nearer to the goal state?
- Path cost ignores direction. This might lead to a lot of redundant searches.

## Heuristics
Definition: A rule of thumb, simplification, or educated guess that reduces or limits the search for solutions in domains that are difficult and poorly understood.

### Heuristic function h(n)
- The heuristic function h(n) is an estimate of how close a state n is to the goal state.
- Informed search algorithms use heuristics to solve the search problem.
- There are good and bad heuristics

In the Romania Holiday example, the straight line distances to the Goal state could be used as the heuristic function.

## Greedy Best-First Search

- General Idea: Expand the node n with the lowest heuristic h(n)
- Implementation: use a PQ ordered by heuristic h(n).
- Evaluation function f(n) = h(n)

### Steps
1. The initial state (Arad). Queue: A
2. After expanding Arad: Queue: Sibiu, Timisoara, Zerind, Arad (lowest heuristic first)
3. After expanding Sibiu: Queue: F,R,S,T,A,Z,O,A. Since A is already in the queue, it will not be added anymore.
...

### Properties
- Completeness: No (can get stuck in the loop, unless the repeated states are kept track of)
- Optimality: No (GBFS uses heuristic instead of real path cost rather than metrics)
- Time complexity: $O(b^m)$ (Similar to DFS but a good heuristic can improve the performance greatly)
- Space complexity: $O(b^m)$ (keeps all nodes in memory)

### Exercise: UCS vs GBFS
- What are the issues with UCS in contrast to greedy search?
- Complete and optimal but may "waste" search in the wrong direction.
- What are the issues with GBFS, in contrast to UCS?
- Search generally in the "right" direction but not complete or optimal
- Is there a way to combine the two and address each's shortcomings?
- UCS: f(n) = g(n)
- Greedy: f(n) = h(n)
- Combined: f(n) = g(n)+h(n)

## A* Search
- General idea: Expand the node n that has incurred the least cost and is nearest to the goal state.
- Implementation: using a priority queue ordered by evaluation function f(n)
- Evaluation function f(n) = g(n)+h(n)
- Path cost g(n) = total path cost from start node to node n
- Heuristic h(n) = estimated distance from node n to goal state.

### Property
- Completeness: Yes
- Optimality: Yes (if heuristics are admissible/consistent)
- Time complexity: Same as UCS
- Space complexity: Same as UCS