Heuristic Search

Question 1

What is a heuristic search

Answer 1

Explores the next best node, more likely to lead to the goal state
Using domain knowledge, so called informed/heuristic search

Question 2

A* algorithm

Answer 2

Combines the cost so far and the estimated heuristic cost to the goal

F(n) = g(n) + h(n)

G - path cost from initial state to current state
H - heuristic cost from current state to goal state
F - estimated cost of the cheapest solution

Question 3

What makes a good heuristic

Answer 3

Admissible
Closer the estimate of the heuristic to the actual cost the better

Question 4

Estimating h in A*

Answer 4

How to estimate h
Optimal and complete if the heuristic is admissible
Admissible - the heuristic must never overestimate the cost to reach the goal
H(n) a valid lower bound on cost to the goal

Straight line distance is an admissible heuristic
Will never overestimate the cost to the goal

Question 5

Difference between USC and A*

Answer 5

Both complete and optimal
A* search is directed, USC is undirected