Tip:
Highlight text to annotate it
X
Here we give you an intuition as to why
an optimistic heuristic function, h, finds the lowest-cost path.
When A-star ends, it returns a path, p, with estimated cost, c.
It turns out that c is also the actual cost,
because at the goal the h component is 0,
and so the path cost is the total cost as estimated by the function.
Now, all the paths on the front tier
have an estimated cost that's greater than c,
and we know that because the front tier is explored in cheapest-first order.
If h is optimistic, then the estimated cost
is less than the true cost,
so the path p must have a cost that's less than the true cost
of any of the paths on the front tier.
Any paths that go beyond the front tier
must have a cost that's greater than that
because we agree that the step cost is always 0 or more.
So that means that this path, p, must be the minimal cost path.
Now, this argument, I should say, only goes through
as is for tree search.
For graph search the argument is slightly more complicated,
but the general intuitions hold the same.