最大幅パス問題

グラフアルゴリズムにおいて、最幅パス問題とは、重み付きグラフ内の指定された2つの頂点間のパスを見つけ、パス内の最小重みのエッジの重みを最大化する問題です。最幅パス問題は、最大容量パス問題とも呼ばれます。ほとんどの最短パスアルゴリズムは、パス長の代わりにボトルネック距離を使用するように変更することで、最幅パスを計算できるように適応させることができます。^[1]ただし、多くの場合、さらに高速なアルゴリズムも可能です。

たとえば、インターネットのルータ間の接続を表すグラフでは、エッジの重みが2 つのルータ間の接続の帯域幅を表します。最大パス問題とは、2 つのインターネット ノード間で最大帯域幅を持つエンドツーエンドのパスを見つける問題です。^[2] このパスの最小エッジ重みは、パスの容量または帯域幅として知られています。最大パス問題は、ネットワーク ルーティングへの応用だけでなく、マルチウェイ選挙の勝者を決定するSchulze 法の重要なコンポーネントでもあり、 ^[3]デジタル合成、^[4]代謝経路解析、^[5]最大フローの計算にも適用されています。^[6]

密接に関連する問題であるミニマックスパス問題またはボトルネック最短パス問題は、任意のエッジの最大重みを最小化するパスを求めるものです。これは、輸送計画などの用途があります。^[7]最大パス問題のアルゴリズムは、アルゴリズムによって実行されるすべての重み比較の意味を逆にするか、すべてのエッジの重みをその否定に置き換えることによって、ミニマックスパス問題のアルゴリズムに変換できます。またはその逆も可能です。

無向グラフでは、最大全域木における2つの頂点間のパスとして最も広いパスが求められ、最小全域木における2つの頂点間のパスとしてミニマックスパスが求められる。^{[8] [9] [10]}この同値性から、-頂点無向グラフにおけるすべてのペアの最大幅のパスはの時間で計算できることが直ちに分かる。^[11]${\displaystyle n}$${\displaystyle O(n^{2})}$

有向グラフでも無向グラフでも、最小重みの辺の重みがわかれば、最も幅の広い経路を見つける簡単なアルゴリズムがある。つまり、単に小さい辺をすべて削除し、残りの辺の中から幅優先探索または深さ優先探索を使用して経路を検索するだけである。このテストに基づいて、最大全域木を使用しない、無向グラフで最も幅の広いs - t経路を見つける線形時間 アルゴリズムも存在する。このアルゴリズムの主なアイデアは、線形時間経路検索アルゴリズムをグラフ内の中央辺重みに適用し、経路が存在するかどうかに応じて小さい辺をすべて削除するか、大きい辺をすべて縮小し、結果として得られる小さいグラフを再帰的に処理するというものである。^{[9] [12] [13]}

Fernández、Garfinkel、Arbiol (1998)は、重なり合う領域の複数の画像を組み合わせた合成 航空写真を作成するために、無向ボトルネック最短経路を使用しています。最大経路問題が適用されるサブ問題では、2 つの画像がすでに共通の座標系に変換されています。残っているタスクは、重なり合う領域を通過し、2 つの画像のうちの 1 つを他の画像から分割する曲線である継ぎ目を選択することです。継ぎ目の片側のピクセルは 1 つの画像からコピーされ、継ぎ目のもう一方の側のピクセルは他の画像からコピーされます。両方の画像のピクセルを平均化する他の合成方法とは異なり、これにより、撮影されている領域のすべての部分の有効な写真画像が生成されます。彼らは、そのエッジを横切る継ぎ目が視覚的にどの程度明らかであるかを数値的に推定して、グリッド グラフのエッジに重みを付け、これらの重みに対するボトルネック最短経路を見つけます。従来の最短経路ではなく、この経路を継ぎ目として使用することで、システムは、画像の一部の視認性を高める代わりに他の部分の視認性を低下させるのではなく、すべての点で識別が困難な継ぎ目を見つけるようになります。^[4]

グリッドグラフの2つの対角間のミニマックスパス問題の解は、 2つの多角形チェーン間の弱いフレシェ距離を見つけるために使用できます。ここで、各グリッドグラフの頂点は、各チェーンから1つずつの線分のペアを表し、エッジの重みは、1つの線分のペアから別の線分のペアに渡すために必要なフレシェ距離を表します。^[14]

無向グラフのすべての辺の重みが正の場合、点のペア間のミニマックス距離（ミニマックスパスの最大辺の重み）は超距離を形成します。逆に、すべての有限超距離空間は、このようにしてミニマックス距離から生じます。^[15]最小全域木から構築されたデータ構造により、直交木で最小共通祖先クエリを使用して、クエリごとに定数時間で任意の頂点ペア間のミニマックス距離を照会できます。直交木のルートは、最も重い最小全域木の辺を表し、ルートの子は、最も重い辺を削除することによって形成された最小全域木のサブツリーから再帰的に構築された直交木です。直交木の葉は入力グラフの頂点を表し、2つの頂点間のミニマックス距離は、それらの最小共通祖先である直交木ノードの重みに等しくなります。最小全域木の辺がソートされると、この直交木は線形時間で構築できる。^[16]

有向グラフでは、最大全域木解法は使用できません。代わりに、いくつかの異なるアルゴリズムが知られています。どのアルゴリズムを使用するかの選択は、パスの開始頂点または終了頂点が固定されているかどうか、または多くの開始頂点または終了頂点のパスを同時に見つける必要があるかどうかによって異なります。

全ペア最広路問題は、投票者が候補者を優先順位でランク付けする多面選挙で勝者を選ぶためのシュルツ法に応用されている。シュルツ法は、頂点が候補者を表し、2つの頂点ごとに辺で接続された完全な有向グラフを構築する。各辺は、接続する2人の候補者のペアごとの競争の勝者から敗者に向かっており、その競争の勝利の差でラベル付けされている。次に、この方法はすべての頂点のペア間の最広路を計算し、各対戦相手への経路が逆の場合よりも広い頂点を持つ候補者が勝者となる。^[3]この方法を使用した選挙の結果はコンドルセ法と一致している。つまり、すべてのペアごとの競争に勝った候補者は自動的に選挙全体で勝者となる。しかし、この方法では、コンドルセ法自体が失敗する状況でも、一般的に勝者を選ぶことができる。^{[17]シュルツ法は、}ウィキメディア財団を含むいくつかの組織で使用されている。^[18]

投票アプリケーションで発生するような密な有向グラフ内のすべてのノードのペアについて、最も広いパス幅を計算する場合、漸近的に最も速い既知のアプローチでは、時間がO ( n ^(3+ω)/2 )かかります。ここで、 ω は高速行列乗算の指数です。行列乗算の最もよく知られているアルゴリズムを使用すると、この時間制限は O ( n ^2.688 )になります。^[19]代わりに、Schulze メソッドの参照実装では、より単純なFloyd–Warshall アルゴリズムの修正バージョンが使用され、時間はO ( n ³ )かかります。^[3]疎なグラフの場合は、単一ソースの最大幅パス アルゴリズムを繰り返し適用する方が効率的な場合があります。

エッジが重みによってソートされている場合、ダイクストラのアルゴリズムの修正バージョンは、指定された開始頂点とグラフ内の他のすべての頂点との間のボトルネックを線形時間で計算できます。 ダイクストラのアルゴリズムの従来のバージョンよりも高速化された主なアイデアは、このアルゴリズムによって頂点が考慮される順序での各頂点へのボトルネック距離のシーケンスが、ソートされたエッジの重みのシーケンスの単調な部分シーケンスであるということです。したがって、ダイクストラのアルゴリズムの優先キューは、バケット キューとして実装できます。バケット キューは、1 からm (グラフ内のエッジの数)までの数字でインデックス付けされた配列で、配列セルiには、ボトルネック距離がソート順で位置iのエッジの重みである頂点が含まれます。この方法により、ソートと同じくらい速く最大パス問題を解決できます。例えば、辺の重みが整数として表現されている場合、m個の整数のリストを整数ソートするための時間制限がこの問題にも適用される。^[13]

Berman & Handler (1987) は、サービス車両と緊急車両がサービスコールから基地に戻るときにミニマックスパスを使用する必要があることを提案しています。このアプリケーションでは、車両が戻る途中で別のサービスコールが発生した場合、戻る時間よりも応答時間の方が重要です。エッジの重みがエッジ上のポイントから可能な限り遠いサービスコールまでの最大移動時間であるミニマックスパスを使用すると、サービスコールの受信から応答車両の到着までの最大遅延を最小限に抑えるルートを計画できます。^{[7] Ullah、Lee、Hassoun (2009) は、}代謝ネットワークの主要な反応チェーンをモデル化するためにマキシミンパスを使用しています。彼らのモデルでは、エッジの重みは、エッジによって表される代謝反応の自由エネルギーです。^[5]

最幅パスの別の応用は、最大フロー問題に対するフォード・ファルカーソンアルゴリズムで生じる。フロー残余ネットワーク内の最大容量パスに沿ってフローを繰り返し拡張すると、最大フローを見つけるために必要な拡張回数の小さな上限O ( m log U )が得られる。ここで、エッジ容量は最大Uの整数であると仮定される。ただし、この分析は容量が正確に最大になるパスを見つけることには依存しない。容量が最大値の定数倍以内であるパスであればどれでも十分である。この近似の考え方をエドモンズ・カープアルゴリズムの最短パス拡張法と組み合わせると、実行時間O ( mn log U )の最大フローアルゴリズムが得られる。^[6]

入力グラフのエッジの重みの比較のみが可能で、それらの演算はできない計算モデルでも、単一のソースと単一の宛先を持つ最大容量パスとミニマックスパスを非常に効率的に見つけることが可能です。^{[13] [20]}アルゴリズムは、最適パスのボトルネックエッジを含むことがわかっているエッジのセットSを維持します。最初は、 S はグラフのすべてのmエッジのセットにすぎません。アルゴリズムの各反復で、 S をほぼ同じサイズのサブセットの順序付けられたシーケンスS ₁、S ₂、...に分割します。このパーティション内のサブセットの数は、サブセット間のすべての分割ポイントが、繰り返しの中央値検索によって時間O ( m )で見つけられるように選択されます。次に、アルゴリズムは、エッジを含むサブセットのインデックスによってグラフの各エッジの重みを再設定し、重み付けし直したグラフに対して修正ダイクストラアルゴリズムを使用します。この計算結果に基づいて、どのサブセットにボトルネックのエッジ重みが含まれているかを線形時間で判断できます。次に、ボトルネックの重みが含まれていると判断したサブセットS _iでS を置き換え、この新しいセット Sで次の反復を開始します。 Sを分割できるサブセットの数は各ステップで指数関数的に増加するため、反復回数は反復対数関数O ( log * n )に比例し、合計時間はO ( m log * n )です。^[20]各エッジ重みがマシン整数である計算モデルでは、このアルゴリズムの繰り返し二分法の使用は、Han & Thorup (2002) のリスト分割手法に置き換えることができ、S を1 つのステップでO ( √ m ) 個のより小さなセットS _iに分割して、線形の全体的な時間制限を実現できます。^[21]

ミニマックスパス問題の変種は、ユークリッド平面上の点の集合についても考えられてきた。無向グラフ問題と同様に、このユークリッドミニマックスパス問題は、ユークリッド最小全域木を見つけることで効率的に解くことができる。つまり、木内のすべてのパスはミニマックスパスである。しかし、ホップ長を最小化するだけでなく、同じホップ長を持つパスの中でパスの全長を最小化または近似的に最小化するパスが求められる場合、問題はより複雑になる。この解は、幾何学的スパナを使用して近似することができる。^[22]

数論において、未解決のガウスの堀問題は、ガウス素数内のミニマックスパスが有界または無制限のミニマックス長を持つかどうかを問うものである。つまり、ガウス素数によって定義される無限ユークリッド点集合内のすべての点pとqのペアに対して、 pとqの間のガウス素数内のミニマックスパスのミニマックス辺の長さが最大で Bになるような定数Bが存在するか？^[23]