English subtitles

← 04-22 Improving The Solution Solution

dummy description

Get Embed Code
1 Language

Showing Revision 1 created 05/06/2012 by Amara Bot.

  1. The answer is exhausting the frontier won't work,
  2. because the frontier might be infinite.
  3. In this particular problem, there's only a finite number of states,
  4. but in some problems there might be an infinite number.
  5. If we kept on generating new elements onto the frontier
  6. we may never get to the end.
  7. Doing one step won't do it either.
  8. In this case, if once we found the solution from this 14,
  9. we then gave all the other guys one step, it would work in this case.
  10. But it might be that it took two steps.
  11. Maybe from the 15 there'd be one step that costs 1 and another step that cost 2.
  12. I might not just be one step, so that's not going to work.
  13. The test later part will work.
  14. The reason it works is because now we've guaranteed
  15. that everybody on the frontier is sorted,
  16. and we're pulling off the shortest one first.
  17. If we put it back onto the frontier rather than recognizing immediately that it's a goal,
  18. then since we're pulling them off in order of increasing cost,
  19. then we know that the first one we pull off the frontier that is a goal
  20. that must be the cheapest path to the goal.