English subtitles

← U2 17

Get Embed Code
2 Languages

Showing Revision 2 created 05/24/2016 by Udacity Robot.

  1. And the answer is no, we're not done yet. We have reached a goal state.
  2. We put a path onto the frontier that reaches the goal of Bucharest, but we haven't popped that path off the frontier.
  3. And uniform cost search continues to search until we pop it off the frontier.
  4. We continue looking to see if there's a better path that also reaches the goal.
  5. So let's see. I forgot to say Thagoras is explored, so let's continue.
  6. Let's take the cheapest path on the frontier and expand that.
  7. The cheapest path is this, 146. We'll expand that, get another path into (Sibiyu).
  8. That's a worse path than we had before, so we'll drop it.
  9. Then let's see what's next. Looking on the frontier, the cheapest now is here at 299.
  10. We'll expand that. We get a path of cost 374.
  11. Put that on the frontier. Now let's go again.
  12. Now the cheapest path is over here at 317.
  13. We'll mark that as explored and add two more paths--one here that's a worse path, so it gets dropped.
  14. And one path that also reaches the goal, and that has a total cost of 418.
  15. So that just shows it's a good thing we waited, a good thing we didn't stop when we found the first path to the goal,
  16. because now this second path found is actually cheaper than the first path found.
  17. But we're not going to stop here because we still haven't popped off a path that reaches the goal.
  18. So we'll continue. What's next? Now the cheapest path on the frontier is here at 366.
  19. We expand that, and we get paths that are worse paths to points we've already seen before.
  20. So nothing new goes on the frontier. Next, the cheapest path on the frontier is at 374.
  21. Again, expanding that leads nothing useful. Only worse paths than we've seen before.
  22. And now finally, the cheapest path on the frontier is this 418 path to Bucharest,
  23. so we pop that off, and now we reach the goal, and now we stop.
  24. So even though we found the 460 path first, we don't stop there because there might be another path
  25. that also reaches the goal that's cheaper. We keep on going until we popped a path off of the frontier that reaches the goal,
  26. and that's why uniform cost search is guaranteed to find the cheapest path to the goal.