Problems, Problem Spaces, and Search
15
Building a Problem-Solving Program
1. Define the problem precisely.
2. Analyze the problem.
3. Represent the task knowledge.
4. Choose and apply representation and reasoning
techniques.
16
One Legal Chess Move
17
Another Way to Describe Chess Moves
18
A Water Jug Problem
19
Production Rules for the
Water Jug Problem
20
A Water Jug Problem (Contd)
21
One Solution to the
Water Jug Problem
22
To Specify a Problem
1. Define the state space.
2. Specify the initial states.
3. Specify the goal states.
4. Specify the operations.
23
Production Systems
1. A set of rules.
2. Knowledge/databases.
3. A control strategy.
4. A rule applier.
24
Algorithm : Breadth-First Search
1. Create a variable called NODE-LIST and set it to the initial state.
2. Until a goal state is found or NODE-LIST is empty:
(a)Remove the first element from NODE-LIST and call it E. If NODELIST was empty, quit.
(b) For each way that each rule can match the state described in E
do:
(i) Apply the rule to generate a new state,
(ii) If the new state is a goal state, quit and return this state.
(iii) Otherwise, add the new state to the end of NODE-LIST.
25
Two Levels of a Breadth-First
Search Tree
26
Algorithm : Depth-First Search
1. If the initial state is a goal state, quit and return success.
2. Otherwise, do the following until success or failure is signaled:
(a) Generate a successor, E, of the initial state. If there are no more
successors, signal failure.
(b) Call Depth-First Search with E as the initial state.
(c) If success is returned, signal success. Otherwise continue in this loop.
27
A Depth-First Search Tree
28
Problem Characteristics
Is the problem decomposable into a set of (nearly) independent smaller or
easier subproblems?
Can solution steps be ignored or at least undone if they prove unwise?
Is the problems universe predictable?
Is a good solution to the problem obvious without comparison to all other
possible solutions?
Is the desired solution a state of the world or a path to a state?
Is a large amount of knowledge absolutely required to solve the problem, or
is knowledge important only to constrain the search?
Can a computer that is simply given the problem return the solution, or will
the solution of the problem require interaction between the computer and a
person?
30
A Decomposable Problem
31
A Simple Blocks World Problem
32
A Proposed Solution for the
Blocks Problem
33
An Example of the 8-Puzzle
34
Facts about Marcus
1. Marcus was a man.
2. Marcus was a Pompeian.
3. Marcus was born in 40 A.D.
4. All men are mortal.
5. All Pompeians died when the volcano erupted in 79 A.D.
6. No mortal lives longer than 150 years.
7. It is now 1991 A.D.
35
Two Ways of Deciding That Marcus is Dead
36
An Instance of the Traveling Salesman
Problem
37
Two Paths Among the Cities
38
The Four Categories of
Systems
Production
39
A Search Graph for the Water
Jug Problem
40
Algorithm : Check Duplicate Nodes
1. Examine the set of nodes that have been created so far to see if the new node
already exists.
2. If it does not-simply add it to the graph just as for a tree.
3. If it does already exist, then do the following:
(a) Set the node that is being expanded to point to the already existing-node
corresponding to its successor rather than to the new one. The new one can simply
be thrown away.
(b) If you are keeping track of the best (shortest or otherwise least-cost) path to each
node, then check to see if the new path is better or worse than the old one. If worse,
do nothing. If better, record the new path as the correct path to use to get to the
node and propagate the corresponding change in cost down through successor nodes
as necessary.
41
Some Cryptarithmetic Problems
42