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