Sometimes problems only seem hard to solve. A hard problem may be one that can be reduced to a number of simple problems...and, when each of the simple problems is solved, then the hard problem has been solved. This is the basic intuition behind the method of problem reduction. We will have much more to say about this method of search when we cover problem solving and planning in the second half of the course. At this point, our goal is simply to introduce you to this type of search and illustrate the way in which it differs from state space search.
The typical problem that is used to illustrate problem reduction search is the Tower of Hanoi problem because this problem has a very elegant solution using this method. The story that is typically quoted to describe the Tower of Hanoi problem describes the specific problem faced by the priests of Brahmah. Just in case you didn't decide to read this story, the gist of it is that 64 size ordered disks occupy one of 3 pegs and must be transferred to one of the other pegs. But, only one disk can be moved at a time; and a larger disk may never be placed on a smaller disk.
Rather than deal with the 64 disk problem faced by the priests, we will consider only three disks...the minimum required to make the problem mildly interesting and useful for our purpose here...namely to illustrate problem reduction search. The figure below shows the state space associated with a 3-disk Tower of Hanoi Problem. The problem involves moving from a state where the disks are stacked on one of the pegs and moving them so that they end up stacked on a different peg. In this case, we will consider the state at the top of the figure the starting state. In this case all three disks are on the left-most peg. And we will consider the state at the bottom right to be the goal state. In this state the three disks are now all stacked on the right-most peg.
0 comments:
Post a Comment