Skip to content
Hallway
0:00 / 0:00

#a*search#branchandbound#dijkstra

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

MIT OpenCourseWare

6.5M subscribers • 34 videos on Hallway • University channel

YouTube
  • Recommended by 1 person: 1 on Stack Overflow and its sister sites.
  • Presented by Patrick Winston, Professor at MIT
  • May be out of date. Uploaded 12 years ago, in an area where tools change fast.

Intermediate. Assumes working knowledge.

280K views12 years ago1 recommendation

Computer scienceAI and machine learningAlgorithmsComputation and complexity

Patrick Winston explains search algorithms including branch and bound, heuristics, and the A* algorithm.

MIT 6.034 Artificial Intelligence, Fall 2010 View the complete course: 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 ocw.mit.edu/terms More courses at ocw.mit.edu

Why it's here

1 person recommends this

What people say. Recommended as a clear explanation of branch and bound search and its relationship to Dijkstra's algorithm.

Moments people linked to

Sebastian Grafon Stack Overflow • Recommends

I was working through link to this video when at 23:14 I felt that branch & bound with an "extended list" was very similar to Dijkstra's algorithm. Later on in the lecture when the algorithm is again extended with an admissable heuristic, we get A*. That led me into thinking that Dijkstra's algorithm is this very subclass of branch & bound. Is that right? To summarize the lecture: Search algorithms are explored. In particular, they start from a simple branch & bound solution: Until the destination node is visited (extended), visit the node with the shortest distance from the source and add its successors to the priority queue of nodes to visit (sorted by min distance). This doesn't yet detect c…
6View the answer