Breadth First Search - Part 1

  Рет қаралды 83,463

John Levine

John Levine

Күн бұрын

The simplest version of breadth-first search. This version doesn't use a visited set but still finds the shortest path from the start state to a goal state. Part 2 will show you how to use a visited set to potentially make the search more efficient.

Пікірлер: 29
@Jajdjejwi28
@Jajdjejwi28 4 жыл бұрын
I wasted hours at my uni with professors that overcomplicated these search algorithms. You sir saved me big time!
@Amirak254
@Amirak254 Жыл бұрын
I relate
@abhilamsal7185
@abhilamsal7185 4 жыл бұрын
Breadth First Search applies goal test to each node when it is generated rather than when the node is selected for expansion. Therefore, once the algorithm determines shallowest goal node, it stops the search. By following your explaination, the time complexity of BFS comes around in the order of O( b^ (n+1) ). However, if the nodes were to be tested for goal nodes when they were generated rather than when selected for expansion, time complexity becomes O(b ^ n) since whole layer of nodes at depth n would be expanded before goal was detected. b -- branching factor n -- depth of shallowest goal node.
@mariagabrielagarciaarroyo4733
@mariagabrielagarciaarroyo4733 6 жыл бұрын
Loving this channel, super well explained. Thank you!
@nerioamaral4045
@nerioamaral4045 4 жыл бұрын
I love John's Lecture so helpful when it comes to explaining, I would love to have him as my AI Professor. anyways Thanks Dr John
@syntaxerror2144
@syntaxerror2144 9 ай бұрын
Amazing work brother!
@raphaellmsousa
@raphaellmsousa 6 жыл бұрын
Congratulations for your explanation! It was the best one for this topic for me!
@kelvinmonari5512
@kelvinmonari5512 6 ай бұрын
You are the best profesor ever
@limitless1692
@limitless1692 5 жыл бұрын
Wow simple and clear Thank you Sir Much appreciated :)
@johnlevine2909
@johnlevine2909 5 жыл бұрын
You're very welcome!
@benaya6
@benaya6 5 жыл бұрын
the best explanation I found so far...thank you sir
@franchello1105
@franchello1105 6 жыл бұрын
A couple of drawbacks to bring up. Not guaranteed to find the least costed path from S to a Goal State. Also would use a ton of storage to maintain all the current unexpanded nodes. Back in college we had to solve the canibal missionary problem using DFS, because the storage required would grow exponentially if BFS is used.
@mustafaalshaqaq2303
@mustafaalshaqaq2303 2 жыл бұрын
Thanks. This is very helpful.
@yourfellowmuslimyagi2065
@yourfellowmuslimyagi2065 2 жыл бұрын
Excellent explanation
@yourdoom9868
@yourdoom9868 6 жыл бұрын
Thanks for the explanation sir!
@AsomyTraiget
@AsomyTraiget 3 ай бұрын
Thanks
@tzaswit
@tzaswit 3 жыл бұрын
Thank you
@abhirustagi6969
@abhirustagi6969 6 жыл бұрын
thankyou sir!!! very well explained
@hosseinjavoon
@hosseinjavoon 3 жыл бұрын
thank you it was great ❤🌹
@gabethebabe3840
@gabethebabe3840 6 жыл бұрын
WOW great video!
@ruixincheng6201
@ruixincheng6201 5 жыл бұрын
great explanation!!! could you please upload more videos about Neural networks and probability problems? such as Bayes networks,approximate inference and CNN
@fidelhernandez2322
@fidelhernandez2322 6 жыл бұрын
If let's say there is only one goal state (G1). Could I accept G1 as the goal state as soon as I add it to the frontier? By the way thank you for your clear explanation!
@jerushanmoodley2641
@jerushanmoodley2641 4 жыл бұрын
Well explained
@sknganga3633
@sknganga3633 3 жыл бұрын
This guy saving my degree
@hashithakularatne3646
@hashithakularatne3646 2 жыл бұрын
don't we need to add all the visited letters for that path?
@nadaali5
@nadaali5 5 жыл бұрын
thank u
@amirhoxha6231
@amirhoxha6231 Жыл бұрын
smart fella
@kjohari_
@kjohari_ 4 жыл бұрын
Missing your videos sir
@mr.olorinthemaia
@mr.olorinthemaia Жыл бұрын
radu cretulescu trece-ma la examen
Breadth First Search - Part 2
3:05
John Levine
Рет қаралды 45 М.
Depth First Search
7:16
John Levine
Рет қаралды 101 М.
What's in the clown's bag? #clown #angel #bunnypolice
00:19
超人夫妇
Рет қаралды 43 МЛН
Random Emoji Beatbox Challenge #beatbox #tiktok
00:47
BeatboxJCOP
Рет қаралды 32 МЛН
How Strong is Tin Foil? 💪
00:25
Brianna
Рет қаралды 46 МЛН
Lecture 13: Breadth-First Search (BFS)
50:48
MIT OpenCourseWare
Рет қаралды 704 М.
A* Search
12:32
John Levine
Рет қаралды 421 М.
Uniform Cost Search
10:23
John Levine
Рет қаралды 411 М.
Lecture 14: Depth-First Search (DFS), Topological Sort
50:31
MIT OpenCourseWare
Рет қаралды 450 М.
Breadth First Search (BFS): Visualized and Explained
10:41
Reducible
Рет қаралды 213 М.
Depth First Search Algorithm | Graph Theory
10:20
WilliamFiset
Рет қаралды 473 М.
What's in the clown's bag? #clown #angel #bunnypolice
00:19
超人夫妇
Рет қаралды 43 МЛН