More ideas on problem 2.5.
This discusses something I have mentioned only in passing.
A* search is an AI term for a kind of search midway
between Breadth First and Best First. The idea is
to use a priority based on two parts: the the AI lingo,
the priority function is f*, where
f*(b) = g*(b) + h*(b)
where h*(b) is the best evaluation function we can
come up with (say distance to the center), and g*(b)
is the best estimate of the number of steps required
to reach this position.
You may find you reach a position that took you 20
steps through another path that only takes 16 steps,
so g*(b) is just an estimate. But when you find the
better path, you update the stored board to point to
the new, better, solution, which has the effect of
lowering g*(b), and thus f*(b), and thus improving
the priority of the position.
Breadth first amounts to
f*(b) = g*(b)
and Best first amounts to
f*(b) = h*(b)
While Breadth first will find the minimal solution,
it is very slow. A* search also finds the minimal solution,
but does so more rapidly, by focusing on those positions
that lead someplace (have a low h*()). Other combinations
of g and h are possible, trading speed for accuracy.
I find A* search a simple change to make which results
in shorter solutions. (One question: when you update
a board, how do you reflect it's new cost in boards that
descend from that position? Does it matter?)
My resource was the Handbook of AI, but Winston's AI
book also discusses A* search.
- jeff parker
