Heuristic Functions for Informed Search

Question 1

What will a good heuristic do?

Answer 1

direct search towards a solution, reducing time costs

Question 2

What does a more effective heuristic do?

Answer 2

expand fewer nodes

Question 3

effective branching factor

Answer 3

number of branches each node expands

Question 4

What is the effective branching factor when the heuristic is perfect?

Answer 4

1

Question 5

heuristic domination

Answer 5

h2(n) ≥ h1(n) for all nodes n
means h2 will never expand more nodes than h1

Question 6

techniques for building admissible heuristics

Answer 6

• relax the problem
• use subproblems to build a pattern database

Question 7

relaxed problems

Answer 7

• create a relaxed version by adding edges but not states in the state space

Question 8

What is the cost of an optimal solution to a relaxed problem?

Answer 8

a consistent and admissible heuristic for the original problem

Question 9

subproblem

Answer 9

an instance of a problem with a simpler goal state

Question 10

what is the simpler goal of a subproblem?

Answer 10

a “necessary but not sufficient” component of the actual goal

Question 11

pattern database

Answer 11

stores the cost to the simpler goal from every subproblem state