YouTube

Got a YouTube account?

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

Japanese subtitles

← 07-12 Getting To Point B

Get Embed Code
3 Languages

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

  1. 次はアンドリュー・ゴールドバーグさんです
  2. 彼はMicrosoftリサーチの主席研究員で
  3. 実世界の問題解決のための
    アルゴリズム設計の専門家です
  4. 興味深い研究対象の1つに
  5. 巨大なネットワーク上でマイクロ秒のうちに
    最短経路を探す問題があります
  6. 今回はそのアルゴリズムについて
    教えていただきましょう
  7. 最近主に取り組んでいるのは
  8. 最短経路のアルゴリズムです
  9. 中でも特に力を入れているのが
    GPSナビゲーションアプリです
  10. つまりAからBへの道順ですね
  11. なるほど
  12. この問題の分析自体は昔から研究対象になっていますね
  13. 新たな課題が出てきたそうですね
    その内容と理由は?
  14. GPSナビゲーションが広く普及するに従って
  15. 新たな欠点が浮き彫りになりました
  16. というのもGPSマップの範囲が世界規模に及び
    詳しい情報を載せなくてはならなくなったため
  17. 線形時間で問題をずっと早く処理する
    必要性に迫られたのです
  18. 基本的にBing地図やグーグルマップが
    要求を受け取った時
  19. 地図のすべてを見る時間はありません
  20. ダイクストラ法や線形時間アルゴリズムであっても
    十分に速くはなく
  21. 新しい欠点は解決できないままです
  22. そこでグラフを前処理して
    クエリに答えられるようにします
  23. 理論が機能すれば
    対数の多項式時間で解決することができます
  24. 過去15年ほど多くのリサーチが行われてきました
  25. この研究所だけでなく
    他のところでもたくさん行われてきています
  26. その結果10年前には信じられなかったような
  27. 非常に効果的なアルゴリズムが作られています
  28. そして実際に大陸的なネットワーク上で
    マイクロ秒のうちに
  29. クエリに答えられるようになったのです
  30. 対ごとの最短距離の可能性を
    すべて記憶しておくのではないんですね
  31. はい そのとおりです
  32. 現在大陸規模のネットワークには
    何千万ものノードがあって
  33. いくら最近のディスクが巨大でも
    カバーするには多すぎますからね
  34. 高速道路網と
    ソーシャルネットワーク上のグラフに
  35. 何か関係性があると思いますか?
  36. 最近関連した研究をいろいろと行って
    今発表の準備をしているところです
  37. その研究の際に一般に公開されているネットワークを
    詳しく分析しました
  38. その結果次にお話しする
    ハブラベリング・アルゴリズムが
  39. このようなネットワークで非常に有効だと
    分かったのです
  40. そしてこの種のネットワークでは活用できますが
  41. 例えばスモールワールドネットワークなどでは
    それほど機能しないのです
  42. 興味深いですね
  43. ではこれからそのアルゴリズムについて
  44. 少し教えていただけませんか?
  45. 距離の求め方についてお話しましょう
  46. 2個のノードがあってこの間の距離を知りたいとします
  47. その際このアルゴリズムでは初めにグラフを前処理して
  48. 各ノード用にラベルを計算します
  49. 分かりやすくするため
    グラフは無向グラフとしましょう
  50. ノードのラベルは私たちがハブと呼ぶ他の各ノードと
  51. 特定のノードからそれぞれのハブとまでの距離を
    示したものです
  52. それぞれのノードが持つラベルには
    次に述べる特性を持っています
  53. ノードを2個選ぶと
    ハブの集合は交差することになります
  54. またその2個のノード間の最短経路上に
    交差マークはノードを1個持つことになります
  55. このノードは大事ですよ
  56. なぜならそこから2つのハブまでの距離を合計すると
  57. 最短距離が分かるからです
  58. ではすべてのハブの最短距離が
    記憶されるということですか?
  59. いいえ
    各ノードにハブの集合があり
  60. 各ハブへの距離が分かるのです
  61. 2個のノードはハブを共有する必要があるんですね
  62. 最短経路では共有しています
  63. なるほど そういうことですか
  64. つまりこれは非常に強い特性で
  65. 結局は特定のノードにとって他のすべてのノードが
  66. ハブ上にあればいいのです
  67. 最短経路が保証されるんですね
  68. 特性も残りますがnの順でキューが出されます
  69. 最短経路を探す時に必要なのは値の小さなラベルです
  70. 他の手法よりこの方法の方がそれが可能です
  71. なぜ私たちの手法が
    道路ネットワークで機能するかというと
  72. ラベルを計算できるからです
  73. 例えば西ヨーロッパのグラフに
    1800万のノードがある場合
  74. 約70のラベルを計算できます
  75. たった70ですか?
  76. 頂点はいくつでしたっけ?
    1600万?
  77. 1800万ですよ
  78. その中からたった70だけでいいんですか?
  79. だから速いんですよ
  80. ノードIDによってそれらのハブをソートする場合
  81. 70という大きさのの2つの配列を
    交差させるだけでいいということです
  82. 局所参照性のあるマージソートのように効率がよく
  83. マイクロ秒もかからないうちに処理できます
  84. 驚くほど速いですよ
  85. しかしなかなか簡単に理解できる手法ではありません
  86. ヨーロッパのある交差点を例に考えます
  87. 例えばピカデリーサーカスにしましょうか
  88. いや ピカデリーサーカスの北の角にしましょう
  89. もしあなたがそこにいるとしたら必要な情報は
  90. ヨーロッパの他の70地点への距離だけです
  91. これは何とも驚くことで
  92. そのため皆が実用的ではないと思うのです
  93. もっと多くの地点が必要だと思うでしょう
  94. しかし信じられないことにずっと少なくて済むのです
  95. この考え方を広い範囲で考えてみると
  96. まずは大規模な高速道路の立体交差が思い浮かびます
  97. しかしそれはあまり多くありませんから
  98. 州の高速道路の立体交差やもっとローカルな
  99. 大きな通りの交差点を基本的に想定しています
  100. ただこの手のアルゴリズムのグラフで
    問題になるのは碁盤目です
  101. でも地図の碁盤目は大きくありませんし
  102. たとえ碁盤目があったとしても
  103. 例えばマンハッタンでも通り10本ほどなので
    問題ありません
  104. ブロードウェイが対称性を損ねていますしね
  105. ですから想像するほど大きな問題にはならないのです
  106. 驚くべき手法ですね
  107. 70地点といっても国を越えてカバーするため
  108. 時には切断なども起こると思うのですがいかがですか?
  109. また同じ国の中でも切断されることもあるでしょう
  110. 国外にいる時と国内の同地域にいる時では
  111. 必要なバケット数に違いはありますか?
    遠距離だと少なくていいでしょうか?
  112. あるいはローカルだとより必要でしょうか
  113. その配分はどうなるでしょう
  114. 指数の面で数が増えてもほとんど変わりません
  115. それはすごい
  116. ただどこの国にいるかで変わるということはあります
  117. 人口密度の高いところなら
    特有の事情を考慮しなければなりません
  118. 一方人がいないところにいれば
  119. 経路は1つでいいわけですね