# AI - lesson 06
#### Francesco Arrigoni
###### 28 October 2015
## Informed search strategies

### Evaluation function $f(n)$ types

### Greedy best first
$$f(n)=h(n)$$
$h(n)$ is called *heuristic function* and is an estimate of __how far__ is a node __from the goal__

#### example
- The nodes of the graph are __cities__ and the heuristic function can be the cartesian distance of the cities

- In the game of 15 an heuristic can be an estimate of the number of moves needed to complete the game

By definition the heuristic function is defined over __nodes__, but commonly are defined over a __state__, in fact
the heuristic function of two nodes referring to the same node is the same.

According to how heuristic functions are defines, there can be loops in __greedy best first__

#### Optimality

This strategy is __not optimal__ in general

#### Complexity

Setting a not clever heuristic function, this strategy is equivalent to the depht first  
But with a good heuristic function, we can exploit this to achieve better results.
__time__:$O(b^m)$
__space__:$O(b^n)$

### $A^*$

In this case the __evaluation function__ is defined as $f(n)=g(n)+h(n)$
$g(n)$ is the cost for going from the root to node n
$h(n)$ is an estimation of the costs for going from node n to the goal g

Doing so $f(n)$ is the estimated cost of the solution passing through n

#### Optimality

$A^*$ is optimal when using __tree search__, that is when the heuristic function is *admissible*
$h^*()$ is admissible when $\forall n\;h(n)\le h^*(n)$ The heuristic function never overestimates the cost of reaching a node.

Returning to the road example:  
The straight distance (line of sight) between two cities is a valid heuristic by definition, in fact the real distance
can not be smaller than this.

##### example

$$f(g_2)=g(g_2)+h(g_2)>c^*$$
$$f(n)=g(n)+h(n)\le c^*$$
$$f(n)\le c^*<f(g_2)$$

An Heuristic function is __consistent__ if for every node that is a successor of n
$$\foralln,n' h(n)\le c(n,n')+h(n')$$

__Consistency__ of heuristic function implies __admissibilitu__

- $f(n) is not decreasing along every path

$A^*$ will choose nodes from the frontier with value that in a non decreasing order.

#### Complexity
- Time complexity $O(\square^{|h-h^*|})

If the heuristic function is always zero, $A^*$ degerates in uniform cost.

If we have a perfect heuristic function, the time complexity is constant
$A^*$ is called __optimally efficient__, this means that given a fixed heuristic function. $A^*$ is guaranteed to expand the
minimum number of nodes