Hill Climbing Algorithm in Artificial Intelligence with Real Life Examples| Heuristic Search

Summary

This video introduces the Simple Hill Climbing algorithm, a local search technique with no global problem knowledge. It explores the greedy approach, where the algorithm keeps moving forward as long as it finds a better state, stopping when no improvements are possible. Key points covered include local maxima, plateaus, and ridges—common problems that can limit progress. Using examples, the video explains how the algorithm selects the best move based on heuristic values and highlights the challenges faced when the algorithm cannot backtrack. It's a valuable resource for students preparing for exams.

Takeaways

• 🔍 Simple hill climbing is a local search algorithm with knowledge limited to its local domain, not the global problem.
• ⚡ The algorithm uses a greedy approach, continuously progressing until the best move is no longer available.
• 🚫 Hill climbing does not allow backtracking, meaning it cannot reverse once it reaches a point where no better move is possible.
• 🌲 The algorithm starts from an initial state and explores new nodes by selecting the best from multiple branches based on their heuristic values.
• 🧮 Beam width in hill climbing is 1, meaning it explores only the best move and forgets the others without saving them in memory.
• 🧗 The algorithm mimics climbing a hill while blindfolded, moving upward as long as a better state is found but stopping once no better state is available.
• 📉 The local maximum problem occurs when the algorithm reaches a peak that is not globally optimal, preventing further improvement.
• ⛰️ A plateau or flat maximum occurs when all neighboring states have the same heuristic value, causing the algorithm to stop due to no clear direction.
• 🧗‍♂️ Ridge is a problem in hill climbing where the algorithm moves in only one direction, even if a better state is available in another direction.
• ❌ Hill climbing is efficient in terms of space complexity since it does not store all states, only the best current state, but this can lead to issues like local maxima.

Q & A

What is the simple hill climbing algorithm?

The simple hill climbing algorithm is a local search algorithm that focuses on finding the best move by comparing the current state with neighboring states, aiming to achieve a better state without knowledge of the global solution.

What does it mean that the simple hill climbing algorithm is a local search algorithm?

It means that the algorithm only has knowledge of its immediate surroundings (local domain) and makes decisions based solely on this information without considering the global view of the problem.

How does the greedy approach work in hill climbing?

In the greedy approach, the algorithm continuously moves towards a better state as long as it finds one. Once no better state is found, the algorithm stops.

Why is backtracking not allowed in the simple hill climbing algorithm?

Backtracking is not allowed because the algorithm does not store previously visited states in memory. Once it moves to a new state, it cannot go back, even if no better state is found.

What is the role of heuristic values in the simple hill climbing algorithm?

Heuristic values guide the algorithm to choose the best option by evaluating the cost or value of each state. The goal is to minimize the heuristic value to find the optimal solution.

What is the 'local maximum' problem in hill climbing?

The local maximum problem occurs when the algorithm reaches a state that seems like the best solution based on its local knowledge, but there may be a better solution (global maximum) beyond its current view.

What is the 'plateau' or 'flat maximum' problem in hill climbing?

The plateau problem arises when the algorithm reaches a state where all neighboring states have the same heuristic value. Since there is no better move, the algorithm cannot decide where to go next and stops.

What is the 'ridge' problem in hill climbing?

The ridge problem occurs when the algorithm is moving in a single direction and reaches a point where a better state exists in a different direction. However, because the algorithm does not change its direction, it cannot reach the better state.

How does space complexity affect the performance of the simple hill climbing algorithm?

The space complexity is low in the simple hill climbing algorithm because it does not store all the explored states in memory. It only keeps track of the current best state, which reduces memory usage.

What is the significance of 'beam width' in the hill climbing algorithm?

In simple hill climbing, the beam width is set to one, meaning the algorithm only explores the best move from the current state and discards other options. This narrow focus helps reduce complexity but limits exploration of alternative solutions.

Outlines

00:00

🤖 Introduction to Simple Hill Climbing Algorithm

This paragraph introduces the Simple Hill Climbing Algorithm and its relevance in competitive exams and university-level assessments. The speaker quickly touches on important points such as its local search nature, greedy approach, and no backtracking. The algorithm explores the best move in each step and continues until it no longer finds a better option. A basic algorithmic structure is provided, with a real-world analogy of blindfolded hill climbing to explain how the algorithm operates by always progressing upwards unless a better state is no longer found.

05:00

🚩 Challenges in Simple Hill Climbing: Local Maximum Problem

This section explains the problem of local maximums in the Simple Hill Climbing algorithm. The speaker compares it to reaching a peak while blindfolded, unaware that there may be a taller peak nearby. Once the local maximum is reached, the algorithm cannot proceed to explore higher hills because it only allows movement toward better states, without backtracking to lower points. The example focuses on how this creates limitations, particularly in scenarios like the Traveling Salesman and 8-Queen problems, where this type of search can miss better solutions due to its narrow focus on the immediate best choice.

10:03

📊 Flat Maximum and Ridge Problems in Simple Hill Climbing

This paragraph delves into two other key issues with Simple Hill Climbing: the flat maximum (or plateau) and ridge problems. A flat maximum occurs when all neighboring states have the same heuristic value, leading the algorithm to a standstill as it cannot choose between equally valued options. The ridge problem is highlighted as a case where the algorithm moves in one direction, unable to switch direction even if a higher point exists nearby. These issues further limit the efficiency of Simple Hill Climbing, making it more prone to getting stuck without finding optimal solutions in certain complex problems.

Keywords

💡Hill Climbing Algorithm

The hill climbing algorithm is a local search technique used in artificial intelligence to find solutions by iteratively improving a single state. It chooses the neighboring state that appears better based on a heuristic, without considering the global landscape. The video explains this algorithm as being 'blindfolded,' where the algorithm only focuses on the local environment to make decisions, such as climbing a hill until a better move is no longer possible.

💡Local Search

Local search refers to an algorithm's ability to focus on a small part of the search space rather than the entire problem domain. The hill climbing algorithm is an example of a local search algorithm because it does not have global knowledge but only makes decisions based on its current state and immediate neighboring states. The script emphasizes this feature by explaining that the algorithm 'works in the local domain.'

💡Heuristic Value

A heuristic value is a measure used to estimate how close a given state is to the goal state. In the video, heuristic values help the algorithm decide which state is better by comparing values and choosing the one with the lower cost. The video uses an example where the current state has a heuristic of 5, and the algorithm compares it with neighboring states to decide the next move.

💡Greedy Approach

The greedy approach refers to the algorithm's behavior of always selecting the best immediate option without considering future consequences. In hill climbing, this means choosing the next state that has the best heuristic value and continuing until no better options are available. The video describes this as a key feature where the algorithm keeps moving 'until it is getting the best move.'

💡Beam Width

Beam width in this context refers to the number of states the algorithm explores at each level of the search tree. In simple hill climbing, the beam width is 1, meaning only one state is considered at each step, which reduces space complexity but can limit the ability to explore multiple possibilities. The video contrasts this with other algorithms that may explore multiple paths.

💡Local Maximum

A local maximum is a point in the search space where the algorithm can no longer find a better neighboring state, even though there may be a better state globally. The video explains this problem using the metaphor of climbing a hill blindfolded and thinking you’ve reached the top, only to realize later that a taller hill exists nearby. This is one of the key limitations of hill climbing.

💡No Backtracking

No backtracking means the algorithm cannot return to a previous state once it has moved to a new one. In hill climbing, this restriction prevents the algorithm from revisiting earlier options, even if they may eventually lead to better solutions. The video highlights this as a limitation, explaining that once the algorithm reaches a local maximum, it cannot explore other paths that require going downhill first.

💡Plateau or Flat Maximum

A plateau, or flat maximum, occurs when the neighboring states all have the same heuristic value, leaving the algorithm with no clear direction to proceed. In the video, this problem is illustrated as a scenario where all neighboring states have the value 5, making it impossible for the algorithm to choose a better move, causing it to stop without finding an optimal solution.

💡Ridge

A ridge is a situation where the algorithm is stuck in a narrow, steep section of the search space, making it hard to move towards a better solution without first descending. The video uses a 3D example to explain how the hill climbing algorithm may fail to reach a higher peak (B) because it is moving in only one direction and cannot go back to explore other paths.

💡Space Complexity

Space complexity refers to the amount of memory the algorithm requires as it runs. The hill climbing algorithm is efficient in terms of space complexity because it only stores the current state and does not keep track of previously explored states. This is a key advantage discussed in the video, as the algorithm 'removes the others' and only focuses on the best state.

Highlights

Simple hill climbing algorithm is a local search algorithm with knowledge of only its local domain.

The algorithm follows a greedy approach and stops when it no longer finds a better move.

Hill climbing algorithm does not allow backtracking; once it moves forward, it cannot revisit previous states.

The algorithm starts from an initial state and selects the best option among multiple branches using heuristic values.

Beam width in hill climbing is one, meaning only the best option is explored while others are discarded.

The primary rule in hill climbing is that if a state is better than the current state, it becomes the new current state.

One major problem in hill climbing is the local maximum issue, where the algorithm gets stuck at a local peak, thinking it has reached the global maximum.

The algorithm works like climbing a hill blindfolded—only knowing if the current step is better than the last one.

Local maximum means the algorithm reaches a stable state where it can't move up or down and assumes it has reached the goal.

In some cases, like the 8-queen or traveling salesman problems, hill climbing is beneficial due to its low space complexity.

Another issue with hill climbing is the plateau or flat maximum, where all neighboring states have the same heuristic value, and no progress can be made.

Ridge is another problem in hill climbing, where the path is upward but the algorithm cannot change direction to reach the global maximum.

Hill climbing only focuses on one best move at a time and doesn't store other possible paths in memory, reducing space complexity.

If the heuristic value of the next state is higher, the algorithm halts as it does not allow moving to worse states.

Backtracking is not allowed in hill climbing, meaning once a state is discarded, the algorithm cannot revisit it, limiting its exploration.

Transcripts

Hello friends, welcome to Gate Smashers

In this video we are going to discuss

Simple hill climbing algorithm

And in this video we are going to discuss all the important points about it

Which will be very beneficial in a competitive exam and in your university and college level exams also

So guys quickly like the video

Subscribe the channel if you have still done

And please press the bell button

So that you can get all the latest notifications

So we will start simple hill climbing algorithm

First important point is

It is a local search algorithm

That means it has got knowledge of its local domain

It does not have any knowledge of the whole global problem

Second is greedy approach

Until it is getting best move it keeps on going

As it will stop getting the best move, it will stop over there

3rd no back tracking

If it is not getting any best move

Then it cannot do backtrack

We will go ahead and discuss this with an example

So over here there is a simple algorithm

Just we're starting with the initial state

We will start any problem form initial state

Until we don't get any solution

So what we are doing we are finding a new operator that is a new node

If we see over here with a simple example

Then this is my initial state

Ahead of which I have 3 states

That means it has 3 branches

Now from these 3 branches

Best under heuristic value based on their cost

Whichever method we are using

Based on there heuristic at we did

We have to find out best from all 3

What is beam width in this ?1

Beam width one means

The one which is best from all these 3

It will only explore this ahead

It will forget others

That means neither we are saving them in the memory

This was the best from them

So we explored this ahead

Now let's say we have these 3 problems ahead

Now these are the 3 branches as we go ahead

Now let's say if this is best from the 3

Then this will be explored ahead

You forget this

This is the simple concept of simple hill climbing algorithm

This line is the most important

If the state is better than the current state

Then it is a new current state

That means you keep on going

Until you are getting better state

Till then you keep on moving ahead

As you stop getting better state

So from there you cannot do backtrack

It works in a very simple way

Because what is its name hill climbing

What is the meaning of hill climbing over here

That you are simply climbing a hill

But blindfolded

Blindfolded means you have tried a cloth on your eyes

And you are climbing a hill

In that what is the best move that we have

Until you are going on a height

Until you are climbing up

Till then you will keep on climbing

If in the middle somewhere you feel that your leg is going downwards

Then you will not go there

Until your leg is going towards up

You keep on following the best move

At one point your leg will be stable

That means neither you can go down nor up

So you will go there and stop

So that is the best path for you

Over here you went till this path

So you have achieved maximum value over here

All the problem over here is which we are going to discuss ahead

So this example I have already written over here just to save the time

Let's see over here this is the problem this is the starting and this is the goal state

Now from starting state I have these 3 options

I can move towards anyone from these 3

But now what I have to check? Heuristic value

Now when I checked the heuristic value, the heuristic value of this state is 4

It's heuristic is 5

It's heuristic is 6

What I have to do is I have to select only one which is the best

That means from these 3

Which is my current state? This

So which one is better than the current state?

You just have to focus on this line

If the state is better than the current state

Then see which is the better from these 3

Is this better? No

This is equal

Is this better? No it's heuristic value is more

We want less

We have to reach to the goal state in the minimum cost

So which one is the better state

This one

Where will it move? Towards this side

It will forget this

Neither we are saving it in memory

Nothing

Now we will move ahead

Now we will again search ahead of this

In this way it is moving

But over here what are the problems

In hill climbing

Problem is local maximum

What is the meaning of local maximum

As I told you right now

That you are going blindfolded

Because you have got knowledge only of local domain

So if you are not blindfolded

Then you will have knowledge of the whole domain

You will come to know that this is a mountain, this is also one mountain

On this mountain I have to climb

You will be able to see the whole view

But over here you are not able to see the complete view

Because you are working on the local search

So what is there in the local domain

You are climbing blindfolded

You're climbing the mountain

What is your best move?

Best movies that until your leg is going towards up direction

That is your best move

So on one point

You will reach on a stable state

So after reaching there neither your legs towards up nor it is towards down

Then what you will feel that you have achieved the goal state

I have reached at the maximum value

So as you removed the blindfold from your eyes

Then you will feel that wow I have achieved the maximum value

But there is a problem

What can be the problem

That there is a another hill

There is another hill whose height or value is more than this

Which can be seen over here in the diagram

But now you cannot achieve this

Why? Because it works until

Until you get better state their current state

So you have already achieved maximum value over here

So now we will not go towards minimum

Because to go over your first you will have to go towards minimum

You will have to go down

So this will not go down

So although if we want to solve travelling salesman problem

Or we want to solve 8 queen problem

It works good in some problems

Because over here the space complexity is less

We are not keeping all the states in the memory

We are just keeping the best state in the memory

We are removing the others

So until you are getting the best

Till then it is good

That means this whole value depends on heuristic

If you are getting good heuristic

Then you keep on moving

But over here local maximum means

You achieved the maximum

But is that globally maximum?

No this is globally maximum

So this will not be achieved

So this is the concept of what

You can say this is a problem called local maximum

So over here also I have shown you this problem

Although this problem is a theoretical part only

What over here I am explaining you with an example that what is the meaning of local maximum

You started from 5 state

You are heuristic is 5

What is the value in current state? 5

So you need better value than this

Obviously better value means

You want to reach in less heuristic, in less cost

So which one will you select from 4,5 and 6 ?

Obviously you will select 4

So you removed this, you did not save this in the memory

This is also not saved in the memory

So my space complexity will be better

Because we are going towards only one best move

Now let's say you explored this ahead

When you explored this state

Now your current state is 4

So now when on this current state you explored next state

This is taking me at 5

That means you are heuristic has increased

So what is my question telling over here

Algorithm is telling if it is better than the current state

Then it is a new current state

So over here a new current state will not be formed

Because heuristic value has increased

So this will stop over here only

That is called a local maximum problem

Then plateau or which is also called as flat maximum

Actually these words are based on hill climbing only

What is the meaning of hill climbing

When you are climbing

Then you got a flat point

Flat point means

Where your neighbors

That means all the neighbors that you have

Let's say value of all is same

5 5 5

Now at this point whom will you select?

When all are giving you the same heuristic value

Then which one will you select from them?

So in this case also it does not give you any answer ahead

So it stops over here

So is also one of the problem

Of plateau or flat maximum problem in the hill climbing

And 3rd is ridge

What is the meaning of Ridge

When you have multiple values

See over here you will be able to see clearly in the 3D diagram

Let's say you are moving in One Direction

You are climbing over here

You keep on climbing

Until you get the best move

And what is the meaning of best move

Until your leg is towards front

It is towards up

That is the best

That means you are climbing the mountain

You reached at 1 point

So you remove your blindfold over here

That means I have reached at the maximum value

Now obviously after this minimum value will start

So you will not go there

But what is the meaning of Ridge

That between A and B, B is above A

Now this B is above A

But now after reaching over here

It will not change the direction

Let us not changing the direction it is moving in One Direction only

So although B point is above it

But you cannot reach on that

Because it is only moving in One Direction

Although it is a special case of local maximum only

So this is all about the hill climbing problem

This is the algorithm and over here I have cleared with an example

What is the problem of local maximum

And how do we actually evaluate it

So when we discussed beam search

In beam search the value of beta

It can be multiple like 2, 3, 4, 5

But in hill climbing

The value of beta is one

You just have to go on one best move

Forget others

You simply skip others

So lets say you will stop at one point

Now we know that it is not taking me towards the best

Then I should go back

But you cannot go back

Because back tracking is not allowed over here

So this is all about the hill climbing algorithm

Thank you