bidvertiser01

Friday, July 23, 2010

Hill Climbing Procedure.

HILL CLIMBING PROCEDURE


This is a variety of depth-first (generate - and - test) search. A feedback is used here to decide on the direction of motion in the search space. In the depth-first search, the test function will merely accept or reject a solution. But in hill climbing the test function is provided with a heuristic function which provides an estimate of how close a given state is to goal state. The hill climbing test procedure is as follows :

 

1. General he first proposed solution as done in depth-first procedure. See if it is a solution. If so quit , else continue.



2. From this solution generate new set of solutions use , some application rules



3. For each element of this set



(i) Apply test function. It is a solution quit.



(ii) Else see whether it is closer to the goal state than the solution already generated. If yes, remember it else discard it.



4. Take the best element so far generated and use it as the next proposed solution.



This step corresponds to move through the problem space in the direction



Towards the goal state.



5. Go back to step 2.



Sometimes this procedure may lead to a position, which is not a solution, but from which there is no move that improves things. This will happen if we have reached one of the following three states.



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



(b) A "plateau'' which is a flat area of the search space, in which neighboring states have the same value. On a plateau, it is not possible to determine the best direction in which to move by making local comparisons.



(c) A "ridge" which is an area in the search that is higher than the surrounding areas, but can not be searched in a simple move.



To overcome theses problems we can

(a) Back track to some earlier nodes and try a different direction. This is a good way of dealing with local maxim.



(b) Make a big jump an some direction to a new area in the search. This can be done by applying two more rules of the same rule several times, before testing. This is a good strategy is dealing with plate and ridges.



Hill climbing becomes inefficient in large problem spaces, and when combinatorial explosion occurs. But it is a useful when combined with other methods.

8 comments:

  1. Very precise And helpful..it shall be kind if you elaborate a bit more on the pitflls of hill climbing..
    Regards

    ReplyDelete
  2. Please elaborate on the pitfalls of hill climbing

    ReplyDelete
    Replies
    1. In Hill Climbing Procedure It is the stopping procedure of the search Due to Pit falls. i.e
      a) A "local maximum " which is a state better than all its neighbors , but is not better than some other states farther away. Local maxim sometimes occur with in sight of a solution. In such cases they are called " Foothills".
      (b) A "plateau'' which is a flat area of the search space, in which neighboring states have the same value. On a plateau, it is not possible to determine the best direction in which to move by making local comparisons.
      (c) A "ridge" which is an area in the search that is higher than the surrounding areas, but can not be searched in a simple move.

      To over come these pit falls we follow to backtrack to some earlier nodes and continue the search in some other direction., or restart the search from root by changing the search direction., to overcome above fit falls.


      Delete
  3. really very nice thank you sir .. appreciate your work n help

    ReplyDelete
  4. i think your blog lead me to achieve S grade in this subject

    ReplyDelete
  5. Thank you for the explanation, but I have a question. Isn't a generate-and-test function always used in all different search algorithms (like BFS for example)? What makes hill climbing a variety of DFS and not of any other?
    Thank you.

    ReplyDelete
  6. can u explain further about some other approaches to overcome hill climbing problems. Add another approaches if any!

    ReplyDelete