Ford-Fulkerson法(最大流量増加法)によるアルゴリズムの時間計算量と解の収束性についての図説

#CTODO あとで図を追加する。したappbird.icon

目的

コンピュータサイエンス教科書シリーズ19 数理計画法/加藤直樹のp.102の証明の行間を埋める。

主に整数容量のときの時間計算量の証明の部分の行間を対象とする。

https://gyazo.com/a7301a0e9e737ad2b8d0c815ecabf364

将来の自分や他の人がこの行間に詰まった際の手助けとなるよう、できる限り図説する。

制約

用語は全てこの本に則って使う。

ただし、その書籍独自の言葉であるように見えた場合は別途定義を付記している。

事前定義

解く問題は最大流問題である

グラフ$ G:=(V, E, c);

$ c: E \to \R^+は容量関数。

$ f: E \to \R^+: $ Gにおけるフロー(変数)

$ G_f: $ (G, f)に対する残余ネットワーク

Fig.1 $ G, f, G_fの描画

図中の$ \Rightarrowは概念の依存を表す。

$ A \Leftarrow Bは「$ Aがあってはじめて$ Bを考えられる」という意味

要するに、$ G_fはどの方向に後どれだけ流せるかということを示している。

逆辺は一部の流量を減らす方向に調節

https://gyazo.com/108c028f0b88f704fb3d9e5638d08dd5

$ \mathcal{A}: Fold-Fulkerson法(最大流量増加法)における以下の手順

要するにアルゴリズムのうちの更新手順

(1)$ fに対する($ G_fの)フロー増加可能パス$ pの中で、そのパスに関する残余容量が最大のものを探す。

$ pに関する残余容量とは、$ pの辺における残余容量の最大値のことを指す。

注辺$ eの残余容量とは、$ c(e) - f(e)のことである。

(2)

もし$ pが存在すれば

その$ pに沿って$ fのフローを増加させ、$ fを更新する

存在しなければ

アルゴリズム全体を終了する。

$ f_i: $ \mathcal{A}の$ i回目の反復終了時における変数$ fの値

$ 0回目は$ \mathcal{A}が一度も実行されていない状態を指す。

Fig.2 アルゴリズム$ \mathcal{A}の動作

https://gyazo.com/63043e9dc8685740527d02e8c635993b

主張

Ford-Fulkerson法にて、パスの選択に最大流量増加法を取れば、以下が期待できる。

(i) 実数容量を取る時、解が漸近する。

$ \lim_{n \to \infin} |f_n| = |f^*|

$ |f^*|は真値となる最大フロー

この実数容量は無理数も含むことに注意

注無理数の場合、適当にパスを選択するようなFord-Fulkerson法には停止性が保証されない。

異なった値に収束する恐れがある。

(ii) 整数容量を取るとき、アルゴリズムは停止性を持つ。

$ \mathcal{A}の反復回数は$ \mathrm{O}(m\log(Um))となる。

ただし、$ Uは辺$ Eの中で最大の容量を表す。

Fig.3 誤差の収束性

https://gyazo.com/268998baa97fd93cf7bc24189d7e8ee9

証明

/icons/pass.icon補題1. 最大流量$ f^*が既知のとき、高々$ |E|回の反復によって、$ fの値を$ f^*にできる。

Fig.4 $ f^*が既知の時のフロー増加について

訂正: 図中の$ \mathcal{A}を$ \mathcal{A'}に読み替える。

ここで扱うアルゴリズムでは$ \mathcal{A}のように最大流量増加法をとっていない。

また、「$ fに最も近い辺」の$ fを$ f^*に修正

https://gyazo.com/b69eb533aa238998e2e76b486360a5e1

教科書の証明がわかりやすいので概説にとどめる。

各反復で

$ f^*と比べて埋まりきっていないが、$ f^*に最も近い流量を持つ辺を含むパスを選んでいく

残余容量ぶんだけパスに沿ってフローを増加させる。

すると、各反復で必ずいずれかの辺が最大の流量を取り始める。

/icons/notepad.icon付記

最大流量$ f^*が既知であるという前提に立っていることに注意

このことから、$ fから取れるフロー増加可能パスは高々$ |E|個しかないことがわかる。

フロー増加可能パスをフローへ適用する順序によって、最終結果は変わらないことによる

(残余ネットワークの逆辺の存在によってこの性質が実現されている。)

/icons/pass.icon補題2. 最大流量増加法によってパスを選ぶと、必ず$ i回目の$ \mathcal{A}の反復においてフロー$ fが$ \frac{|f^*| - |f_i|}{|E|}以上増加する。

Fig.5 $ \mathcal{A}1回分のフロー増加量の下界の導出

$ f^*が未知であることに留意する。

https://gyazo.com/cafbf1d3ed3d852bdccc656a8cbfcab1

(行間)

平均の性質による。

$ i回目の反復において取れるフロー増加可能パス全体$ Pを考える

$ Pの要素は、補題1より高々$ |E|個である。

$ Pのパスによって増加するフローの合計値は$ |f^*| - |f_i|である。

(1) よって、フロー増加量の平均$ \overline{p_\Delta}は、$ \frac{|f^*| - |f_i|}{|E|}以上である。

$ \frac{|f^*| - |f_i|}{|E|} \leq \overline{p_\Delta}

(2) ここで最大流量増加を実現するフロー増加可能パス$ p \in Pをとる。

すると$ pは、$ \overline{p_\Delta} \leq p_\Deltaなるフロー増加量$ p_\Deltaを実現する

最大値は平均を上回る。(背理法により証明可能)

よって、$ \frac{|f^*| - |f_i|}{|E|} \leq p_\Delta

/icons/pass.icon補題3. 最大流量増加法に従ってパスを取ると、$ n回目の$ \mathcal{A}の反復に際して以下が満たされる。

(行間)

$ |f^*| - |f_n| \leq (1 - \frac{1}{m})^{n}(|f^*| - |f_0|)

Fig.6 $ \mathcal{A}の反復によって縮まる誤差

https://gyazo.com/ed9a41cd728efd5e812500d4dc0bde8d

ただし、$ m := |E|

$ i回目の$ \mathcal{A}の反復に関して、補題2より以下が満たされる。($ iは非負整数)

$ \frac{|f^*| - |f_{i}|}{m} \leq |f_{i+1}| - |f_{i}|

これを変形すると、以下の不等式を得る。これは$ \mathcal{A}一回あたりの誤差減少量の上界を示す。

$ |f^*| + \frac{(|f^*| - |f_{i}|)}{m} \leq |f^*| + |f_{i+1}| - |f_{i-1}|

$ |f^*| - |f_{i+1}| \leq |f^*| - \frac{|f^*|}m + \frac{|f_{i}|}m - |f_{i}|

$ |f^*| - |f_{i+1}| \leq (1 - \frac1m)(|f^*| - |f_{i}|)

以下の不等式の両辺はいずれも正であるから、これらを掛け合わせると題意の不等式を得る。

$ |f^*| - |f_{1}| \leq (1 - \frac1m)(|f^*| - |f_{0}|)

$ |f^*| - |f_{2}| \leq (1 - \frac1m)(|f^*| - |f_{1}|)

$ \vdots

$ |f^*| - |f_{n}| \leq (1 - \frac1m)(|f^*| - |f_{n-1}|)

よって、

$ |f^*| - |f_n| \leq (1-\frac1m)^n(|f^*| - |f_0|)

/icons/notepad.icon付記

厳密には数学的帰納法を踏む必要がある。

/icons/pass.icon系4. $ 0 \leq |f^*| - |f_n| \leq \frac{1}{2^{n/m}}(|f^*| - |f_0|)

Fig.7 不等式の変形と誤差の上界

https://gyazo.com/6e997691997d5cb69764fcd407ed4312

ここで次の関係に注意する。

$ (1 - \frac{1}{m})^{m} \leq \frac1e \leq \frac12

すなわち$ (1 - \frac{1}{m})^{n} \leq \frac{1}{2^{n/m}}

このことから、以下を得る。

$ |f^*| - |f_n| \leq (1 - \frac{1}{m})^{n}(|f^*| - |f_0|) \leq \frac{1}{2^{n/m}}(|f^*| - |f_0|)

また、$ f^*の最大性により、任意のフロー$ fに対して$ |f| \leq |f^*|が成立するため、

$ 0 \leq |f^*| - |f_n|

/icons/pass.icon定理5. 解の収束性

以上の議論より、系4.における挟み撃ちの原理を用いて

右辺$ \lim_{n \to \infin} \frac{1}{2^{n/m}}(|f^*| - |f_0|) = +0に基づいて

$ \lim_{n \to \infin} ( |f^*| - |f_n| ) = +0

i.e. $ \lim_{n \to \infin} |f_n| = |f^*|

よって、解の収束性を得た。

/icons/notepad.icon付記

実際の収束速度はどうやって調べると良いのだろう...？

実測？

/icons/pass.icon定理6. 整数容量の時のアルゴリズム停止性

Fig.8 アルゴリズムに必要な反復回数に対する上界 (定理6, 7)

https://gyazo.com/a7301a0e9e737ad2b8d0c815ecabf364

(1) アルゴリズムの性質上、$ |f^*| - |f_i|は非負整数にしかならない。

(2) (定理5.に関連して、)アルゴリズムの誤差上界は$ \mathcal{A}を繰り返すうちに$ 1に到達する。

(行間)

系4における右辺に注目する。

これは、真値$ |f^*|と実測値$ |f|の誤差の上界となる。

数列$ a_n := \frac{1}{2^{n/m}}(|f^*| - |f_0|) > 0はステップ数$ nに対して狭義単調減少数列である。

よって、必ず$ a_Nが$ 1を下回るステップ数($ N)が存在する。

/icons/notepad.icon付記

ε-N論法による収束の定義によれば、$ \varepsilon = 1として

$ \exist N\in\N; \forall n\in\N; N \leq n \Rightarrow |a_n - 0| = a_n < 1

であることからもこの主張を理解できる。

(3) アルゴリズムは停止性を持つ。

$ |f^*| - |f_N| \leq a_N < 1になるとき、(1)より$ |f^*| - |f_N| = 0である。

これは、真値がもとまりアルゴリズムの目的が達成されたことを意味する。

よって、このようなステップ番号$ i = nが存在すると言えたので、アルゴリズムは停止する。

/icons/notepad.icon付記

同様の理由から、実数容量の時でも許容誤差さえ設定してしまえばアルゴリズムが停止することがわかる。

(ただし、この許容誤差がアンダーフロー(__DBL_EPSILON__)しないように気を付ける必要はある。念の為。)

/icons/pass.icon定理7. 整数容量の時の$ \mathcal{A}の反復回数は$ \mathrm{O}(|E|\log(U|E|))に従う。

Fig.9 アルゴリズムが停止するときの反復数$ nについて、その上界を求める方針

https://gyazo.com/ae05ba455d9043ceb03a3c552b6cb43d

(1) 任意のフロー$ fに対し、$ |f^*| - |f| \leq |f^*| \leq Umである。

(行間; 簡単である)

流量は、どう足掻いても各辺の容量の和以上を流すことができない。(各辺の容量制約と流量均衡条件による。)

任意のフローに対して、$ |f| \leq \sum_{e\in E}f(e) \leq \sum_{e\in E} c(e)

ましてや、最大流量$ Uに関してその最大性により$ c(e) \leq Uなのだから、以下を得る。

$ |f| \leq \sum_{e\in E} c(e) \leq \sum_{e\in E} U = U|E| = Um

よって、$ |f^*| \leq Um

$ |f|が非負整数より$ |f^*| - |f|\leq Umも得る。

(2) 誤差の上界$ a_nが$ a_n < 1となる$ nがどこに存在するかを知る。

$ nに対する停止十分条件: $ \frac{1}{2^{n/m}}(|f^*| - |f_0|) < 1

実際のアルゴリズムはこの条件を満たす$ nよりももっと早く停止している場合がある。

この条件を変形していく

$ \frac{1}{2^{n/m}}(|f^*| - |f_0|) < 1

$ m\log(|f^*| - |f_0|) < n.... (2-1)

よって、$ a_n < 1を満たす$ nは$ m\log(|f^*| - |f_0|)以上の自然数全てである。

ただし、今回求める$ |f^*| - |f_0|のうち、$ |f^*|は一般に不明である。

よって、オーダー評価する際にあたっては、この未知数を省きたい。

ここで、(1)より以下のようになる。

$ m\log(|f^*| - |f_0|) \leq m\log(Um)

このことから、以下を満たすような$ n'もまた$ a_n < 1を満たすことがわかる。

$ m\log(Um) < n'.... (2-2)

(2-1)から(2-2)の変形は同値変形ではなく、あくまで十分条件になっている。

(2-2)ならば(2-1); 必要性を失って変形している。

(2-1)に比べて(2-2)の方が、$ nの範囲が$ +\infin方向へ狭まっていることに留意する(Fig.9を参照)

以上より、$ m\log Um < nを満たす$ n全ては、$ a_n < 1を満たす。

よって、$ a_n < 1となるような$ n としては、少なくとも $ n = \mathrm{ceil}(m\log Um)以上にある。

よって、$ n = \mathrm{O}(m\log Um)

これが$ \mathcal{A}の高々必要な反復回数である。... (2)

/icons/notepad.icon付記

(2) 系4で求まった不等式は、誤差の値域ではなくてあくまで上界であることに留意したい

そのため、ここで求まった$ nはあくまで上限の値という意味しか持たない。

以上より、このアルゴリズムの時間計算量は$ O(|E||V|^2\log U|E|)である。

$ \mathcal{A}のパス探索でDijkstra法(ダイクストラ法)を用いるのであれば、$ O(|V|^2)に従うステップ数を要する。

$ \mathcal{A}は、$ n = O(m\log{Um})に従う反復回数を要する。

よって、これらを掛け合わせれば題意の時間計算量を得る。

/icons/notepad.icon付記

なんかDijkstra法早くない...？

普通のDijkstra法で、重みを確定する頂点を選ぶ部分でヒープを使えば$ O(|E|\log|V|)である。

なので正確には$ O(|E|^2\log|V|\log(U|E|))

ここで言及したDijkstra法には多少の変形を要するらしい。

$ |E|は$ O(|V|^2)なので、確かに$ O(|V|^2\log|V|)が$ O(|V|^2)に減るのはお得

□

参考文献

コンピュータサイエンス教科書シリーズ19 数理計画法/加藤直樹

グラフ・ネットワークアルゴリズムの基礎/浅野考夫

/icons/notepad.icon余談

今回証明したアルゴリズムは最大フロー最小カット定理によって正当性が保証されている。

ボトルネックが発生する場所が最小カットであることがキモである。

より実用的なアルゴリズムとしてはDinicのアルゴリズムがある。 ($ O(|V||E|\log n))

レベルグラフというものを導入するらしい。

$ \mathrm{O}(nm^2)であるようなEdmonds-Karpのアルゴリズムも知られている。

ただし実用上あまり早くはないらしい...？

最近になってほぼ線形時間のアルゴリズムが発表されたらしい。

(授業で聞いただけなので詳細は不明)

定理7(2)が教科書だと1行で済まされているのでビックリした。

必要性と十分性を正しく理解していないと理解できないのでは...？

何か遠回りしてしまっているのだろうか？

人生で初めてアルゴリズムを文字で置いた。使うかな〜と思っていたけど意外と結構使った。

アルゴリズムの証明にまた一つ強くなった気はする

絶対これテストに出ないやつなのにやりこんでしまった...appbird.icon

図を用意するのにかかったのはおおよそ1時間15分。テストが終わった後に図を書いた。