Week 3a - Heuristics
===

{%hackmd theme-dark %}

Outline & Objective
---
- Understand the role that heuristic plays in informed search
- Understand the important properties of heuristics
- Admissible, consistent, dominance
- Able to design heuristics that are appropriate for specific problem instances, based on these properties:
- Relax problem
- Sub-problem

### Optimality of A* (Intuitive)
###### Question: Optimality is defined by the path cost. Wouldn't there be cases where it does not return the optimal solution (i.e. high path cost, low heuristics) Or in this case does this mean that the heuristics used is inadmissible/inconsistent?

- Lemma: A* search expands nodes in order of increasing f value
- Gradually adds "f-contours" of nodes (based on the evaluation function, f, which is based on path cost and heuristics)
- Contour i has all nodes with f=f~i~, where $f_i<f_{i+1}$

### Property: Admissible Heuristic
- A heuristic h(n) is admissible if $h(n) \le h^*(n)$
- h(n) = estimated distance from node n to goal state
- h*(n) = true cost from node n to goal state
- Example: Romania Holiday
- h(n) = straight line distance from current city to destination city
- h*(n) = actual road distance from current city to destination city
- In this case, straight line distance can never be greater than the actual road distance

- Inadmissible heuristics might lead the search (node expansion) further away from the goal state

### Property: Consistent Heuristic

- A heuristic h(n) is consistent if $h(n) \le c(n,a,n') + h(n')$
- h(n) = estimated distance from node n to goal state G
- h(n') = estimated distance from node n' to goal state G
- c(n,a,n') = cost of getting from node n to n'

### Property: Dominance
- A heuristic h~2~(n) dominates h~1~(n) if $h_2(n) \ge h_1(n)$ for all n
- Provided that both heuristics are admissible
- A more dominant heuristic will be better for search
- Potentially explore less branches. If the heuristic is less dominant, A* just performs similarly to Greedy Best First Search. A heuristic should ideally be as close to the actual path cost as possible.

## Designing a Heuristic
There are 2 ways to design a heuristic: using the solution of relax problem, or solution of sub-problems.
### Example: 8-Puzzle
#### Relax Problem
#### Sub-Problems