Defining The Problem As A State Space Search

Defining the problem as a state space search
Suppose we have a water jug problem:
You are given two jugs , a 4- gallon one and a 3- gallon one .Neither has any
measuring markers on it . There is a pump that can be used to fill the jugs
with water how can you get exact 2 gallons of water into the 4- gallon jug?
The state space for this problem can be described as of ordered pairs
of integers (x, y) , such that x=0,1,2,3 or 4 and y=0,1,2 or 3 , represents the
number of gallons of water in the 4- gallon jug , and y represents the
quantity of water in the 3- gallon jug . The start state is (0,0) . The goal state
is (2,n) for any value of n ( since the problem does not specify how many
gallons need to be in the 3- gallon jug).
The operators to be used to solve the problem can be described as
shown in Fig bellow. They are represented as rules whose left side are
matched against the current state and whose right sides describe the new
state that results from applying the rule.
1- (x,y) (4,y) fill the 4- gallon jug

If x<4
2- (x,y) (x,3) fill the 3-gallon jug
If x<3
3- (x,y) (x-d,y) pour some water out of the 4- gallon jug
If x>0
4- (x,y) (x-d,y) pour some water out of the 3- gallon jug
If y>0
5-(x,y) (0,y) empty the 4- gallon jug on the ground
If x>0
6-(x,y) (x,0) empty the 3- gallon jug on the ground
If y>0
7- (x,y) (4,y-(4-x)) pour water from the 3- gallon jug into the 4-gallon
If x+y>=4 and y>0 jug until the 4-galoon jug is full
8- (x,y) (x-(3-y),3)) pour water from the 4- gallon jug into the 3-gallon
If x+y>=3 and x>0 jug until the 3-gallon jug is full
9- (x,y) (x+y,0) pour all the water from the 3 -gallon jug into
If x+y<=4 and y>0 the 3-gallon jug
10- (x,y) (0,x+y) pour all the water from the 4 -gallon jug into
If x+y<=3 and x>0 the 3-gallon jug
11- (0,2) (2,0) pour the 2-gallon from the 3 -gallon jug into
the 4-gallon jug
12- (2,y) (0,x) empty the 2 gallon in the 4 gallon on the ground
Production for the water jug problem
Gallons in the Gallons in the Rule Applied

4- gallon Jug 3- gallon
0 0
0 3 2
3 0 9
3 3 2
4 2 7
0 2 5 or 12
2 0 9 or 11
One solution to the water Jug problem.

Problem Solving Consist of:
1- data base:
-current states .
-goal .
2- operations:
manipulate knowledge base ( using rules , frames , nets).
3-control strategy
-control strategy
-what to do next
Objective:
To achieve goal by applying a sequence of operations of operations to the
initial state .
Example(1):
To find a rout from a to z

On the following graph
Data base: initial state, root so far, goal , “I”.
Operations: - go from last node visited to on adjacent node
Control strategy: choose an adjacent node to the last visited of

random.
Example(2):
Eight tile puzzle 2 1 6
Data base: current state of tile 4 8
7 5 3
goal state
1 2 3
8 4
7 6 5
Operations: - move hole up or
move hole down or
move hole left or
move hole right
Control strategy: - choose a direction to move hole at random.
Example(3):
One can visits cities in USA.
A B C D E
A Boston 0 250 1450 1700 300
B New York 250 0 1200 1500 2900
C Miami 1450 1200 0 1600 3300
D Dallas 1700 1500 1600 0 1700
E Sanfrancisco 3000 2900 3300 1700 0
‫المسافر غير محدد بتغير المصروف والمسافة‬
‫اذا كان التحديد باقرب الطرق‬

Search Techniques
Graph search
It is as usually impossible to generate
the whole state space , so a subspace
Generated called the search space.
The search space may grow or
Shrink as processing continues.
Depth First Search

The state space is searched by progressing
drown a branch until the goal is reached
or no farther operation can be applied .
This type of search will find a solution if
the number of possible state generated from
the initial state is finale .
Note : prolog uses a depth first search strategy

to satisfy goals if a branch terminates without
a achieving the goal , then , backtrack to
generates different branch .
The state space is searched by examining all
the nodes at the given level before moving on to the next level .
Example : patient diagnosis , an illness has an associated of symptoms
.the pat out system determine all relevant symptoms and
To conduct a depth first search (algorithm):
1-From a one-element queue consisting of the root node.

2-Until the queue is empty or the goal has been reached, determine if the
first element in the queue is the goal node
2-a if the first element is the goal node, do nothing.
2-b if the first element is not the goal node remove the first element from
the queue and add the first elements children if any to front of the queue.
3-if the goal node has been found, announce success otherwise announce
failure.
Breadth first search

Note: to conduct breadth first search
The some algorithm of depth first search
Except in the end of 2b the
word front of the queue is
replaced by the word back of the queue.
Breadth first search is good
when the no. of a alternative at the choice
points is not too large.
Depth first search is good when the goal
node is not too deep.
Hill climbing
The most problems facing hill climbing are:
1-foothill problem: occurs whenever there are secondary peaks if
it is local, and the user is left with a false source of accomplishment.
2-plateau problem: comes up when there is mostly a flat area
separating the peaks.
Hill climbing
Hill climbing is a variant of generate-and-test in which feedback from
the test procedure is used to help the generator decide which direction to
move in the search space.
-In a pure generate-and-test procedure, the test function responds with

only a Yes or No. But if it the test function is augmented with a heuristic
function that provides an estimate of how close a given state is to a goal
state, The generate procedure can exploit it as show in the algorithm
bellow.
Simple Hill climbing algorithm

1-Evalute the initial state .If it is also a goal
state then return it and quit. Otherwise, continues with the initial state
as the current state.
2-Loop until a solution is found or until there are no new
operation left to be applied in the current state:
A-Select an operator that has not yet been applied to the current
state and apply it to produce new state.
B-Evaluate the new state :
I-It is a goal state, then return it and quit.
II-It is not good state but it is better than the current
state, then make it the current state.
III-It is not better the current state, then continue in the loop.
-The key difference between this algorithm and the one we gave for generate-
and-test is the use of on evaluation
into the control process.
Steepest-Ascent Hill climbing

A useful version on simple hill climbing considers all the moves from the
current state and select the best one as the next state . This method is called
steepest ascent hill climbing or gradient search.
-Notice that this contrasts with basic method in which
The first state that is better than the current state is selected.
Algorithm: steepest-Ascent Hill climbing
1-Evaluate the initial state if it is also a goal
state then return it and quit. Otherwise, continues with the initial state
as the current state.
2-Loop until a solution fund or until a compute Iteration produces no

change to current state.
A-let SUCC be a state such that any possible Successor of the
current state will be better than
SUCC .
B-For each operator that applies to the current state do:
I-apply the operator and generate new state.
II-Evaluate the new state .If it is a goal state, then return it and
quit. IF not, compare it to SUCC. If it is better, leave SUCC alone.
C-If the SUCC is better than current state, then set current state
to SUCC.
Best first search :

We have really discussed two systematic control strategies breadth first
search and depth first search (of several verities) .
In this section , we discussed a new method , best first search , which is a way
of combining the advantages of both depth first search and breadth first
search .
The * A algorithm :
1- From a queue of the partial paths .Let the initial queue consist of
the zero
length ,zero step path from the root node to new here .
2- Until the queue is empty or the goal has been reached determine
if the first path in the queue reaches the goal node:
2.a If the first path reaches the goal node ,do nothing .
2.b If the first path does not reach the goal node:
2.b.1 Remove the first path from the queue .
2.b.2 from new paths from the removed one by extending one step .
2.b.3 Add the new paths to the queue .
2.b.4 Sort the queue by the sum of the cost accumulated so far and the
lower-bound estimate of the cost remaining ,with least-cost paths in
front .
2.b.5 If two or more paths reach a common node, delete all those paths
except the one that reaches the common node with the minimum cost .
3-If the goal node has been found ,announce success otherwise announce
failure .
e(total path length )= D(already traveled)+e(distance remaining ).

Defining The Problem As A State Space Search

Uploaded by

Copyright:

Available Formats

Defining The Problem As A State Space Search

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Defining The Problem As A State Space Search

Uploaded by

Copyright:

Available Formats

Defining the problem as a state space search

Suppose we have a water jug problem:

1- (x,y) (4,y) fill the 4- gallon jug

Production for the water jug problem

Gallons in the Gallons in the Rule Applied

One solution to the water Jug problem.

To find a rout from a to z

Control strategy: choose an adjacent node to the last visited of

‫اذا كان التحديد باقرب الطرق‬

Depth First Search

Note : prolog uses a depth first search strategy

1-From a one-element queue consisting of the root node.

Breadth first search

-In a pure generate-and-test procedure, the test function responds with

Simple Hill climbing algorithm

Steepest-Ascent Hill climbing

2-Loop until a solution fund or until a compute Iteration produces no

Best first search :

e(total path length )= D(already traveled)+e(distance remaining ).

You might also like