04.2 Heuristics and Admissibility

Heuristic

educated guess of cost-to-go

Admissible

never overestimates

Heuristic

a function h(n) that estimates the cost of reaching the goal state from a given state

Improving the efficiency

heuristic, acts as a guiding principle to prioritize certain search paths over others

Correctness

heuristics do not guarantee _

Computational burden

but provide informed approximates that help reduce the _ _ of search

Admissible

never overestimates the actual cost to reach the goal

Remain optimal

this property ensures that search algorithms like A* _ _, since they will not be misled by inflated estimates that could cause them to bypass the best solution

Safeguard, Principle of Optimality

admissibility is therefore a _ ensuring the heuristic’s guidance still respect the _ _ _

Prevents shortcuts to disaster

why admissibility matters (1)

Ensures trust in algorithm

why admissibility matters (2)

Stops wasted detours

why admissibility matters (3)

Easy to compute

designing heuristics (1)

Not overestimate

designing heuristics (2)

Guide search faster than blind

designing heuristics (3)