Recall — This works better than GBFS because we account for the distance already traveled (g(n)).
In addition to the five components, we use problem-specific knowledge beyond the definition of the problem itself.11. “Informed” just means the algorithm has a sense of direction, like a compass, rather than blindly expanding outwards.
Idea: Use an evaluation function (f(n)) for each node.
Heuristic function h(n): Estimated cost of cheapest path from node n to goal. (h(goal) = 0).
Evaluation Function: f(n) = h(n)
Idea: Avoid expanding paths that are already expensive.
Evaluation Function: f(n) = g(n) + h(n)
Recall — This works better than GBFS because we account for the distance already traveled (g(n)).
Analysis: Complete, Optimal (under finite b and positive step costs). Time is exponential, Space keeps all nodes in memory (runs out of space before time).
Note — Optimally efficient: No other optimal algorithm is guaranteed to expand fewer nodes than A*.
An admissible heuristic never overestimates the cost to reach the goal (it’s optimistic).22. If a heuristic overestimates, A* might avoid a path that is actually optimal, breaking its guarantee. Think of it as “assuming the best-case scenario”.
\boxed{ \text{Admissible: } h(n) \le h^*(n) \quad \forall \quad n } Theorem: If h(n) is admissible, A* using tree-search is optimal.
Why? — Admissible is great for tree search, but graph search can lock you out of optimal paths if you check a node via a suboptimal route first and mark it “explored”.
A heuristic is consistent if, for every node n and every successor n', the estimated cost of reaching the goal from n is no greater than the step cost to n' plus the estimated cost to the goal from n'.
Think of consistency like the triangle inequality: h(n) \le c(n,a,n') + h(n')33. Think of it like the triangle inequality — the direct path is always at most as long as any detour.
Note — Every consistent heuristic is also admissible.
Theorem: If h(n) is consistent, A* using graph-search is optimal.
Effective Branching Factor (b^*): A well designed heuristic should have a value of b^* close to 1.44. b^*=1 means the heuristic points you directly to the goal with no wrong turns.
Domination: h_2 dominates h_1 if h_2(n) \ge h_1(n) for all n. h_2 will expand fewer nodes.
Relaxed Problem: A problem with fewer restrictions on actions.55. This is the most reliable engineering trick for inventing new heuristics for new problems. The exact cost of a solution to a relaxed problem is a great admissible heuristic for the original problem.
If the rule is “A tile can move to an adjacent empty square”, we can relax it to:
“Informed” just means the algorithm has a sense of direction, like a compass, rather than blindly expanding outwards.↩︎
If a heuristic overestimates, A* might avoid a path that is actually optimal, breaking its guarantee. Think of it as “assuming the best-case scenario”.↩︎
Think of it like the triangle inequality — the direct path is always at most as long as any detour.↩︎
b^*=1 means the heuristic points you directly to the goal with no wrong turns.↩︎
This is the most reliable engineering trick for inventing new heuristics for new problems.↩︎