mits58のメモ

メモ　参考にしないでください

Widest Path ProblemとMinimax Path Problem

英語版wikiを和訳しただけ、色々調べる（Todo）しまとめる（Todo）

概要

どんな問題？

  • グラフ理論における問題の1つで
    重み付きグラフの2つの指定された頂点間のパスにおいて、
    最小重みの辺の重みが最大なもの    を見つけるという問題
  • Bottleneck Shortest Path Problem（ボトルネック最短路問題）
    Maximum Capacity Path Problem（最大容量パス問題）
    などとも呼ばれることがある
  • パス長さの代わりにボトルネック距離を使うことで、多くの最短経路アルゴリズムを用いてWidest Pathsを計算することが可能（だが、より高速なアルゴリズムあり）

応用例

  • 例えば、インターネットにおけるルータ間の接続関係を表したグラフを考える。このとき、ある辺の重みは2つのルータ間の接続の帯域幅を表す
  • ここにおいて、Widest Path Problemは、可能な最大限の帯域幅を持つ、ある2つのインターネットノード間のパスを見つける問題となる
  • このパスにおける最小の辺重みは、パスの帯域幅や容量と呼ばれる
  • 他にも、選挙方式の1つのシュルツ法において当選者を決定する際や、デジタル画像合成、代謝経路分析、最大フローの計算においても重要な要素の一つとなっている

Minimax Path Problem（最小最大パス問題）

  • Widest Path Problemと類似した問題として、パスに含まれる辺の重みの最大値を最小化するというMinimax Path Problem（最小最大パス問題）がある
  • この応用として運輸計画に関するものがある
  • Widest Path Problemに対する任意のアルゴリズムは、Minimax Path Problemに対するアルゴリズムに変形することができ、逆もしかり
  • どうすればよいかと言うと、アルゴリズムにより行われる重み比較の意味を逆にするか、全ての辺重みを等しく正反対なものに置き換える

無向グラフにおけるWidest Path Problem

  • 無向グラフにおいて、2頂点間のWidest Pathは、グラフにおける最大全域木上に存在し、2頂点間のMinimax Pathは同様に最小全域木上に存在する。[8][9][10]
  • 有向、無向に関わらず任意のグラフにおいて、あるWidest Pathにおける最小重みを持つ辺の重みがわかっている場合、そのWidest Pathを見つける愚直なアルゴリズムが存在する。 ->  その辺の重みより小さい重みを持つ辺を削除した上で、残りの辺をもとに任意のパスをBFSやDFSを用い探索する
  • この観察に基づいた、最大全域木を用いない、無向グラフにおけるWidest s-t pathを見つける線形時間アルゴリズムが存在する
  • このアルゴリズムの主なアイデアとして、グラフにおける中央値の辺重みを用い、先程の線形時間でWidest Pathを探索するアルゴリズムを適用する
  • 続いて、パスが存在する場合、先程の重みより小さな重みの辺を削除し、存在しない場合は、先程の重みより大きな重みの辺を縮約し、結果として得られる小さなグラフに対し再帰する

Minimax Path Problemの画像合成への応用

  • Fernandez, Garfinkel, Arbiol（1998）では、このMinimax Path Problem (Bottleneck Shortest Path) を重複した領域がある複数の画像を組み合わせる、合成航空写真を形作るために用いた
  • Widest Path Problemが適用される部分問題において、 2つの画像はすでに共通座標系に変換されていて、残りの課題は、つなぎ目を選択することである。
  • つまり、2つの画像の1つから、他の画像を分ける曲線を選択すること
  • つなぎ目の片方のピクセルは、画像のうちの1つからコピーされ、つなぎ目のもう一方のピクセルは、もう片方の画像からコピーされる
  • 他の両方の画像におけるピクセルの平均をとる合成方法と異なり、この方法は正しい画像を生成することができる(this produces a valid photographic image of every part of the region being photographed. )
  • グリッドグラフの辺に対する重みを、そのエッジがつなぎ目としてどのくらい視覚的に見えるかの数値量として、これら重みに対するWidest Pathを探索する(They weight the edges of a grid graph by a numeric estimate of how visually apparent a seam across that edge would be, and find a bottleneck shortest path for these weights.）
  • 従来の最短経路ではなくこのパスをつなぎ目として用いることで、他の場所でのより低い視認性のために、画像の一部においてより視認性を高くする犠牲を払うことを可能にすることよりもむしろ、その点すべてにおいて認識が困難なつなぎ目をシステムによって検出することができる(Using this path as the seam, rather than a more conventional shortest path, causes their system to find a seam that is difficult to discern at all of its points, rather than allowing it to trade off greater visibility in one part of the image for lesser visibility elsewhere.[4])
  • グリッドグラフの2つの相対する角の間におけるMinimax Path Problemへの解法を用いることで、2つのpolygonal chainの間のweak Frechet distanceを見つけ ることができる
  • ここで、各グリッドグラフの頂点は、各チェーンから1つずつ、線分の1つのペアを表し、辺の重みは、1つのペアの線分から別の線分へと移動するのに必要なFrechet distanceを表す
  • もし、無向グラフのすべての辺の重みが正であるならば、点間のMinimax距離（Minimax Pathの最大の辺重み）は超距離を形成する
  • このようにして、逆にすべての有限な超距離空間は、Minimax距離からくる
  • 最小全域木から形成されたデータ構造によって、任意の頂点間のMinimax距離を、Cartesian TreeにおけるLCAクエリを用いることで、1つのクエリに付き定数時間で答えることができる
  • Cartesian treeの根は、最小全域木における最大重みの辺を表し、その子は、最大重み辺を削除することによって形成された最小全域木の部分木により、再帰的に形成されたCartesian treeである
  • Cartesian treeの葉は入力グラフの頂点を表し、2つの頂点間のMinimax距離は、Cartesian treeにおける、LCAにあたる頂点の重みに等しい
  • 最小全域木の辺がソートされている時、このCartesian treeは線形時間で形成することができる

有向グラフ

  • 有向グラフにおいて、最大全域木による解法は使用できない
  • 代わりにいくつかの異なるアルゴリズムが知られている
  • 単一始点かつ単一終点のもの、単一終点のもの、全点対のものなどがある

全点対Widest Path Problem

  • 優先順位に基づき投票者が候補者のランク付けを行う双方向選挙における照射決めるためのSchulze法における応用として、全点対Widest Path Problemがある
  • Schulze法は、頂点が候補者で、任意の2頂点が辺により連結されている完全有向グラフを形成する
  • 各辺は、つながっている2人の候補者の間における、勝者から敗者の向きに向き付されていて、そのコンテストのマージンでラベル付けされている
  • 続いて、頂点の全ての対におけるWidest Pathを計算する、そして勝者はその頂点が互いに相対する頂点へのWiderなPathを持つ候補である
  • この方法を用いる選挙の結果はコンドルセ法（全ての点対のコンテストに勝利した候補者は自動的に全体の選挙にも勝利する）からなるが、それは一般的に勝者に選択されてしまうことを許してしまう、コンドール法が失敗するときでさえも
  • Schulze法は、Wikimedia Foundationを含むいくつかの組織において使用されている
  • 投票における応用の一つのような、密な有向グラフにおける、全点対に対するWidest Path幅を計算するために、漸近的に最速の知られている方法として、O(n^(3+ω)/2)の方法がある（ここで、ωは高速行列乗算の指数である）
  • 行列乗算に対する知られている最良のアルゴリズムを用いると、この計算量上界は、O(n^2.688）となる
  • 代わりに、Schulze法の参照実装は、より簡単なO(n^3)のワーシャるフロイドアルゴリズムを変更したものを用いる
  • 疎なグラフに対しては、単一始点のWidest Pathアルゴリズムを繰り返し適用するほうがより効果的である場合がある

単一始点

  • もし辺が重み順にソートされている場合、ダイクストラアルゴリズムを変形したものを用い、指定された始点から他のすべての頂点間のBottleneckを線形時間で計算することができる
  • 従来のダイクストラアルゴリズムにおけるスピードアップの背後にある考え方は、このアルゴリズムによって考慮される順序における、それぞれの頂点におけるボトルネック距離の列が、辺重みに対しソートされた列である単調な部分列であるということ
  • それ故に、ダイクストラアルゴリズムの優先度付きキューは、バケットキューとして実装することができる（1からm[グラフの辺数]で索引付けされた配列で、i番目の要素には順序付けされたi番目の辺の重みのボトルネック距離が含まれている
  • この方法はソートと同じくらい早くWidest Path Problemを解くことができ、例えば辺重みが整数で表現されている場合、m個の整数のリストを整数ソートする際の計算量の上界を適用することができる

単一始点と単一終点

  • BermanとHandler(1987)は、サービス車両と緊急車両は、サービスコールから基地へ戻る際にMinimax Pathを使うべきだと提案した
  • この応用において、車両が戻るのにかかる時間は、他のサービスコールが発生した際の反応時間より重要でない
  • 辺の重みが、アル点における辺から最も遠い可能性のあるサービスコールまでのMinimax Pathを用いることにより、サービスコールを受け取ったあとに、反応車両が到着するまでの、可能性がある最大の遅れを最小化することができる
  • Ullah, Lee and Hasson(2009)は、彼らのモデル内で、代謝ネットワークにおける支配的な反応連鎖をモデリングするために、Maximin Pathを利用した
  • 辺の重みは、対応する代謝反応の自由エネルギーの値である
  • Widest Pathの他の応用として、最大フロー問題に対するFord-Fulkerson algorithmがある
  • フローの残差ネットワークにおける最大容量のパスに沿ってフローを繰り返し増加させることは、最大フローを見つけるために必要な増加数に関するオーダーO(m log U)を与える（ここで、辺の容量は最大でもU(整数)であると仮定される）
  • しかしながら、この分析は正確な最大の容量を持たないパスを見つけることに依存しない、最大値の定数項の範囲内の容量の任意のパスで 十分である
  • この近似アイデアと、Edmonds-Karpアルゴリズムにおける、最短経路増加法を組み合わせることにより、最大フローアルゴリズムがO(mn log U)で動く
  • 入力グラフの辺重みの比較のみを許し、算術演算を許さないような計算モデルにおいても、単一始点・単一終点のMaximum-CapacityパスやMinimaxパスをとても効率良く見つけることが可能である
  • そのアルゴリズムは、最適なパスのボトルネックとなっている辺を含むとして知られている、辺の集合を保つ
  • 最初に、Sをグラフの全てのm辺からなる集合に初期化する
  • アルゴリズムの繰り返しの各々において、Sがほぼ同じ大きさの部分集合の順序付けられた列に分解される
  • この分割における部分集合の数は、O(m)での中央値探索を繰り返すことにより見つかる部分集合間の分割点の全てを選択するという方法で行われる
  • そしてグラフの各辺を、その辺が含まれる部分集合のインデックスにより再重み付けし、その再重み付けされたグラフ上において修正されたDijkstraアルゴリズムを適用する
  • この計算結果に基づき、ボトルネックとなっている辺重みを含む部分集合がどれかを線形時間で決定することができる
  • そしてSを、ボトルネック重みが含まれている部分集合S_iにより置換し、次のループをこの新しい集合Sにおいて始める
  • Sの可能な部分集合の数は、各ステップにおいて指数的に増加するため、反復回数は、反復対数関数（iterated logarithm function）に比例し、O(log* n)である、そして合計の時間はO(m log*n )となる
  • 各辺の重みが整数データ型の時、このアルゴリズムの繰り返しbisectionする部分を、HanとThorupのリスト分割テクニックに置き換えることができ、SをO(√m)のより小さい集合に、1つのステップで分割することができ、全体として線形時間のオーダーになる

ユークリッド空間上の点集合

  • Minimax Path Problemの変種として、ユークリッド空間情の点集合を考慮するものがある
  • 無向グラフの問題として、このユークリッドMinimax Path Problemはユークリッド最小全域木を見つけることにより効率的に解くことができる（この木上の全てのパスはMinimax Pathとなる）
  • しかし、ホップ長を最小化するだけでなく、同じホップ長を持つパスの中で、パスのトート有るの長さを最小化する or 近似的に最小化することも望まれている場合、問題がより複雑になる
  • 近似的な解法としてGeometric Spannerが用いられる
  • 数論において、ガウス素数におけるMinimax PathsのMinimax長は上界を持つか否かについて問う、未解決なGaussian moat問題がある。
  • 言い換えると以下のようになる
    ガウス素数により定義される、無限のユークリッド点集合に含まれる全ての点pとqのペアに対し、ガウス素数pとqの間のMinimaxパスは、たかだかminimax edge長がBであるか？