■学生論文賞受賞論文

最大隣接順序を用いた最大流アルゴリズムの改良と実装
松岡 祐治（東京大学工単部計数工学糾 現所属・束京大草大学院情報型工学系研究科数理情報学専攻）
指導教官 岩田 覚助教授とどれぐらい流せるかを考えたネットワークを残余ネ

1．はじめにットワークといい，〟pで表す．

最大流問題とは，与えられたネットワークにおける最大フローを探す問題のことで，様々な最適化問題に適用できることからこれまでに活発な研究かなされている．1988年にGoldberg−Tarjanによってプッシ

入口s＋から出口5￣へのプリフロー甲：A→Rとは次の条件（1），（2）を満たす関数である．
（1）容量制約：各枝α∈Aに対して，0≦甲（α）≦

c（α）．

ュ・リラベル法か提案され，ネットワークの点の数を（2）フロー境界条件：各点〃∈Ⅴ＼（s＋，S−）に対して，乃，辺の数を∽，最大容量をUとすると，0（〃忽柁log∂甲（〃）＝。〃か鼠る枝甲（αト。出雲る枝P（α）≦0（乃2／m））の計算量で最大流問題か解けるようになった．
このGoldberg−Tarjanのアルゴリズムか現在のところ実用的にも最速といわれている．

つまり，フローと異なり流量が保存されていなくてよい．−∂甲（〃）（≧0）を70リフローの残存量といい，残存量か正の点を活性点という．また，出口に流入する

そうした流れの中，2003年にFuJIShige［1］が最大量−わ（5−）をプリフロー甲の流量∂（甲）と定義する．

隣接順序に基つく新しい枠組みの最大流アルゴリズムを提案した．Fujishigeのアルゴリズムは理論的には0（乃（∽＋乃logプ？）logク7U）の計算量であるか，強多項式時間ではないことが示されている．実用的にも，
Goldberg−Tarjanのアルゴリズムと比較すると大きく劣っていた．

3．プリフローを用いた改良案
改良したアルゴリズムは次のとおりである．
StepO：入り口から出る枝a＝（s＋，u）∈Aに対して，
甲（α）←C（α）．それ以外の枝αに対しては，P（α）←0．

Stepl−1：MA−Orderlng（〟p，S−）を行い，出口からそこで本論文では，Fujishigeのアルゴリズムに対する改良として，7ウリフローを用いたアルゴリズムを提案する．計算機実験を行ったところ，実行時間が改良前のアルゴリズムに比べて10分の1程度と大きく減っており，実用的な速度においてGoldbergTTar−janのアルゴリズムに大きく近ついたといえる．

2．ネットワークに関する諸定義の順序（〃。（＝S￣），〃1，・，〃々）を得る．もしすべてのz＝1，…，kに対して∂p（uz）＝0を満たすならばStep2−1へすすむ．
Stepl−2：l＝k，k−1，…，1について，すべてのuzから出る枝（uz，u）∈L，V，に対して，puSh（vりu）：（〃z，α）∈A言ならば，

甲（〃り〟）←P（〃z，〟）＋mln（−∂甲（仇），Cグ（〃z，〟）），（〃りα）∈A；ならば，ネットワークは〟＝（C＝（Ⅴ，A），S＋，S￣，C）と書かれ，G＝（Ⅴ，A）はⅤを点集合，Aを枝集合とする有向グラフ，5＋∈Ⅴは入口，5￣∈Vは出口，CA→Z．は容量関数をそれぞれ表している．また，ルl＝乃，lAl＝∽とおく．

Step2−1：MA−OrderIng（JV p，S＋）を行い，入口からの順序（〃0（＝5＋），〃1，…，〃々）を得る．もしすべての〃∈Ⅴ＼（5＋，S￣）に対して毎（〃）＝0ならば終了．

ネットワーク〟か与えられたとき，入口∫＋から出口5￣へのフロー甲A→Rとは容量制約，流量保存則を満たす実数値関数である．また，入口から流出する量をフロー甲の流量という．
ネットワーク〟にフローPが流れているとき，あ2005年1月号

p（〟，〃〜）←甲（〟，〃【）−mln（−∂甲（〃乙），C甲（〃z，〟））SteplTlにもどる．

Step2−2：l＝k，k−1，・・・，1について，すべてのuzから出る枝（uりu）∈L，V．に対して，puSh（vりu）：（仇，〟）∈A；ならば，甲（〃乙，〟）←甲（仇，〟）十mln卜∂甲（仇），Cp（〃り〟）），© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（51）51MO（〃り祝）∈A；ならば，

M甲（〟，〃乙）←甲（〟，〃ェ）−mln（一毎（〃z），C9（〃1，〟））
Step2−1にもどる．

︒

を選んでいき，選ぶ点がなくなれば終了する．文献

00

すでに選んだ点の集合Ⅳへの流出量が大きい順に点︵s︶ ￠ ∈ ■ 一 ぎ ∈ 亡 コ ∝手続きMA−Ordering（Np，S）は，点sから始めて，［1］において提案された手続きと異なり，辺の向きを逆にたどることに注意する．

理論的には，次の補堰から少なくとも改良前の計算量0（乃（椚＋乃logプ7）log称U）でおさえられることが示

1213

せた．

1415
Numb即01vo州COさ（POW即Of2）

1￠

1718

図1GENRMF−LONGfamllyに対する結果

補題31Stepl−2の実行後にプリフローの残存している点があったとする．￠をStepト2の実行前のプ］）フロp甲とし，￠をStepl−2の実行後に得られた70リフロー甲とする．このとき，∂（￠）−か（￠）≧（∂＊一方（￠））／乃が成り立つ．ただし，か＊は〟におけ︵s︶￠∈−1︻ど■UU⊃∝

る最大流量を表す．

4．計算機実験の結果

0

改良したアルゴリズムをプログラムFMAPに実装した．プログラムFMAは改良前のアルゴリズムを実装している．プログラムHI＿PRはGoldberg−Tarjanの最遠点選択基準を用いたアルゴリズムを実装してお12

13

り，Goldbergのサイトからダウンロードした．

1415
16
Numboro†vt沼l￠OS（POW8JO†2）1718

図2 GENRMF−LONGERfamllyに対する結果

プログラムの入力となるネットワークを作るために，

DIMACSCoreExperimentで提示されているジェネレータGENRMFを用いた．各サイズについて5種類のランダムな入力データを作り，その平均をとっている．

（FMAP）は，すべてのデータにおいて改良前（FMA）に比べて大きく実行時聞か減っている．また，

互○∈コP∈U⊃∝

結果をま とめる と，改良 したプログラム▲U

Goldberg−Tarjanのアルゴリズム（HしPR）と比較すると，実用的に大きく近づいたことが分かる（図1〜3）．
125．まとめ
本論文では，FujishigeのアルゴT）ズムに対する改13141516
Numboro†vo仙⊃OS（POWOrO†2）1718

図3 GENRMF−WIDEfamilyに対する結果良としてプリフローを用いたアルゴリズムを提案した．
計算機実験の結果をみると，すべてのデータにおいて参考文献

改良前より速くなっており，実用的に有意な改良であることが確認できた．さらに，Goldberg−Tarjanのアルゴリズムと比較したところ，実用的に大きく近づいたことが分かった．
52（52）［1］S FujlShlge．AmaxlmumflowalgorlthmuslngMA
OrderlngS（砂eYat10nSResea7JChLette7S，VO131，pp176−178，2003© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ