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.

simple and clear .Keep updating

ReplyDeleteArtificial Intelligence Online Training