Heuristics

Question 1

Why is consistency necessary?

Answer 1

To prove the f(n) never decreased because of shortcuts

Question 2

How to fix generic search to handle shortcuts?

Answer 2

• use backpointers to update parent in case of shortcut
• recompute g and resort open by tracing back new path

Question 3

Effective Branching Factor

Answer 3

How much the algorithm branches on way to find goal. Way of characterizing how helpful a heuristic is.

Question 4

Problem Relaxation

Answer 4

Adding more edges/paths to a problem as to have fewer constraints.
Relaxed problem has same state space just with additional costs, so relaxed solution cost is guaranteed to be an admissible heuristic for original problem.

Question 5

Composite Heuristics

Answer 5

Combination of set of admissible, consistent heuristics that are non-dominated

Question 6

Disjoint Pattern Databased

Answer 6

Splitting problem into disjoint subproblems and adding together their cost