Informed Search

Question 1

Uniform Cost Search

Answer 1

• frontier is a priority queue
• a node’s priority is its distance from the initial state

Question 2

What are the performance properties of Uniform Cost Search?

Answer 2

Complete: yes, if step-costs are positive
Optimal: yes, if step-costs are positive
Time: O(b^(1 + [c/e])
Space: O(b^(1 + [c/e])
note: C* = path cost of the optimal solution and e = the smallest step cost for any action

Question 3

A* Search

Answer 3

• frontier is a priority queue
• node’s priority is its evaluation function f(n)
• f(n) = g(n) + h(n)
• h(n) is a heuristic function

Question 4

admissible heuristic

Answer 4

it never over-estimates

Question 5

constistency

Answer 5

later guesses aren’t inconsistent with earlier guesses

Question 6

What are the performance properties of A* search?

Answer 6

Complete: yes, if b is finite and step costs are positive
Optimal: yes, if h(n) is admissible (tree search) or consistent (graph search)
Time: O(c^d)
Space: O(c^d)
note: c = effective branching factor