YouTube Transcript:
Lec-11: Best First Search Algorithm | How it Works | All Imp Points(Pros & Cons)

Skip watching entire videos - get the full transcript, search for keywords, and copy with one click.

Video Transcript

Video Summary

Summary

Core Theme

Best First Search (BFS) is an informed search algorithm that uses a heuristic function to prioritize nodes, aiming to find a path to the goal state more efficiently than uninformed search methods by focusing on the most promising options.

Mind Map

Click to expand

Click to explore the full interactive mind map • Zoom, pan, and navigate

Hello friends, welcome to Gate Smashers

In this video we are going to discuss

Best first search algorithm

And in this video we are going to discuss all the important points related to BFS

Which are very important for your competitive exams and also for your college or university level exams

So guys quickly like the video

Subscribe the channel

If you have not still done

And please press the bell button

So that you keep on getting all the notifications

So we will start with best first search algorithm

The first important point is that it comes under the informed search technique

And as it comes in informed

We use heuristic method in this

How to find the heuristic?

What is heuristic?

I have already made a video on this

Even there is already a video on informed and uninformed search technique

Their link is given in the description box

From that videos your base will be formed

Because all these videos are linked

Even I solved the 8 puzzle problem

Without heuristic and with heuristic

So when we solve it with heuristic

Then somewhere we have already used BFS

But how does the algorithm of BFS works

Which is the algorithm

That you will come to know clearly in this video

And all the important points related to BFS

Pros and cons

You will come to know about each and everything in this video

So first of all we will start with the algorithm

Let OPEN be a priority queue

Containing the initial state

Over here first of all you have to concentrate on OPEN

Open and closed

Over here what is written priority queue

OPEN is my priority queue

In which what we have to do

Like normal queue

But what is the priority over here

Over here based on their heuristic value

According to the heuristic value of the node

We are giving them priority

And according to that only we will remove them from queue

And according to that only we will explore them further

So over here loop

If OPEN is empty

Return the failure

Otherwise remove the first node from the open

That is called a node

If node state is goal

Then return the path from initial to node

Else generate all the successors of the node

By seeing it looks like a theoretical concept

And if we will solve this with an example

Then you will come to know clearly that how actually BFS works

Show over here you are given a graph

It is the map of a city

Now over here I want to reach from A to G

A is my start state

And G is goal state

What is this? This is my goal state

Now to reach from A to G

First of all as I told you

What does best first search use

Now over here which heuristic method we are using

How we are calculating heuristic

To calculate that we are using straight line

What we are doing with the help of straight line distance

That is also called a Elucedian distance

What are we finding out with Elucedian distance

We are finding out straight line distance

From A to G from D to G from all the nodes

What is the Elucedian distance what is the straight line distance

That we have found out

And that we have already written over here

Even if you get a question

Then this will be already given

Because how will you find this out in X&Y coordinates

Although this is work of mathematics

It comes in mathematics

But over here you need not calculate

Otherwise you can take X-axis and Y-axis

You can calculate it has a simple formula

X1-Y

((X1-X') +( Y'-Y')^2)^2

Generally we find out in this way

Let's say ((X2-X1)^2 +(Y2-Y1)^2)^2

So we find out X&Y according to these 2 coordinates

I have already given this in the question over here

From A to G, B to G, C to G, D to G all of them

The Euclidian distance, the straight line distance is already given over here

So we have to consider it as heuristic value

Show on basis of heuristic value only

We have to work on best search algorithm

Over here you can see the distance

7, 14, 25

These are not heuristic

This is the cost

That means the cost to go from A to C

Cost to go from B to E

Cost to go from E to H

This is actually giving cost

Best first search totally concentrates on what

On heuristic value

You remember this point

In best first search we concentrate only on what

We have to keep main focus only on heuristic value

According to these values only you have to run this algorithm

So first of all OPEN be a priority queue containing in the initial state

So what is there with me in open

A came first of all

Next loop

If open is empty then return the failure

No we have nodes somewhere

A is there first of all in open

So remove the first node

Whichever first node I have so by default A is the first node

So I have given node to it

I have given it a name node

If node is a goal

Is this my goal state?

No my goal state is G

So what I have to do I have to come in the else part

Simply over here

Generate all the successors of the node

And put newly generated a node in open according to their f value

What is f value over here

We have to put them in the queue according to the heuristic value

We have to remove it on the basis of their priority

So what is the concept of priority

Whose heuristic value is the minimum

That is the best

The concept is very simple

What is the meaning of heuristic somewhere you will calculate distance

Or you find out the cost

The one which has the minimum cost the one which has the minimum distance

That is best for me

So come we will start from A

See who all are connected from A

From A, B is connected, C is connected and D is connected

You can simply see over here

From A, B, C and D are connected

The first of all find out there heuristic value

You don't have to focus on this you have to focus on heuristic value

Then see you are going from A to B, B will take you to the goal state

What is the meaning of this

That you go from A to B, B will take you the goal state

With which heuristic value

With how much cost

See what is the cost to go from B to G? 32

Write it down

From A you go to C, C we will take you to the goal state

With the cost of 25

D will take you to the goal state

With the cost of 35

So what you did generate all the successors of the node

Which is the node? A

Which is the node at this time? A

And put the newly generated node into the OPEN

Then add B, C, D in the queue

But based on according to their F value

That means according to the HN value

See according to HN value

If A was there first of all in the queue

I removed A out

Now which one will go in queue?

First of all C will go

Why? Because cost of C is the minimum

Then B will go

And then D will go

You have to work in a very simple way

Now what you have to do, you have to again remove the first

A is already removed

So now which is the first one

C is first

Then remove C and then again we have to do the same work in loop

Then look these both are already there in the memory

B and D are already there in the memory

But now we have to explore C, based on there heuristic value

Look C is going at E

And C is going at F

Even though C is again going at A also

If you want to make you can make

It has no benefit

But still C is connected with how many

We have written with all

Now see we are going from C to E

And E is taking you to the goal state

With 19 cost

F is taking you the goal state, with 17 cost

A is taking you the goal state

With 40 cost

So which is the minimum from all of them

From all of them minimum is

I'm again telling you, you don't have to explore A

Yes you will not do

Because what we generally do

We have already explored A

So we generally add this into closed list

As we have made open

In the same way there is closed

We have added them in closed queue which have already been explored

So you mainly focus on E and F only

Who is minimum from E and F

So now F will go first

Then E will go

Because F is to be explored first

Then you explore F

See F is taking you, is it taking you? Yes

F is taking you to the goal state

That means it is taking you to G state

And what is the cost to go from G to G? 0

Obviously you have already reached at goal state

Then goal state will take you to goal state

With the cost of obviously zero

So over here in this way my path is being followed

From A to C

From C to F

From F to G

So same we are doing over here also

Over here my goal state has came

If Open is empty return failure

If remove open over here

Node is a goal

Now over here G is my node

Then return the path from initial to the Node

Then what is my path

A, from A I went to D

Sorry from A I went to C

A path that we have made over here

From A we had gone to C

From C we had gone to F

From G we had gone to G

So see this is my final path

So according to the heuristic value

It is taking me in minimum heuristic value

Till goal state

So generally in this way best first search works

So look in uninformed

Now if we will compare this

With uninformed

Or with without heuristic

So in that we use breadth first search

Or we use depth first search

So how that would have worked

From A, first it would have gone to B, C, D

It would explore all the 3 first

Then it would go to the next level

In this we have just explored C

We have saved B and D

In case if it will go ahead and fail

Then I can again go on B

But still we have not explored

And after that look at C

When we reached at C

Then it is taking at E also and F also

Then I did not explore E

But if we use this in without heuristic or in uninformed

Then on next level you have to follow each node of each level

Which we generally do in BFS breadth first search

So that's why its cost or generally what is the space complexity

O(b^m) or many time we call it as O(b^d)

That is b is the branching factor

How many children are there how many nodes are being generated

And d is the depth

Which is exponential time complexity

But the best first search

It generally works on greedy method

Over here we are using kind of greedy method only

We are greedy for the heuristic value

I am greedy for the less heuristic value

I will consider it as my local maximum

And I will explore that only

I will not explore the others

Then obviously my time complexity over here is good

But always remember

That whenever you use best first search with heuristic

It always gives the good solution

It may or may not give optimal solution

There is no guarantee of it

It can give also and it might not give also

Yes it will always give good solution

And you can normally say in best case or in average case

It is much better than the uninformed method

Reason it has exponential time complexity

It has exponential space complexity

But over here normal complexity will be there

Over here polynomial time complexity will be there

But always remember in worst case

BFS also

Same O(b^m) or O(b^d) it can go

That depends on what

On heuristic

If your heuristic is good

If you have calculated heuristic properly

Then it is good

But if your heuristic is bad

Then it can make you follow same like uninformed

Which is exponential time complexity

It is in the same way like if you are roaming in a new city

And you want to go from one place to another

And you do not have any Google map or anything

Then obviously what you will do

Obviously you will use heuristic

What is the meaning of heuristic? You will take information

You will ask someone

If that person tells you correctly

Then it is good

Normally instead of exploring the whole city you will ask and go

Then you will reach quickly

But if the person tells you wrong

Then obviously what will happen

That is a bad heuristic

Then you will require that much time only which is required in uninformed or without heuristic

So in worst case both are same

But you can say in normal case, in average case or in best case

It performs much better than the uninformed heuristic method

So see over here also

If you look just at the cost

If you are working on heuristic

Then you are following this path from A to C

C to F

F to G

What you look carefully

If you considered the normal cost

Just the cost to reach there

Then see how much it is

Without heuristic

14+10=24

+20

But if you go through this

From A to C, from C to E

From E to H

From H to G

Then see what will be the cost

14+8=22

+9=31

+10=41

Which is less then the this cost

So if you take care of both of this

That this cost also and heuristic also

Then there are more chances to get an optimal solution

Which is generally used by A*

Which you will already get in the next video

So this is all for this video

Related to BFS

I have covered all the points over here

Which will help you a lot in your competitive exam or your college or university level exam also

Thank you

Click on any text or timestamp to jump to that moment in the video

Most transcripts ready in under 5 seconds

One-Click Copy125+ LanguagesSearch ContentJump to Timestamps

Paste YouTube URL

Enter any YouTube video link to get the full transcript

Most transcripts ready in under 5 seconds

Get Our Chrome Extension

Get transcripts instantly without leaving YouTube. Install our Chrome extension for one-click access to any video's transcript directly on the watch page.

Add to Chrome — Free

Works with YouTube, Coursera, Udemy and more educational platforms

Get Instant Transcripts: Just Edit the Domain in Your Address Bar!

YouTube

←

→

↻

https://www.youtube.com/watch?v=UF8uR6Z6KLc

YoutubeToText

←

→

↻

https://youtubetotext.net/watch?v=UF8uR6Z6KLc

YouTube TranscriptPreparing your results…

YouTube Transcript:Lec-11: Best First Search Algorithm | How it Works | All Imp Points(Pros & Cons)