プリフロープッシュ法

プリフロープッシュ法について

プリフロープッシュ法は、数理最適化においてフローネットワークから最大流を見つけるためのアルゴリズムです。この法則は、名前の通り、プッシュ操作と再ラベル操作の二つの手続きによって運用されます。この手法によって、プリフローを維持しつつ、再ラベル操作を通じてネットワーク内の近隣の頂点間でフローを調整し、最大流を求めることが可能になります。

従来の最大流問題に対して、フォード・ファルカーソン法がソースからシンクまでの経路を用いてフローを増加させていくのに対し、プリフロープッシュ法はより効率的に問題を解くことができるとされています。汎用のプリフロープッシュ法では、時間計算量は強多項式オーダーの O(V²E) で動作します。これはエドモンズ・カープ法の O(VE²) よりも効率的です。

また、プリフロープッシュ法には、計算量が O(V²√E)で動作する方法もあり、この方法はhighest label node selectionに基づいています。さらに、動的木を用いた手法では、時間計算量は O(VE log(V²/E)) に達するものの、実用面では効率が少し低下することがあります。

このアルゴリズムの特徴の一つは、最小費用流問題への拡張が可能である点です。距離ラベルの考え方を導入することで、より効率的に経路を見つけることができ、プリフロープッシュ法と組み合わせることで高いパフォーマンスを実現することができます。

プリフロープッシュ法の歴史

プリフロープッシュ法の起源は1974年にアレキサンダー・カルザノフによって提案されたプリフローの概念にさかのぼります。彼はこのアイデアを Soviet Mathematical Dokladiに掲載しました。彼の手法は、増加道の距離を求めるのにラベリングシステムを使用せず、プッシュ操作によって解決を図るものでした。

その後、アンドリュー・V・ゴールドバーグとロバート・タージャンにより、プリフロープッシュ法として具現化されました。彼らは1986年11月に開催されたSTOC '86でこのアルゴリズムを初めて公開し、1988年にはACMの学術論文誌に掲載されました。両者の研究では、O(V²E) の一般的解法、O(V³) の段階的解法、そして動的木を使用する O(VE log(V²/E)) の手法が提案されています。

ゴールドバーグとタージャンは、Yossi ShiloachやUzi Vishkinによる並列最大流アルゴリズムにおいて、距離ラベルの手法に自身の技法を適用したことでも知られています。

このように、プリフロープッシュ法は、最大流問題における重要で強力なアルゴリズムとしての地位を確立しており、その応用範囲や拡張性の高さにより、多くの研究や実装に影響を及ぼしています。

もう一度検索