Beam Search Algorithm in Artificial Intelligence | All Imp Points | Heuristic Search Techniques
Summary
TLDRThis video provides an in-depth explanation of the Beam Search algorithm, focusing on its importance in managing space complexity compared to the Best First Search algorithm. It highlights how Beam Search narrows down the best options by selecting only a limited number of nodes based on a 'beam width' or 'beta value,' enhancing efficiency. The tutorial also emphasizes key differences, like Beam Search’s potential incompleteness, and introduces related topics such as heuristic values, sorting techniques, and space complexity optimization. The video concludes with a teaser for the next topic, the Hill Climbing algorithm.
Takeaways
- 🤖 Beam search algorithm is a variation of best first search, which focuses on improving space complexity.
- 🧠 Both best first search and beam search are heuristic-based algorithms, helping choose the best path toward the goal state.
- 🔍 Beam search differs from best first search by limiting the number of nodes it keeps in memory, based on a specified beam width (Beta).
- 📉 The beam width (Beta) controls how many of the best nodes are kept, pruning the others to improve efficiency.
- 🧮 Best first search keeps all nodes in memory and sorts them, leading to higher space complexity, while beam search only keeps the best nodes.
- ⏳ Beam search improves space complexity, making it constant due to pruning unnecessary nodes.
- 📊 Sorting methods like merge sort or quick sort are used in beam search, with fewer elements leading to faster sorting.
- 🚧 Beam search sacrifices completeness, as it might prune the optimal path, leading to a potential dead end.
- 🚀 Beam search is faster but might not always provide the optimal solution, as it limits exploration.
- ⛰️ When the beam width is reduced to 1, the beam search algorithm becomes similar to the hill climbing method.
Q & A
What is the primary focus of the beam search algorithm?
-The primary focus of the beam search algorithm is to optimize space complexity by limiting the number of nodes kept in memory, using a beam value to retain only the best nodes at each level.
How is beam search different from best first search?
-Beam search is a variation of best first search. While best first search keeps all nodes in memory and sorts them, beam search limits the number of nodes using a beam value, pruning less optimal nodes to save space.
What is the heuristic value, and how is it used in these search algorithms?
-The heuristic value is an estimated cost from the current node to the goal state. Both beam search and best first search use this value to prioritize nodes, choosing the paths with lower heuristic values for further exploration.
What is the role of the beam width (or beta) in beam search?
-The beam width (or beta) determines how many nodes are retained at each level during the search. For example, if the beam width is 2, the algorithm keeps only the two best nodes based on their heuristic values, discarding the rest.
How does beam search help improve space complexity?
-Beam search improves space complexity by pruning less optimal nodes based on the beam value, keeping only a limited number of nodes in memory. This reduces the overall space required compared to storing all nodes, as in best first search.
Why is beam search not considered a complete algorithm?
-Beam search is not considered a complete algorithm because it prunes nodes based on the beam value. This pruning can lead to removing paths that may later prove optimal, potentially leading to dead ends and missing the best solution.
What happens if the beam value is set to 1?
-If the beam value is set to 1, beam search becomes the hill climbing method. In this case, only the single best node is kept at each level, making the search highly greedy but potentially missing optimal solutions.
How does the time complexity of beam search compare to best first search?
-Beam search reduces the time spent on sorting nodes because fewer nodes are retained in memory. While best first search must sort all explored nodes, beam search sorts only a limited set of nodes, making it more time-efficient in some cases.
What is the trade-off when using beam search compared to best first search?
-The trade-off with beam search is that while it reduces space and time complexity by pruning nodes, it may miss the optimal path due to its incomplete nature. Best first search, on the other hand, explores all paths but at a higher cost in memory and time.
Can beam search provide an optimal solution every time?
-No, beam search does not guarantee an optimal solution every time. Since it prunes nodes, it might discard the optimal path early in the search, leading to suboptimal results in certain cases.
Outlines
🔍 Introduction to Beam Search Algorithm
The video starts with an introduction to the Beam Search Algorithm, emphasizing its importance for competitive and academic exams. The host urges viewers to like, subscribe, and press the bell icon for notifications. The Beam Search Algorithm is introduced as a variation of the Best First Search Algorithm, which is based on heuristics. The speaker explains how the algorithm uses a starting state (A) and explores possible paths (B, C, D) by comparing their heuristic values. The example illustrates how the heuristic guides the search by choosing the path with the lowest cost (C), while keeping other paths (B, D) in memory using a priority queue. The discussion also covers sorting methods to manage the open list, ensuring that the lowest heuristic value is always explored first.
🧠 Memory and Pruning in Beam Search
This section delves deeper into the differences between Best First Search and Beam Search. In Best First Search, all explored nodes are kept in memory and sorted to prioritize the best path. However, Beam Search introduces a beam width, which limits the number of paths stored in memory. For example, if the beam width is 2, only the two best paths are retained, and others are pruned. This reduces space complexity by removing less optimal choices, making Beam Search more space-efficient than Best First Search. The concept of backtracking is also introduced, explaining how the algorithm may need to revisit earlier nodes if the current path leads to a dead end.
📉 Optimizing Space Complexity with Beam Search
This paragraph explains how Beam Search improves space complexity by pruning nodes based on the beam width. With fewer nodes in memory, both space and time complexity are reduced. The speaker discusses how Best First Search has both time and space complexity of O(b^d), but Beam Search reduces space complexity to a constant factor determined by the beam width. The importance of choosing the right beam value (beta) is highlighted, as a smaller beam width reduces memory usage and sorting time. The concept of branching factor and depth is explained in relation to exponential growth in search algorithms, with Beam Search providing an efficient way to manage these challenges.
⚠️ Limitations and Incompleteness of Beam Search
Here, the speaker discusses the limitations of Beam Search. Unlike Best First Search, which explores all nodes and ensures completeness, Beam Search may prune nodes that could lead to the optimal solution. This makes it a non-complete algorithm, meaning it might not always find the best or correct path, especially if a pruned path turns out to be the optimal one. The example illustrates how pruning can lead to dead ends or suboptimal solutions. The paragraph concludes by introducing the idea of Hill Climbing, which will be covered in the next video. The speaker wraps up the discussion by emphasizing the trade-off between space complexity and completeness in Beam Search.
Mindmap
Keywords
💡Beam Search Algorithm
💡Heuristic
💡Best First Search
💡Space Complexity
💡Beam Width
💡Priority Queue
💡Sorting
💡Pruning
💡Branching Factor
💡Hill Climbing Algorithm
Highlights
Introduction to Beam Search algorithm and its importance for competitive and university exams.
Beam Search is a variation of Best First Search algorithm that focuses on optimizing space complexity.
Beam Search and Best First Search both use heuristics to guide the search process.
The concept of heuristic values is explained using an example, where C is the best choice as it has the lowest cost.
Best First Search algorithm uses sorting to manage the priority queue and determine which nodes to explore next.
In Beam Search, nodes that are not explored are removed from the memory, improving space efficiency.
Beam width (or Beta) determines how many nodes are kept in memory; a smaller beam width results in fewer nodes.
For example, with a beam value of 2, only the best two choices are kept in memory while others are discarded.
Beam Search uses a greedy method to explore nodes based on the lowest heuristic value.
The advantage of Beam Search is that it reduces space complexity by limiting the number of nodes stored in memory.
Beam Search can fail to find the optimal solution because it prunes potentially correct paths.
Beam Search has constant space complexity, but its completeness is not guaranteed.
When the beam value is set to 1, Beam Search becomes a Hill Climbing algorithm.
Beam Search is not guaranteed to provide the most optimal solution, as it may prune the correct path during exploration.
In the next video, Hill Climbing algorithm, which is closely related to Beam Search, will be discussed.
Transcripts
Hello friends welcome to Gate Smashers
In this video we are going to discuss
Beam search algorithm
And in this video related to beam search algorithm
We are going to discuss all the important points
Which in your competitive exams
Or for your college or university level exams also they will be very helpful
So guys quickly like the video
Subscribe the channel if you have still not done
And please press the bell button
So that you can get all the latest notifications
So we will start beam search algorithm
First of all
Beam search algorithm takes care related to what
Related to space complexity
As we had discussed in the last video
Best first algorithm
And best first search algorithm
Or if we talk about beam search algorithm
Both are based on heuristic
In best first search
We had discussed same example over here
In this example I have made some changes
I have added an extra edge
So that you can understand it with more clarity
So if we apply best first search over here
Which we have seen in the last video
If you have not checked that video then definitely check it once
Because this beam search is variation of best first search only
It is modified a bit
And we have given it name of a new algorithm
That is beam search algorithm
What is that change
Which was not there in best first search
We are actually going to discuss that change in this video
So as over here we have starting state A
And goal state is G
So if A is my starting state
Then how many choices I have from A
Either I can go from A to B
Or I can go to C
Or I can go to D
I have 3 choices over here
From A you can go to B,C or D
And what do we check over here?
Heuristic value
What is the meaning of heuristic value?
That B is taking me to the goal state, with 32 cost
B is taking me with 32 cost
We have already calculated this heuristic value
I had told you in the last video that how we had calculated
That is called a straight distance
Over here we have done straight line distance calculation
C is taking me to the goal state with the cost of 25
D is taking to the goal state with the cost of 35
And what do we apply in breadth first search
The one which will be having minimum heuristic
Whose heuristic value will be the best
What is the meaning of best, the minimum the value the best the answer
So which is the minimum value over here? C
So C is taking me in the minimum cost to the goal state
So I will explore C ahead
The concept is very simple
Of best search algorithm
Because the name itself indicates best search
So if over here we compare ahead of C
Then what we will do about B&D
We keep B&D in the memory
And when we maintain priority queue how we do that
First of all A came
We removed A
After that we explored B, C&D
Now which is the minimum from them
C so which is after C
After C we have B
And which is there after B
D
What you have applied over here
Over here we have used sorting
We have used sorting method over here
So that I can come to know which is the minimum
So that I will remove that one first from the priority queue
This is called a open list
So to remove from open list I have applied sorting algorithm over here
Now I will remove C from here
And I will further explore C
What about B and D
B&D are still there in the memory
That means they are already there in the queue
Now what will I do I will go on C, so when I went on C
Then what option do I have from C
From C I have option
Either I can go to D
Or I can go to F
I have F option from C
I have option of E
Or have option of A from C
So there is no need to again go to A from C
Because you have already came from A to C
And you have already explored A
So if you want to make C to A then you can make it
But there is no benefit of this
Because A is already explored
So from open list we will put it into closed list
The meaning of closed list is those that are already explored
You put across on them and you are not going to explore them again
In case I take these 3 options and go ahead
So how will these 3 options take me
D is taking me in 35 cost
F is taking me in 17 cost
And E is taking me in 19 cost
So again what will I do I added these 3 in priority queue
First of all we will put F
Then I will put E
Then I will put D
D is already there
And after that I will compare these 4
I will compare value of all 4
We will again sort them
And after sorting I will come to know
That the value of F is the minimum
So F will come ahead in these 4
So that I can further explore F
This is the simple concept
Of best first search algorithm
But over here what you need to understand actually is
Over here you have to understand the first important point
The node that you are not exploring
You are keeping them also in the memory
You are keeping them also in the memory and when you are doing sorting
At that time they are participating
Obviously if they are in the memory then you have to make them participate overall
Because the best first search
It makes a global list and goes on
Global list means
All those you have explored till now
All the names that you have written till now
That all are there in the open list or in the open priority queue
But what does beam search tells
Beam search is telling why you are keeping all these elements in the priority queue
Why you are keeping all these in priority queue
Just based on some beam value
You will be given beam value according to the question
Let's say if I talk over here beam width
If I give you beam with or Beta value as 2
Sometimes it is called as beta sometimes it is written as n
Based on the beam value let's see if I give you beam value is 2
Then what is the meaning of 2
That we have to keep best 2
Remove others
Like you started the journey from A
You had 3 options B, C and D
You came to know that from these 3 C is better
After that B is better
After that D is better
If you are beam search value is 2
That means you need not keep all the choices
You keep only best 2 from all the choices
That is the simple point
So 2 best means you can keep C and B
That means you can explore C
Even if you want B
If in case C will take me in future to a dead end
Obviously we are using kind of greedy method
So the one which I find the best that yes I can follow this path
This is the minimum
You went on that
Then you went ahead and asked if you are travelling in any city
You don't know anything about that city
You don't have any map
Then you are asking someone going ahead
So in case if you get some wrong heuristic
If someone is telling you a wrong way
Then obviously somewhere you can go on a dead end also
We are not going in this example
But somewhere you can also go on a dead end state
So in that case you will have to backtrack
You will have to go to a further state
Then it is possible that you have to also Explore B
But what is beam search telling
That you keep just best 2
Remove others
That means remove D from here
You don't have to explore D
You don't have to put D into the list
The concept is very simple
Now let's say that you explored C
You have kept B into the memory
You explored C
You have option D, F and E
Let's suppose
We have already removed D from here
But just for example if we consider it
So again what value is given over here 2
So 2 means, the 2 best heuristics
Keep them and remove the others
What will happen due to this
Your space complexity will be better
Because BFS the best first search algorithm was there
In best first search time complexity was O(b^d)
And space complexity was O(b^d)
What is b it is a branching factor
Branching factor means if it is my starting node
We explored them from starting node
After exploring them again I explored them
All of them and this is your branching value
And the more depth you will go
It will become an exponential complexity
Time also in space also
So what benefit you are getting from beam
That from starting state if you explored further states
So now based on the beam value
Beam value is 2
So you take 2 best
Remove others
That means you don't have to keep them into the memory
Now let's say you explored them
Then further there are multiple options
Again you have to take 2 best
Let's say these 2 are best
Remove others
So obviously what will be better than that
Due to this your space complexity will be better
So you can guess yourself how much will be the space complexity
Space complexity will be constant
Because all the values
The value of beta will be less
That much more nodes you are pruning that means you are removing
So by default if you will remove the beam search
If we talk about best first search
Then you can see in the case of best first search
By default what is the beam with
Infinite
Because you are not pruning any value
You are keeping all of them in the memory
So the more you will reduce the beam value
That much more nodes you will remove
You will go on pruning
So obviously your space complexity will be better
That is a constant space complexity
Second there will also be difference in time
How? The sorting that you are doing
Obviously for sorting you have multiple method
Merge sort quick sort
There are many complexity methods
So generally the complexity is L(log n)
Sometimes in worst case it also goes up to n^2
But if you consider on an average
That whichever sorting method you are using over here
So when number of nodes will be reduced
Then it will be easy to sort
So that is why beam search is actually used
So for beam search you can say that we have modified best first search a bit
In terms of how many values we are pruning
So how is this value found
Generally this value will be given to us
But somewhere on the backend based on some heuristic values
Based on lot of experiments
I will have to fix this value
Because in this case there can also be problem somewhere
What can be the problem
Best first search takes the global list
It will consider all
It will consider all in the list
So it is a complete algorithm
But, you cannot say beam search as complete
What is the reason
Same example I will be giving
You picked up 2 best
You removed others
Ahead of this also again you picked 2 best
You removed others
It is possible that it can take you ahead to a dead end
And let's say this is taking you to the right path
But you have already pruned the right path
So this completeness is not over here
Yes it can give you a good solution or quality somewhere
But there is no guarantee of always providing an optimal solution
Show in beam search always remember this as the main point
Take care of the space complexity is constant
And somewhere you will be given b value
Over here there is some difference in time because we have to do sorting in less elements
And in this I want to tell the last point over here
If the value of beta
If beam value is given as one
1
If I give you that the value of b is just one
Then we call it as hill climbing method
So we are going to discuss hill climbing algorithm in the next video
That is all about the beam search algo
Thank you
Посмотреть больше похожих видео
5.0 / 5 (0 votes)