Return to Video

04-22 Improving The Solution Solution

  • 0:00 - 0:03
    The answer is exhausting the frontier won't work,
  • 0:03 - 0:05
    because the frontier might be infinite.
  • 0:05 - 0:08
    In this particular problem, there's only a finite number of states,
  • 0:08 - 0:10
    but in some problems there might be an infinite number.
  • 0:10 - 0:13
    If we kept on generating new elements onto the frontier
  • 0:13 - 0:15
    we may never get to the end.
  • 0:15 - 0:17
    Doing one step won't do it either.
  • 0:17 - 0:21
    In this case, if once we found the solution from this 14,
  • 0:21 - 0:25
    we then gave all the other guys one step, it would work in this case.
  • 0:25 - 0:27
    But it might be that it took two steps.
  • 0:27 - 0:33
    Maybe from the 15 there'd be one step that costs 1 and another step that cost 2.
  • 0:33 - 0:36
    I might not just be one step, so that's not going to work.
  • 0:36 - 0:38
    The test later part will work.
  • 0:38 - 0:42
    The reason it works is because now we've guaranteed
  • 0:42 - 0:44
    that everybody on the frontier is sorted,
  • 0:44 - 0:46
    and we're pulling off the shortest one first.
  • 0:46 - 0:52
    If we put it back onto the frontier rather than recognizing immediately that it's a goal,
  • 0:52 - 0:56
    then since we're pulling them off in order of increasing cost,
  • 0:56 - 1:00
    then we know that the first one we pull off the frontier that is a goal
  • 1:00 -
    that must be the cheapest path to the goal.
Title:
04-22 Improving The Solution Solution
Description:

dummy description

more » « less
Team:
Udacity
Project:
CS212 - Design of Computer Programs
Duration:
01:03
Amara Bot added a translation

English subtitles

Revisions