Return to Video

04ps-06 Bad Heuristic Solution

  • 0:00 - 0:03
    There was only one correct answer, which is this one over here.
  • 0:03 - 0:09
    The inadmissibility of the heuristic might lead down an exploration of the state space
  • 0:09 - 0:13
    that leads to the goal on a suboptimal path.
  • 0:13 - 0:15
    Let me demonstrate this to you.
  • 0:15 - 0:20
    Here is a world. Suppose our start step is here. Our goal is here.
  • 0:20 - 0:24
    The heuristic is super large for those states over here
  • 0:24 - 0:26
    and smaller around here.
  • 0:26 - 0:30
    The nodes will be expanded following the zeros around here and around here,
  • 0:30 - 0:35
    and the first time the goal is set occurs when we reach the point over here.
  • 0:35 - 0:38
    We never discover the shortcut straight from S to G
  • 0:38 - 0:41
    because of the inadmissible heuristic.
  • 0:41 - 0:44
    That renders point 2 correct, and as a result
  • 0:44 - 0:47
    A-star will not always find the optimal path as I have just proven.
  • 0:47 - 0:51
    Now, it turns out A-star will find the path if one exists.
  • 0:51 - 0:54
    It might find a suboptimal path, but eventually it expands
  • 0:54 - 0:56
    all the nodes that can be reached.
  • 0:56 - 0:59
    If the goal state is among them, it'll succeed to find a path.
  • 0:59 - 1:01
    Therefore this answer here was wrong.
  • 1:01 -
    Of course, none of the above is also a false answer.
タイトル:
04ps-06 Bad Heuristic Solution
概説:

dummy description

more » « less
Team:
Udacity
プロジェクト:
CS373 - Artificial Intelligence
Duration:
01:06
Amara Bot added a translation

English subtitles

改訂