Page 52 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes 4. Producing a possible solution for some problems; this means generating a particular
point in the ............................. .

4.3 Hill Climbing

This is a selection of depth-first (generate and test) search. A feedback is utilized here to decide
on the course of movement in the search space. In the depth-first search, the test function will just
accept or reject a solution. But in hill climbing the test function is offered with a heuristic
function which offers an estimate of how close a known state is to goal state. The hill climbing
test process is as follows:
1. Generally he first proposed solution as performed in depth-first procedure. Observe if it
is a solution. If so quit, else continue.

2. From this solution produce new set of solutions use, some application rules
3. For every element of this set
(i) Apply test function. It is a solution quit.
(ii) Moreover observe whether it is closer to the goal state than the solution already
produced. If yes, keep in mind it else discard it.
4. Take the best element so far produced and use it as the next proposed solution.
This step matches up to move through the problem space in the direction towards the
objective state.
5. Go back to step 2.
At times this procedure may approach to a position, which is not a solution, but from which
there is no move that enhances things. This will occur if we have reached one of the following
three states:

(a) A “local maximum” which is a state improved than all its neighbors, but is not better than
some other states farther away. Local maxim sometimes appears with in sight of a solution.
In such cases they are known as “Foothills”.

(b) A “plateau’’ which is a flat area of the search space, in which adjacent states have the
similar value. On a plateau, it is not probable to verify the best direction in which to move
by making local comparisons.
(c) A “ridge” which is an area in the search that is superior than the surrounding areas, but can
not be looked in a simple move.
To conquer these problems we can:
(a) Back track to some previous nodes and try a different direction. This is a fine manner of
dealing with local maxim.
(b) Make a big jump in some course to a new area in the search. This can be produced by
applying two more rules of the similar rule several times, before testing. This is a good
approach is dealing with plate and ridges.

Example: A search algorithm that tries to locate a route that diminishes the number of
connections utilize the heuristic that the longer the span of the flight, the greater the probability
that it takes the traveler nearer to the target. Thus, the number of connections is diminished. This
is an example of hill climbing in the language of Artificial Intelligence.

46 LOVELY PROFESSIONAL UNIVERSITY