Problem solving and search techniques

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

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