Japanese subtitles

← 02-17 Uniform Cost Search 5

Get Embed Code
2 Languages

Showing Revision 1 created 12/03/2014 by K2480.

  1. 答えはノーです
    ゴールには到達しましたが終了ではありません
  2. ゴールのブカレストに続く経路が
    フロンティア上にありますが
  3. まだフロンティアから経路を削除していません
  4. フロンティアから経路を削除するまで
    均一コスト探索は続くからです
  5. ゴールに続くよりよい経路がないか
    引き続き探します
  6. ファガラシュが既知領域であるということを
    言い忘れました では続けましょう
  7. フロンティアで最小コストの経路を展開しましょう
  8. 最小コスト146の経路を展開し
    シビウへ続く経路を選びます
  9. それは前に通った経路よりも
    高コストなのでやめましょう
  10. 先に進みましょう
    フロンティアで最小コストは299です
  11. ここを展開すると
    この経路のコストは374となります
  12. フロンティアに加えて次へ進みます
  13. 次の最小コストは317です
  14. ここに探索済み領域として2つの経路を加えますが
    こちらは高コストなのでつぶします
  15. もう1つゴールに続く経路の合計コストは418です
  16. 最初にゴールへ到達したあとに
    諦めずに探し続けたかいがありましたね
  17. なぜならこの経路は
    最初に見つけた経路よりも低コストなのです
  18. ただしゴールへの経路がまだ残っているので
    ここで終了ではありません
  19. 次の最小コストは366です
  20. ここで展開し
    これまでの高コストな道を除去します
  21. 新しいフロンティアはありません
    次の最小コストは374です
  22. ここで展開してもいい選択ではありません
  23. ここで先ほどの418の経路が
    ブカレストへの最小コストと確定しました
  24. この経路を削除して
    ゴールへ到着して終了となります
  25. 当初は460の経路を見つけたにもかかわらず
    より低コストな経路を求め探索を続けてきました
  26. ゴールへ続く経路を
    フロンティアから削除するまで続けるのです
  27. これこそ均一コスト探索が最小コストで
    ゴールへ到達できる経路を導き出せる理由です