5. Search: Optimal, Branch and Bound, A*

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 strategies for finding the shortest path. We discuss branch and bound, which can be refined by using an extended list or an admissible heuristic, or both (known as A*). We end with an example where the heuristic must be consistent.

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

Comments

Coding Bee says:

nice explanation
there are some more videos for students on artificial intelligent in following link


Shivangi Singh says:

Loved the Non- Map example that needs consistency to be factored into the algorithm.

Joe Bowman says:

The lectures are really great for foundational understanding of intelligent systems. Also the sleeping guy from last time who has been wearing the same thing to every lecture wasn't there lmaoo

Vivek Poddar says:




What was Eliot's question?
#MIT

Vivek Poddar says:

https://youtu.be/gGQ-vAmdAOI?t=1951
The late comer in the front row is too tired.

Aleksei Maide says:

He is basically explaining Dijkstra's algorithm with some heuristics added…

Michael Avraamides says:

Excellent lecture as usual. One thing that I'm kind of surprised wasn't mentioned. For A*, instead of adding constraints to the heuristic function, another common approach is to add one simple rule to the extend list:
If you find a node that has already been extended but the new travel distance to that node is shorter than the old travel distance to the node, replace the old path with the new one.

So if you work through the last example with this rule you'll see that when visiting C for the second time, the path to C was shorter so it should replace the previous path to C and you would then find the correct solution.

This is how games handle maps with terrain that result in different travel speeds. So that the shortest distance isn't necessarily the fastest path.

I'm not sure about the math and whether this is slightly less efficient, but I know from experience that it works and that it can be very difficult to come up with a heuristic function to estimate the remaining path that satisfies the second constraint.

12345a says:

40:38 He said 100 was okay as it was less than the actual distance
Can we ever say that actual distance < admissible heuristic ?
And do we measure the actual distance and then look for admissible heuristic ?
Wouldnt that be a waste of time ?

12345a says:

Pause at 38:29
He wrote "Acc dist + admissable height"

Shouldnt it be "acc dist + airline distance" ?

12345a says:

I FEEL LIKE I'M IN MIT fyeah

MrFurano says:

I have watched different online videos (courses from Stanford, Course Era…etc.) on AI. This course is by far the best!

Daniel Owers says:

At the end he shows the example where A* doesnt work. Wouldn't you just make it so that if you find a shorter path to a node that already been covered you swap it in?

Adrian Smith says:

Heh, I'm watching this on my laptop. Such a rebel.

Filip Haglund says:

Ah, yes, the famous German auto bond!

pratik khadtale says:

how to calculate airline path for writing a program

Josh Benner says:

When he explains consistency, couldn't you use a check for your extended list where instead of checking if a node has already been reached, instead take whichever repeat is the shortest? Therefore although he reaches C through S-B-C and therefore he was hosed when he tried S-A-C, it'd instead take S-A-C because if there's a way between S & C that is less than the others you'd use that path

Tarek Aloui says:

Guys 44:35 ! I couldn't understand : either the situation we're solving is a map or not, the heuristic still doesn't give a value less than the actual distance, then why is the professor considering it admissible (tho it doesn't satisfy the admissibility rule ) ??

Lakshya Sethi says:

Great lecture. Simulations help a lot to paint a picture about how algorithms work in real scenarios.
I had a little problem with understanding consistency just by reading the book, but this video cleared all my doubts.
Thanks a lot!

Abhishek Bhan says:

Wouldn't BFS give us shortest path as well?

vincy striling says:

WHY NO LAPTOPS

xXxBladeStormxXx says:

I wish you guys would have posted the homework(lab) solutions as well.

Write a comment

*