|
|
f(n) = g(n) + h(n)
where g(n) = actual distance from start state to state n
h(n) = heuristic estimated distance from n to goal
In this case, lowest f is best.
The g(n) component of the evaluation function prevents the search being misled by an (inevitably somewhat inaccurate) heuristic. If the heuristic evaluation h(n) continually returns good evaluations for a path that nevertheless never gets to a goal, the g(n) component will eventually grow to dominate f(n) and the search will be forced back upwards to look for a path that actually works. Algorithm won't get lost down a deep branch going nowhere. Inaccuracy of h(n) is adapted to at run-time.
Luger Fig 4.15
(See goal state at bottom)
e.g. middle choice has 2,8,1 out of place, h(n) = 3, g(n) = 1, f(n) = 4
How this would direct search:
Progression of OPEN and CLOSED:
See
Luger Notes
In step 3,
state e is followed. Its child h has same h(n) value as state f,
but higher f(n) value,
caused by g(n) increasing by 1.
So best-first leaves it on the list and returns to look at f
(step 4).
A heuristic is said to be
admissible
if it provably finds the (joint) shortest path to the goal
where it exists.
Breadth-first search is admissible,
but impractical.
f(n) = g(n) + h(n)
where g(n) = distance from start state to state n along current, known path (haven't yet searched other paths, may find there are multiple different ways to get to n)
h(n) = heuristic estimated distance from n to goal
Consider:
f*(n) = g*(n) + h*(n)
where g*(n) = minimum distance from start state to state n along any path
h*(n) = actual, minimum distance from n to goal along any path
Best-first search with f* is admissible.
But we do not know f*
(it would be an "oracle").
We want f to be as close to f* as possible.
Note that g(n) may be too high - it may not have found the shortest path to n.
For all A algorithms: g(n) ≥ g*(n) for all n.
An A* algorithm is algorithm A where h(n) ≤ h*(n) for all n.
i.e. All states have a worse distance to goal than predicted, or equal,
but never better.
h is always too optimistic.
h(n) = 0 for all n, for example.
Theorem:
All A*
algorithms are admissible.
Proof:
See here.
Roughly:
When A* terminates, it has by definition found a path whose actual cost
is lower than the estimated cost of any path through any unsearched node.
But since those estimates are all optimistic (real cost will be equal or higher),
A* can ignore those nodes.
The trick is to find a non-zero h(n) that will prune the search, but that is still always an underestimate.
The states searched by any A* algorithm will be a subset of the states searched by breadth-first.
Shows that it may not be hard to find a non-zero h(n)
that is still always optimistic.
Then you have an algorithm guaranteed to find optimal path (eventually).
Obviously some h(n)'s are better (weed more states) than others.
Imagine we have two A* heuristics.
h1(n) ≤ h*(n) for all n.
h2(n) ≤ h*(n) for all n.
If h1(n) ≤ h2(n) for all n, we say that heuristic h2 is more informed (i.e. better) than h1
But still need h2(n) ≤ h*(n) for all n.
h1(n) ≤ h2(n) ≤ h*(n) for all nh2 is more informed (better) than h1
One can imagine a sequence of search spaces, each smaller than the previous one, converging on the optimal solution.
Luger Fig 4.28
"Control strategy cost" = Cost of calculating heuristic.
"Rule application cost" = Number of states searched.
LHS - Simple heuristic. Quick to calculate heuristic.
But doesn't prune much - huge space to search.
RHS - Good heuristic. Cuts space.
But calculating heuristic takes time.
Trade-off - Find middle point where computational cost of problem solving is lowest.
On Internet since 1987.
