Page 40 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes
Figure 3.1

1 2 3 2 8 3
8 4 1 6 4
7 6 5 7 5
Goal Initial
The program is to modify the initial configuration into the objective configuration. A solution
to the problem is a suitable sequence of moves, like “move tiles 5 to the right, move tile 7 to the
left, move tile 6 to the down, etc”.

!

Caution To solve a problem by means of a production system, we must state the global
database the rules, and the control strategy.
For the 8 puzzle problem that communicate to these three components. These rudiments are the
problem states, moves and goal. Here each tile configuration is a state. The set of all configuration
in the space of problem declares or the problem space, there are only 3,62,880 different
configurations of the 8 tiles and blank space. Once the problem states have been theoretically
identified, we must build a computer representation, or description of them . This description is
then accessed as the database of a production system. For the 8-puzzle, a straight forward
description is a 3 × 3 array of matrix of numbers. The preliminary global database is this
explanation of the initial problem state.

Did u know? Practically any type of data structure can be accessed to describe states.
A move converts one problem state into another state. The 8-puzzle is suitably interpreted as
having the following for moves. Move bare space (blank) to the left, move blank up, move
blank to the right and move blank down,. These moves are represented by production rules that
function on the state descriptions in the suitable way.
The rules each have prerequisites that must be contented by a state description in order for them
to be valid to that state description. Therefore the precondition for the rule connected with
“move blank up” is derived from the necessity that the blank space must not already be in the
top row.

The problem goal condition generates the basis for the termination condition of the production
system. The control strategy repeatedly use rules to affirm descriptions until a explanation of a
goal state is produced. It also keep track of rules that have been applied so that it can compose
them into sequence displaying the problem solution. A solution to the 8-puzzle problem is
specified in the Figure 3.2.

Example: Depth-First Search traversal for 8-puzzle problem is displayed in Figure 3.2.

34 LOVELY PROFESSIONAL UNIVERSITY