4. Search: Depth-First, Hill Climbing, Beam

Share it with your friends Like

Thanks! Share it with your friends!

Close

MIT 6.034 Artificial Intelligence, Fall 2010
View the complete course: http://ocw.mit.edu/6-034F10
Instructor: Patrick Winston

This lecture covers algorithms for depth-first and breadth-first search, followed by several refinements: keeping track of nodes already considered, hill climbing, and beam search. We end with a brief discussion of commonsense vs. reflective knowledge.

License: Creative Commons BY-NC-SA
More information at http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

Comments

gaurav sharma says:

which software was that

Andy says:

18:52 Doesn't DFS use a stack and BFS use a queue?

Mehul Sharma says:

9:42. Isn't the backtracking idea contrary to the rule of not biting one's tail ?

TheRedstoneTaco says:

So a beam search with a width of 1 is hill climbing?

Tuan Nguyen Anh says:

I don't really get the last problem (the contour problem) of Hill Climbing. Can anyone explain it for me? Thanks in advance.

muhammad rizwan says:

Thanks for sharing

Billy Willy says:

He kept comparing the superior way our eyes finds the path to the goal (G) with the inefficient methodology employed in a few of the search algorithms. But the comparison is silly, imo. We can SEE the goal (G) plus many of the connecting paths at once from our privileged overview. However, if we were in the midst of a large, complex hedge maze and we couldn't see (G), we would operate in a similar fashion to the variants of the depth search, assuming we have a way of identifying the maze's branch points.

12345a says:

39:05
I dont get the 2nd drawback of Hill climbing
He said telephone pole problem
what is that ?

miftah Ihsan says:

what program does he use in the video?

Rahul Dev Mishra says:

Beam Search: At 32:24, how is Node B connected to Node G ? There is no path drawn from B to G on the map ?

Rahul Dev Mishra says:

Hill Climbing Search: At 27:53 why does the instructor say that Node B is closer to the goal than A? From the route map, given the weights, I understand that A is just 8 units away from goal i.e S -> A -> D -> G = 11 units and via node B it is S -> B -> A -> D -> G = 17 units. So why would hill climbing search take the node B path ?

Gorev Minzis says:

Helped me understand a lot thanks!

Although, at 16:55, on enqueueing the paths in the front of the queue, doesn't that violate the FIFO property of a queue?

Juan Manuel Correa Caicedo says:

This is soooo great, thanks for sharing <3 <3 <3

malhar jajoo says:

Why would you need a queue in Depth First search ? Doesn't the recursion stack handle everything ?

Mohamed Benaichouche says:

Minute 13:52 :It doesn'nt mean we are smarter just because we don't serch to the left. We are given an aerial representation of the problem, where as the algorithm is given a point inside the Map, I would compare this to us being inside a labyrinth and asked to find the shortest path to the exit, we would use the same techniques, and we wouldn't find the exist faster.

TCMOREIRA says:

Hill Climbing begins at (26:00)

Jorge Valenzuela says:

It will be really amazing If you can sharing the source code to testing all algorithms. The virtual class is very usefull and very illustrative.

Alexander Black says:

can't believe that guy just took his shoe of 29:00

Epenko says:

First of all: Thank you for there terrific lectures!

Question: with hillclimbing and beam information is used, namely the distance to the target. But to calculate the distance you already know the best path to the target. so how can you know the distance to the target? The only thing you could do is calculate direct distance through Pythagoras, but not using the distances written near the paths. Correct?
But then it should be correctly drawn or presented.

A combination of a system like hill-climbing or beam with a stupid one would give:
a) a superfast answer with a reasonable good path and probably already the best.
b) the best path later on if there is a better solution in the end.

Hemant Panchal says:

oh what i wouldn't give to be in that class just for once….

Artur Baranov says:

https://youtu.be/j1H3jAAGlEA?list=PLnvKubj2-I2LhIibS8TOGC42xsD3-liux&t=2168
this guy is sleeping right in front of professor 😀

orestis tourgelis says:

Great lecture…there could be an improvement on the blackboard switching algorithm : ) maybe 1,2,3 switch to move boards…

Chloe Duan says:

what program was the prof using to simulate the search?

Lawliet L. says:

Outstanding lecture, wonderful teaching skills, I missed best first search here it was mentioned and abstract idea was given, also tree level in beam search should have been a bit more complex to cover all aspects of it, overall very nice explanation, I am lovin it !!!

Lance Bryant says:

Regards optimized search. I take it we take it for granted that we already know the distances to goal from each node for the optimizations. Do beam, and hill climbing searche types still produce faster results if that information is not already available. My guess is they are not applicable in this case because our 'distance' verification itself will have to do extra traversals. Ie making it have more time complexity.

Write a comment

*