Return to Video

06-10 Decision Problems

  • 0:00 - 0:09
    話を簡略化するために簡単な問題でお話ししましょう
  • 0:09 - 0:12
    これまで学んできたように問題に入力します
  • 0:12 - 0:18
    グラフでもリストでも構いません
    解答を得るために処理すると
  • 0:18 - 0:20
    0か1またはイエスかノーになります
  • 0:20 - 0:25
    入力することで二者択一の選択をせまります
  • 0:25 - 0:31
    例としてグラフの連結性を挙げます
  • 0:31 - 0:38
    グラフ上ですべてのノードが接続しているでしょうか
    答えはイエスかノーになりますよね
  • 0:38 - 0:43
    この出力はとても簡潔で0か1になります
  • 0:43 - 0:45
    難しくありませんね
  • 0:45 - 0:51
    たまに0か1を決定するための入力が
    複雑な場合もあります
  • 0:51 - 0:58
    こちらも例ですがグラフとノードv
    ノードuと数字のkを入力します
  • 0:58 - 1:04
    さてvはuにkよりも少ないステップで
    たどり着けるでしょうか
  • 1:04 - 1:07
    また与えられたグラフはツリーでしょうか?
  • 1:07 - 1:12
    もしツリーならサイクルはないので
    ループもありません
  • 1:12 - 1:17
    また他の決定問題ですが
    グラフにブリッジリンクはあるでしょうか
  • 1:17 - 1:22
    エッジを削除した場合はグラフも2つに分かれます
  • 1:22 - 1:28
    グラフと数字のkがあります
    ステップ数がk個離れたペアのノードはありますか?
  • 1:28 - 1:33
    また最短経路はkステップを下回るでしょうか?
  • 1:33 - 1:35
    2部グラフの問題もあります
  • 1:35 - 1:40
    これらは宿題の問題でしたね
  • 1:40 - 1:49
    グラフをエッジで橋渡しすることなく
    2つのノード集合体に分けられるでしょうか?
  • 1:49 - 1:54
    これらはある意味で少々バカげた問題ですね
  • 1:54 - 1:59
    普通ならイエスかノーの答えではなく
  • 1:59 - 2:03
    ペアノードのkステップの数字が
    知りたいわけですからね
  • 2:03 - 2:11
    2部グラフならグラフの分け方はどのようになるのか?
  • 2:11 - 2:15
    vからuまではkステップを下回るのか?
  • 2:15 - 2:17
    それはどのようなパスを取るのか?
  • 2:17 - 2:21
    実際のパスが知りたくて計算していますからね
  • 2:21 - 2:26
    決定問題の面白いところは
  • 2:26 - 2:32
    問題の解釈が問われており
    解釈そのものが解答なのです
  • 2:32 - 2:39
    そして時には多項式を使う問題を導きます
  • 2:39 - 2:46
    もし決定問題が効率的なら
    より興味深い問題につながるでしょう
Title:
06-10 Decision Problems
Video Language:
English
Team:
Udacity
Project:
CS215 - Intro to Algorithms
Duration:
02:47

Japanese subtitles

Revisions