| <<Previous |
Heuristic |
Next>> | |
| Introduction
The puzzle The algorithm Program Design
|
The heuristic estimates the
distance from a state to the solution. The estimate is exactly that, an
estimate. It may be exactly right, or it might be a little pessimistic
or a little optimistic. A good estimate is one that is usually not too
far off from the real thing.
Suppose our heuristic produced an estimate that was sometimes accurate and sometimes optimistic, but was never pessimistic. Such a "non pessimistic" estimate causes us to get to optimal solution states. Non-pessimistic Estimate: Suppose we use our non-pessimistic estimate to decide which path is the most likely one to explore. When we reach a solution-state, we know the real distance from the start to the finish. We also know the current estimates for all the unexplored options. If there is any unexplored option that has an estimate lower than the real solution path, then we know we should explore that further. Suppose the solution we have found is a 10-step solution. And suppose there are three unexplored paths, with estimates of 9, 11 and 14, respectively. If these estimates are not pessimistic, we know that it will take 11 or more steps down the second path and 14 or more steps down the third path. So, we do not have to bother with these two paths. We can "prune" those branches from our search tree. Optimism isn't sufficient. If we simply estimate the distance as 1 step, regardless, that is optimistic. However, we will end up doing an breadth search; the heuristic would be optimistic but useless. |
The Estimate used:
The heuristic I have used is computed like this: look at each block, and calculate the minimum number of moves that would be required to bring it to its final place in the solution state. Do not take account of any intervening blocks. For instance, the '1' should be in the top-left position in the final goal-state. If it is actually in the 3rd column of the second row, then it has to move up at least once (to get to the first row), and it has to move left at least twice (to get to the first column). Add these two distances together and get a total of 3 moves. In fact, it would take more moves, because there would be some moves required to take the other blocks out of the way. This computation of distance to be traveled (assuming a grid-like path), is sometimes referred to as 'Manhattan distance' (as opposed to an 'as the crow flies' distance). We compute this distance for each block. The sum of such distances added across all 15 blocks gives us an optimistic estimate of the total number of moves to get to the desired solution. |
The 15 uses a 4x4 grid. For an example of a program that uses a 3x3 grid (the "8-puzzle") look at this JAR submission. |
