# Tree search with heuristics

## Search algorithms with heuristics

Find absolute distance from goal for each node. choose node with shortest distance.

Cost of each is $$f(n)=h(n)$$, where $$h(n)$$ is the heuristic cost of node $$n$$.

If the heuristic is admissible, then a* is optimal. Intuitively because the the heuristic steers away from any suboptimal solutions.

Admissible? For all nodes n , h(n)<=h*(n). where h* is true cost

$$f(n)=g(n)+h(n)$$

$$g(n)$$ is the cost to reach $$n$$ from the current position.

Informed: Yes

Time: Exponential

Space: Big, all nodes kept in memory

Complete: Yes

Optimal: Yes, if the heuristic is admissible