Beam Search Algorithm in Artificial Intelligence | All Imp Points | Heuristic Search Techniques

Summary

This 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

00:00

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

05:01

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

10:03

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

Keywords

💡Beam Search Algorithm

Beam Search Algorithm is a heuristic-based search algorithm that limits the number of nodes stored in memory by keeping only the 'best' options at each step. In the video, it is highlighted as a variation of the Best First Search, where only a specific number of paths, based on a beam value (e.g., 2), are kept for exploration, reducing space complexity. The script explains this algorithm as an efficient way to handle larger search spaces.

💡Heuristic

A heuristic is a technique used in algorithms to make decisions that guide the search towards a goal by estimating which path might be more promising. In Beam Search, the heuristic value helps prioritize paths with lower estimated costs towards the goal. For instance, from node A, paths to B, C, and D are compared using heuristic values to decide which is best to explore further.

💡Best First Search

Best First Search is a search algorithm that explores paths based on the best heuristic value at each step. In the video, it is compared to Beam Search, with the key difference being that Best First Search maintains all possible paths in memory, leading to higher space complexity. The Beam Search algorithm is introduced as a more efficient variant.

💡Space Complexity

Space complexity refers to the amount of memory an algorithm requires as it runs. Beam Search is discussed as an improvement over Best First Search by reducing space complexity, which is controlled through the 'beam width' or 'beam value'. The fewer nodes kept in memory, the lower the space complexity. The video highlights how Beam Search can achieve constant space complexity.

💡Beam Width

Beam width (or beta value) is a parameter in Beam Search that limits how many of the best nodes are kept in memory during the search. If the beam width is 2, only the two best paths are retained, and others are discarded. The video demonstrates how this impacts memory usage and the overall efficiency of the algorithm.

💡Priority Queue

A priority queue is a data structure used in search algorithms to manage nodes based on their priority, typically determined by heuristic values. In the video, the nodes are inserted into a priority queue where they are sorted and the best node (lowest heuristic value) is chosen for further exploration. The Beam Search algorithm simplifies this process by limiting the number of nodes in the queue.

💡Sorting

Sorting refers to the process of ordering nodes based on their heuristic values in the priority queue. The video explains how sorting is used in Best First Search to determine which node should be explored next. In Beam Search, sorting still occurs, but fewer nodes are sorted due to the pruning effect of the beam width, reducing the computational burden.

💡Pruning

Pruning in Beam Search refers to the removal of less promising nodes from the search process based on the beam width. Nodes that don't rank among the top choices are discarded, thus reducing memory usage and improving efficiency. The video emphasizes pruning as a key factor in reducing space complexity, making Beam Search more efficient than Best First Search.

💡Branching Factor

The branching factor represents the number of possible child nodes or states that can be generated from a given node in a search algorithm. The video mentions that Beam Search reduces the effective branching factor by pruning less optimal nodes, which helps manage space complexity. The branching factor plays a crucial role in determining the search's time and space requirements.

💡Hill Climbing Algorithm

Hill Climbing is a search algorithm where only the best option at each step is pursued, similar to a Beam Search with a beam width of 1. The video briefly introduces this concept, explaining that if Beam Search limits the beam value to 1, it behaves like Hill Climbing, where only the most promising node is explored without backtracking.

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