Multi-start Breadth First Search

先日参加したコンテストで以下のような問題が出題されました1

シンプルなグラフがある。それぞれの頂点は最大で100個ほどのグループに分けられている。各頂点から各グループの頂点までの最短距離を求めよ。ただし、頂点の最大数は\(10^{5}\)である。

この問題、コンテスト中には全く手が出ませんでした。それぞれの頂点から幅優先探索を行なって任意のグループに属する頂点に出会う度に記録すれば、目的はまあ達成です。ですが、計算量は軽く見積もっても\(O(N^{2})\)。\(10^{10}\)を超えてしまいます。これは駄目です。

また、制約から考えると、\(10^{5} \times 100\)のテーブルを用意して記録していけばよいように思うのですが、うまく埋めていくことができませんでした。

このときは次のように考えていました。

  • 各頂点から幅優先探索を行う。訪れた頂点のグループ情報を得る。そのグループに初めて訪れているなら、距離を最短距離として記録する(全てのグループに出会ったらその頂点に関しての探索は終了する)

さてコンテスト終了後に色々考えても計算量が落とせなかったので他のコンテスタントの実装を読んでみました。皆幅優先探索を実装しているようですが、探索をグループの数分しか行なっていません...はて?

ポイントは以下でした。

  • 幅優先探索の開始点はグループに属する全頂点とする(!)
  • 幅優先探索を行う。先ほどのようにグループ情報を集めるのではなく、開始点のグループ情報を伝搬するようにする

なるほど、これなら計算量も\(O(MN)\)に落とすことができます。「多点開始幅探索」、とでも呼称できそうな技法です。

以下のような盤面を考えてみます。ここで、グループは4色の色として表しています。また、グラフは表示されているよりも広く存在しています。

f:id:agw:20180604152628p:plain:w350:h350

単点開始幅優先探索では以下のように探索を行います。この緑色の頂点はすぐに、青色と紫色の点を見つけることができますが、赤色の頂点にたどり着くまでには3ステップかかっていることが分かります。

f:id:agw:20180604152739p:plain

赤色の頂点にたどり着いた時点で自分が属する色以外の3色の頂点にたどり着いたのでここで探索を打ち切ることはできますが、最悪\(O(N)\)の探索を\(N\)回繰り返さなければならないので、計算量は依然\(O(N^{2})\)と考えたほうがよいでしょう。

では多点開始幅探索を見て見ましょう。探索は以下のようになされているようです。先ほどの単開始点から行う幅優先探索に比べて、ほとんどの頂点をすぐ網羅することも注目しましょう。

f:id:agw:20180604153135p:plain

一回の探索で訪れる頂点の数は単点開始でも多点開始でも\(N\)ですが、探索を全体で\(N\)回(最大\(10^{5}\)回)やらなければいけないか、\(M\)回(最大100回)でいいのかで総合的な計算量は大きく変わります。ぜひ覚えておきたい技法です。


  1. 少し簡潔な問題としています