Register Now

Login


Lost Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

Login


Register Now

Supported by:
Please register yourself to join the community.

Artificial Intelligence : Hill Climbing (Steepest Ascent)

I believe that my previous blog has provided you a little hint about how the AI works.
In this blog, I will be discussing another heuristic algorithm which has slightly
better performance than Simple Hill Climbing. This algorithm is known as Hill
Climbing (Steepest Ascent).
It is better than the Simple Hill Climbing in a way that it chooses the better node
out of all the nodes and then proceeds, unlike Simple Hill Climbing in which it
chooses the first better node it encounters and then proceeds. Thereby missing the
next nodes which may have higher heuristic values than the current node and leading
to the wrong selection and falling into local maxima.
The algorithm is as follows:
1. Evaluate the initial state. If it also a goal state return it and quit. Otherwise
continue with the initial state as current state.
2. Loop until a solution is found or until a complete iteration produces no change
to the current state:
a) Let SUCC be a state such that any possible successor of current state is
better than SUCC.
b) For each operator that applies to the current state do-
i) Apply the operator and generate a new state.
ii) Evaluate the new state, if it be a goal state then return it & quit.
Else if it is better than SUCC then set SUCC to this state else retain
SUCC as it was.
c) If SUCC is better than the current state thenĀ  set current state to SUCC.
This gif image will clear the concept:
NOTE: This picture is available in the original blog link.
But, even this algorithm has the same disadvantage as Simple Hill Climbing.
It cannot backtrack to its parent node. If it gets trapped in the local
maxima, then nothing can help it to get out of that situation.
As this algorithm involves very slight change, that’s why I am not providing
the example code this time. My previous blog will serve as a reference. Take
this as a challenge and try to implement it. When you implement it yourself,
you will start to get the essence of AI. So best of luck with that.
I hope you find my blogs helpful and keep following me.
Stay tuned and keep coding.
this algorithm.

About the AuthorBeginner

Leave a reply