YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 05-23 Floyd-Warshall Intro

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. ワーシャル-フロイド法について少し触れます
  2. 60年代初頭に2人の数学者によって考案されました
  3. 動的計画法という概念を用いています
  4. 事実役立ちますが
  5. 本質以上にクールな名前ですね
  6. 実際私も様々な機会に
    動的計画法を活用してきました
  7. しかしそれは単に1つの
  8. アルゴリズムの設計テクニックなのです
  9. プログラミングを動的に変えるというより
  10. テーブルの利用を最適化しているのです
  11. このアルゴリズムについて説明していきます
  12. まずグラフ上のノードに0からn-1まで番号が
    振られていると思ってください
  13. アメコミのデータセットを例に挙げて考えましょう
  14. 登場人物に0からn-1番までの番号を振ります
  15. 簡単ですね
  16. 次のDk正方行列と入力のための集計表のような
  17. 大きなテーブルを与えられたと仮定します
  18. 次の値が入っています
  19. i行とj列の要素には番号が入っておりその番号は
  20. iからjへの最短距離の値です
  21. kより小さい値のノードにだけ移動します
  22. 子供の頃こんなゲームをして遊びました
  23. いろんな色のタイルが敷かれた床で
  24. 例えば青のタイルはワニだから踏まないとか
  25. 決めた色のタイルの上だけ踏んでよいとかです
  26. グラフ上でも同じように考えます
  27. iからjへ移動する時いくつかのノードは
    ピンクだと仮定します
  28. ピンクのノードはkより小さい値なので
    通っても大丈夫です
  29. kより大きい値のノードは通ることはできません
  30. jは到達点なので例外ですが
  31. 間のノードはピンクのものだけです
  32. ピンクだけを通っていくパスはこの場合1つだけです
  33. 踏まれないピンクのノードもあるかもしれませんが
  34. ピンクのノードのみを通る最短の距離を知りたいのです
  35. Kより小さい値のノードです
  36. これらの値がすべて行列に入力されていると仮定します
  37. Θ(n³)個の値がすでに入力されていると仮定します
  38. ここでDk+1という新しい行列を用意することは
  39. 許容されるのでしょうか
  40. この場合はノードkを使うことが許されます
  41. 絶対使わなくてはならないわけではありません
  42. Dk+1はどのように算出すべきでしょうか