Informed Search

Question 1

Informed Search

Answer 1

use domain knowledge to guide selection of the best path to continue searching

Question 2

heuristics

Answer 2

informed guesses

Question 3

heuristic function, h(n)

Answer 3

uses domain specific information in some way
is computable from the current state description
estimates - “goodness” of node, closeness of n to goal, cost of minimal cost path from node to goal

Question 4

meanings of different h(n)s

Answer 4

h(n) >= 0 for all nodes; h(n) close to 0 means we think n is close to goal state

Question 5

best-first search

Answer 5

sort nodes in the frontier list by increasing values of an evaluation function, f(n), that incorporates domain-specific information

Question 6

greedy best first search

Answer 6

use as an evaluation function f(n) = h(n) sorting nodes in the frontier by increasing values of f; selects the node to expand that is believed to be the closest (smallest f) to goal node

Question 7

Is greedy best-first complete?

Answer 7

No

Question 8

Is greedy best-first optimal/admissable?

Answer 8

No

Question 9

Algorithm A Search

Answer 9

f(n) = g(n) + h(n) where g(n) is minimum cost path from start to current node; g term adds a BFS component to the evaluation function; nodes in frontier are ranked by the estimated cost of a solution where g(n) is the cost from start to node n, h(n) is the estimated cost from node n to a goal

Question 10

Algorithm A* Search

Answer 10

f(n) = g(n) + h(n) but for all nodes in the search space h(n)

Question 11

What is an admissible heuristic

Answer 11

guarantees that a node on the optimal path cannot look so bad so that it is never considered

Question 12

Is A* complete?

Answer 12

Yes

Question 13

Is A* optimal/admissible?

Answer 13

Yes

Question 14

When should A* stop?

Answer 14

only when a goal is removed from the priority queue (same rule as uniform cost search); a* with h() = 0 is UCS

Question 15

a heuristic is consistent (monotonic) if

Answer 15

for every node n and every successor n’ of n, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n’ plus the estimated cost of reaching the goal from n’
c(n, n’) >= h(n) - h(n’)

Question 16

Why is A* consistent?

Answer 16

When a node is selected for expansion by A*, the optimal path to that node has been found