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
Data base: current state of tile


goal state




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 ).