| <<Previous |
Search: Brute Force |
Next>> | |||||
| Introduction
The puzzle The algorithm Program Design
|
Exhaustive Search:
Using a computer, one could use a "brute force"
approach. One could evaluate all the possible solutions. Then,
one could choose the one that took the least number of moves.
However, if the blocks are really scrambled up well, this could take a long while. Suppose this is the starting state:
There are three possible moves:
If we choose the first option, we get:
Now, moving the 5 up again would simply cycle back to the original position. So we ignore that. The other possible move is to move the "1" to the left. Do so, we get: Now we have two possible moves:
A "brute force" approach to searching for a solution could go on exploring nodes like this until it hit a solution. |
A "brute force"
search can be done in two ways:
Depth-first: In a depth first search you expand the starting state to figure out all the possible "next step" states. If none of these is a solution-state, you choose any one of these states and expand it again. Examine these, if none is a solution, choose one arbitrarily and expand that one. One has to make sure that one is not going around in circles. In the fifteen puzzle, at some point one will find that searching depth-first down one particular path either lands one at a solution or back at a node that one has seen before. If you find you have cycled back, you step back and expand an unexpanded node. The problem is: if one hits a solution state one does not know that it is optimal. Breadth-first: In such a search, one examines all nodes that are one operation away from the start node. If none are the solution state, then one expands them and examines all the nodes that are two steps away from the solution state. Then, the nodes that are three steps away, and so on. This way, when you find a solution, you know that there is no quicker way (i.e. no way with less steps). Performance: The problem is that with both these methods one might have to examine a lot of stats before one finds a solution. Trying to solve this on a ordinary home computer could take far longer than an average human, even if the computer finally finds a path that takes a lot fewer steps than the human can figure out. Heuristic: A heuristic is some type of estimate that you make at each node. This is an estimate of the distance from that node to the final goal. If you have a good heuristic, it can help you choose the right nodes to expand in a non-arbitrary manner. This means you don't have to examine as many node. However, how do you guarantee that you fond the optimal solution? After all, the heuristic is an estimate, it may be right...but it may be wrong. |
For more information check out these lecture notes from the UCSD Cognitive Sciences department. | ||||
