Best First Search, A* Search, and heuristics (slides4)

Question 1

Best-first search

Answer 1

informed search algorithms use problem-specific knowledge to speed up the search process

use an evaluation function f(n) for each node
-to determine “desirability” of the node
Heuristic functions h(n) is a component of f(n)

-expand node with lowest f(n) first

Question 2

heuristic functions

Answer 2

h(n): estimates the cost of the cheapest path from n to a goal

• depends only on state associated with n
• assume h(n) is non-negative and that it equals 0 at every goal state

Question 3

greedy best first search

Answer 3

expands the node that appears to be closest to goal

Question 4

greedy best first search

Answer 4

completeness: no
time: O(b^m)
- (a good heuristic gives a dramatic improvement)
space: O(b^m) – keeps all nodes in memory
optimality: no

Question 5

A* search

Answer 5

avoid expanding paths that are already expensive

evaluation function f(n) = g(n) + h(n)
g(n) = cost so far to reach n
h(n) = estimated cost from n to goal
f(n) = estimated total cost of path through n to goal

like uniform-cost search with f=g+h instead of g

Question 6

admissibility

Answer 6

heuristic is admissible for every node n, h(n)<=h(n) where h(n) is the true cost to reach the goal state from n

an admissible heuristic never overestimates the cost to reach the goal, e.g. its optimistic
if h(n) is admissible A* using tree search is optimal
-review proof in slides

Question 7

consistent heuristics

Answer 7

a heuristic is consistent if for every node n every successor n’ of n generated by any action a,
h(n) admissibility

Question 8

properties of A*

Answer 8

completeness: yes(unless there are infinitely many nodes with f<= f(G))
time: exponential
space: keeps all nodes in memory
optimal: yes

Question 9

heuristic dominance

Answer 9

if h2(n) and h1(n) are both admissible and h2(n)>= h1(n) for all n, then h2 dominates h1, so h2 is a better heuristic

Question 10

relaxed problems

Answer 10

a problem with fewer restrictions

• a superset of actions are available from each state
• graph of relaxed problem is a supergraph of the original
• cost of an optimal soln may be same or lower