Page 183 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 9: Search and Control Strategies

9.5 Problem Reduction (AND/OR-Tree Search) Notes

The general shape of all states was the same. They were distinguished by the values of their
internal components. The basic idea here is that a problem is represented as one or more goals
to be solved and a step in the problem solving process is either the immediate solution of one of
these goals or its division into a set of (one hopes) simpler sub goals. The technique in question,
construed in abstract terms, is basically just an exploitation of the idea that for any given goal
there are a set of sub goals, such that satisfying the sub goals satisfies the goal. The process of
decomposing a goal into its sub goals is referred to as goal-reduction. We will start by taking a
very simple case where there is only one way of decomposing a goal into sub goals and therefore
there is no search. To illustrate what this means we will look at the Tower of Hanoi problem.

9.5.1 Problem-Reduction and the Tower of Hanoi

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.
Figure 9.1: State Space for the 3 Disk Tower of Hanoi Problem

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. In Figure 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

LOVELY PROFESSIONAL UNIVERSITY 177