Hill Climbing Algorithm in Artificial Intelligence with Real Life Examples| Heuristic Search
Summary
TLDRThis 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
🤖 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.
🚩 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.
📊 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.
Mindmap
Keywords
💡Hill Climbing Algorithm
💡Local Search
💡Heuristic Value
💡Greedy Approach
💡Beam Width
💡Local Maximum
💡No Backtracking
💡Plateau or Flat Maximum
💡Ridge
💡Space Complexity
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
تصفح المزيد من مقاطع الفيديو ذات الصلة
Hill Climbing Search Solved Example using Local and Global Heuristic Function by Dr. Mahesh Huddar
Beam Search Algorithm in Artificial Intelligence | All Imp Points | Heuristic Search Techniques
What are Genetic Algorithms?
Algorithm Design | Approximation Algorithm | Vertex Cover Problem #algorithm #approximation
AO* algorithm in AI (artificial intelligence) in HINDI | AO* algorithm with example
Algoritma Greedy - Berpikir Komputasional | Informatika XI
5.0 / 5 (0 votes)