Page 185 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 9: Search and Control Strategies

upper and lower triangles respectively. The middle subproblem corresponds to the move that Notes
links these two triangles of states. Note that this middle subproblem has no further
decomposition. It is a primitive problem that corresponds to moving the large disk from the
first to the third peg. The yellow border is used to depict primitive or terminal subproblems.
The left and right subproblems are not primitive subproblems and they are each decomposed
further. The three subproblems for each of these subproblems are primitive and correspond to
the first three and the last three moves of the solution.
In this example, only AND nodes are shown. An OR node corresponds to the case where one or
more different non-terminal rules are applied to a particular subproblem. For an OR node, at
least one of the OR nodes must be solved in order to solve the (sub)problem.

Note that syntactically a decomposition is simply a set of (partial) state descriptions. (This
definition can be relaxed even further, but that is a rather long story.) Thus, there are very many
possible non-terminal reduction rules that could be defined for this 3 Disk Tower of Hanoi
Problem. The figure above illustrates another possible non-terminal rule for this problem. In
this case, the first subproblem is to move the middle and small sized disks to the right peg. The
second subproblem is to move these disks from the right peg to the middle peg. This corresponds
to moving down the left side of the triangle in the state space above and then moving across to
the right side. Although this involves unnecessary moves, it leads to a valid solution when
coupled with the appropriate further rules of decomposition.

The next figure above illustrates a non-terminal rule for this problem which involves partial
states. Note that the first subproblem specifies as the goal state a situation where the large disk
is on the left peg and no disks are on the large disk. (Of course, our picture can’t express this last
condition since the other two pegs aren’t in our picture at all.) The next subproblem involves a
goal situation where the large disk is now on the left peg and again no disks are on the large
disk.

Notes That there are four states in the state space that satisfy the goal of the first subproblem
and also four that satisfy the goal of the second subproblem. This observation forces us to
recognize that implicit in the use of non-terminal rules in problem reduction is the
assumption that there is a path in the state space that will be discovered when the partial
state descriptions are bound to an appropriate state space.

LOVELY PROFESSIONAL UNIVERSITY 179