Skip to content
検索結果に戻る

プッシュ・リラベル法

提唱者
Andrew V. Goldberg and Robert E. Tarjan
年
1988
種類
algorithm
系統
Graph Algorithms

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

プッシュ・リラベル法(Push-Relabel Algorithm)は、1988年にAndrew V. GoldbergとRobert E. Tarjanによって開発された、ネットワークにおける最大フロー計算のための非常に効率的な手法である。増加パス法とは異なり、このアルゴリズムはプリフローを維持し、局所的なプッシュ操作と大域的なリラベル操作を用いてフローをシンクへ誘導することで、優れた最悪ケース計算量を達成する。

手法の背後にある直感

このアルゴリズムは、各ノードに「高さ」または「距離ラベル」を維持し、プリフロー(ノードが一時的にシンク需要を超過することを許容する)を使用する。過剰なフローをより高いラベルのノードからより低いラベルの隣接ノードへ繰り返しプッシュし、ノードをリラベルしてシンクへのパスを作成する。その鍵となる洞察は、高さの不変条件を維持し、効率的なデータ構造を使用することで、増加パス法が繰り返し行う必要のあるグラフ全体の探索を回避できることである。アルゴリズムは、すべての過剰フローがシンクに到達したときに終了する。

歴史学

GoldbergとTarjanは1988年にプッシュ・リラベル法を発表し、最大フロー計算のための根本的に異なるパラダイムを導入した。彼らのアルゴリズムは、Edmonds-KarpのO(VE²)よりも改善されたO(V³)の最悪ケース計算量を達成した。その後の数十年で、ギャップヒューリスティック(Goldberg and Tarjan, 1990)、最高ラベル規則、および実世界のネットワークで線形に近い経験的性能を達成する最新のバリアントを含む、数多くのバリアントが開発されてきた。

使うべき場面

増加パス法が非効率になるような、大規模で密なネットワークにおける最大フロー計算にプッシュ・リラベル法を適用する。数百万、数千万のエッジを持つネットワークに特に効果的である。保証された多項式時間性能が必要で、最新のデータ構造を活用したい場合にこれを使用する。疎なネットワークや教育目的には、増加パス法の方が理解と実装が容易な場合がある。

限界と注意点

  • 増加パス法よりも理解と実装が複雑である
  • 最適な性能を得るためには、データ構造(ディスチャージリスト、ギャップヒューリスティック)の慎重な取り扱いが必要である
  • 一部の特殊なグラフクラスに対する一部の特殊アルゴリズムよりも最悪ケース計算量が高い
  • 増加パス法と比較して、解法の直感的理解が劣る

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 優れた最悪ケース時間計算量: O(V³) またはギャップヒューリスティックを用いた場合 O(V²√E)
  • 実際には非常に効率的、特に大規模で密なネットワークにおいて
  • 操作の局所性(プッシュ/リラベル)は、良好なキャッシュ性能を可能にする
  • 並列化および分散実装に適している
  • 異なる問題構造のための複数の実装バリアント

応用

  • ネットワークルーティング: 大規模通信ネットワークにおける最大スループットの計算
  • 画像処理: 最大フローを用いた画像セグメンテーションおよびマット処理アプリケーション
  • 航空会社最適化: 複雑なルーティングネットワークを通じた最大乗客フローの決定
  • 電力網解析: 電気ネットワークにおける最大電力伝送容量の計算
  • サプライチェーン管理: マルチティア流通ネットワークを通じた製品フローの最適化
  • 生物学的ネットワーク: 代謝およびタンパク質相互作用ネットワークにおける最大フローの解析

使い方

使い方

1

ソースの高さを頂点数に設定し、他のすべての高さをゼロに設定する。ソースから出るすべてのエッジを飽和させ、隣接ノードにプリフロー(超過)を作成する。

2

アクティブなノード(超過フローを持つノード)を繰り返し選択し、超過フローをより低い高さの隣接ノードにプッシュするか、ノードをリラベルして高さを増やす。反復を最小限に抑えるために、効率的な選択戦略とディスチャージ操作を使用する。

3

アクティブなノードがなくなるまで続行する。この時点で、すべてのプリフローはソースからシンクへの最大フローに解決されている。

よくある落とし穴

  • 高さの更新またはプッシュ操作の不適切な実装により、最大フローにならない
  • ギャップヒューリスティックと効率的なノード選択を怠り、実用的な性能が低下する
  • プリフローの不変条件(ノードの超過とエッジの容量制約)を適切に維持できない

よくある質問

プリフローとフローの違いは何ですか?

プリフローは一時的にノードが超過フローを保持することを許容する(流入量マイナス流出量が正になりうる)が、真のフローはソースとシンク以外のすべてのノードで保存されなければならない。アルゴリズムは、プリフローが有効なフローになったときに終了する。

高さ関数の目的は何ですか?

高さは準距離尺度を作成する。フローは下り坂(より高い高さからより低い高さへ)にのみプッシュでき、不要なサイクルを防ぎ、終了を保証する。必要に応じて新しいパスを作成するために、リラベルを通じて高さが増加される。

ギャップヒューリスティックとは何ですか、そしてなぜ重要ですか?

ギャップヒューリスティックは、ある範囲の高さを持つノードが存在しない場合にそれを検出し、一部のノードがシンクに到達できないことを示唆する。これらのノードとその超過フローは迅速に特定され処理され、実用的な性能が大幅に向上する。

実用上、プッシュ・リラベル法はEdmonds-Karp法と比較してどうですか?

プッシュ・リラベル法は最悪ケース計算量が優れており、通常は大規模ネットワークでEdmonds-Karp法を上回る性能を示すが、小規模ネットワークや疎なグラフでは、Edmonds-Karp法の方が実装が容易で、同等の性能を示す場合がある。

関連する手法

参考文献

  1. Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.

    DOI 文献を開く
    コピーしました。
  2. Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.

    出版物の文献を開く
    コピーしました。