最大フロー問題の解決における画期的な進歩: 新しいアルゴリズムは「驚くほど高速」

この問題はネットワークフロー理論において非常に基本的なものです。 「新しいアルゴリズムは驚くほど高速です。実際、この問題に対してこれほど効率的なアルゴリズムはあり得ないと確信していました」とイェール大学のダニエル・スピルマン氏は語った。

最大フローについては、旧ソ連の鉄道システムをモデル化するために初めて使用された 1950 年代から研究されてきました。 「その研究は理論的なコンピュータサイエンスよりも古いのです」とカリフォルニア州マウンテンビューの Google リサーチのエディス・コーエン氏は言う。

この問題は、インターネット データ ストリーミング、航空会社のスケジュール、さらには求職者と求人のマッチングなど、さまざまな用途につながります。新しい論文では、最大フローの問題と、コストを最小限に抑えながら最大フローに対処するというより一般的な問題の両方に取り組んでいます。これら 2 つの問題は、長年にわたってアルゴリズム技術の多くの大きな進歩に影響を与えてきました。 「それがまさに、私たちがアルゴリズムに取り組んでいる理由です」とスピルマン氏は語った。

新しいアルゴリズムは、両方の問題を「ほぼ線形」な時間で解決します。つまり、アルゴリズムは、ネットワークの詳細を記録するのにかかる時間とほぼ同じ時間で実行されます。これらの問題を解決するアルゴリズムの中で、あらゆるネットワークに対してこれほど高速なものはありません。カリフォルニア大学バークレー校のサティシュ・ラオ氏は、この結果に驚愕し、「ただただ驚いている」と語った。

スピルマン氏は、このような高速アルゴリズムが発見された今、これまで考えられなかったさまざまな応用問題の解決について考え始めるべき時が来たと考えています。

現時点では、この新しい方法は主に理論的な改善です。アルゴリズムの速度向上は、現実世界で遭遇するネットワークよりもはるかに大きなネットワークにのみ適用され、最大フローの問題を迅速に解決できるからです (少なくともコスト最小化を考慮しない場合)。このアルゴリズムを作成した6人のうちの1人であるカナダのウォータールー大学のリチャード・ペン氏は、新しいアルゴリズムが1年以内に実用化される可能性があると予測している。

一部の研究者は、今後数年間でコンピューター科学者がこれをより実用的に、そしておそらくはより高速にする方法を見つけるかもしれないと考えています。

将来的に改良が加えられたとしても、この新しい論文は「スラムダンクコンテストで最高のスラムダンクだ」とマサチューセッツ工科大学のアレクサンダー・マンドリ氏は言う。彼は基本的に最高だと言っていました。」

一度に一つの道

リチャード・ペン氏は、非常に多くのコンピューター科学者が最大フロー問題に取り組んでいるため、会議で過去の研究について議論するのは映画の最後のエンドロールを見るようなものだと語った。しかし、ほとんどの人は、最初の正式なアルゴリズムは、各ステップで最もアクセスしやすいオブジェクトを使用する、レスター・フォードとデルバート・フルカーソンによる 1956 年の最大フローの貪欲アルゴリズムであったことに同意しています。

このアプローチは次のように考えることができます。まず、指定された時間内にロサンゼルスからニューヨーク市までできるだけ多くの配送トラックを移動させたい高速道路のネットワークを想像してください。フォードとファルカーソンのアルゴリズムは、ロサンゼルスからニューヨークまでのルートを選択し、そのルートに沿ってできるだけ多くのトラックを配置することから始まります。この方法では、通常、その特定の道路区間のすべての道路の容量を最大限に活用することはできません。たとえば、道路が 5 車線の高速道路であっても、2 車線の橋を渡っている場合、一度に走行できるトラックは 2 台だけです。

次に、アルゴリズムは、道路セグメントの容量を変更して、容量の一部が現在使用されていることを反映します。つまり、セグメントの容量から送られたトラックの数を差し引くため、5 車線の高速道路の容量は 3 になり、2 車線の橋の容量は 0 になります。同時に、アルゴリズムはこれらの道路の逆方向の容量に 2 を追加するので、必要に応じて後で交通量の一部を元に戻すことができます。

次に、アルゴリズムは、一部のトラックを収容できるロサンゼルスからニューヨークへの新しい経路を見つけ、その経路に沿ってできるだけ多くのトラックを送り、容量を再度更新します。これらのステップを有限回数実行すると、ロサンゼルスからニューヨークまでの道路はこれ以上のトラックを収容できなくなり、アルゴリズムは完了します。つまり、構築したすべてのフローをマージして、ネットワークを介した最大フローを取得するだけです。

フォードとフルカーソンのアルゴリズムは、このプロセスでインテリジェントな選択を行おうとはしません。他の有用なパスを遮断するパスを選択した場合、それは後でアルゴリズムが対処する問題になります。このアルゴリズムが発表されてから数十年にわたり、研究者たちは、常に最短の利用可能なパスや利用可能な容量が最も大きいパスを使用するなど、アルゴリズムがよりスマートな選択を行えるようにすることで、実行時間を短縮しようと努めてきました。 1970 年、Yefim Dinitz は、ネットワーク内のすべての最短経路を 1 ステップで使用する効率的な方法を発見しました。このアルゴリズムの低容量ネットワークでの実行時間は、Shimon Even と Robert Tarjan によって m^1.5 であることが証明されました (m: ネットワーク内のリンクの数。対照的に、Ford-Fulkerson アルゴリズムでは、低容量ネットワークで複数の m^2 が必要です)。

約 30 年後、ラオとアンドリュー・ゴールドバーグは大容量ネットワークで同様の結果を得ました。しかし、m^1.5 指数を上回るものは存在しません。 「21世紀に入っても、m^1.5の壁は深く根付いている」と、新論文の著者の一人であるトロント大学のスシャント・サチデバ氏は言う。さらなる進歩を遂げるためには、コンピューター科学者は全く異なるアプローチを模索する必要がある。

組合せ論から微積分学へ

これまでのこれらのアルゴリズムはすべて組み合わせアプローチを採用しており、各ステップで何らかの構造を探し、その構造を使用してフローを更新しています。しかし、2003年に、南カリフォルニア大学のスピルマン氏とシャンホア・テン氏は、微積分技術を最適解を見つけるためのガイドとして使用する、まったく異なる「最適化」アプローチへの扉を開きました。

スピルマン氏とテン氏は、最大流量問題ではなく、それぞれ与えられた抵抗を持つ電線のネットワークを通る最低エネルギー電流を見つけるという密接に関連した問題を解決する高速最適化アルゴリズムを開発しました。サチデバ氏は、スピルマン氏とテン氏の進歩は「決定的な瞬間」だったと語った。

ネットワーク内の最大フローと最小コストを決定するための超高速アルゴリズムを作成したチームメンバー (左上から時計回り): Yang Liu、Li Chen、Rasmus Kyng、Maximilian Probst Gutenberg、Richard Peng、Sushant Sachdeva。

研究者たちはすぐに、この進歩を最大流量問題にどのように適用するかを研究し始めました。道路網を電線の網と考えてください。利用可能な容量があまりない道路では抵抗が加わり、電子が道路を移動できなくなります。 Spielman 氏と Teng 氏の研究のおかげで、これらの電線を流れる電流を素早く計算することができ、このモデルは高速道路を通る最大車両流量の大まかな特性を備えています。 (現在の問題ではワイヤの容量に厳密な制限がないため、まったく同じにはなりません。)

そして、この初期フローを生成した後、Ford と Fulkerson の組み合わせアルゴリズムのように容量を再調整できます。次に、各ワイヤの抵抗をリセットしてこれらの変化の量を反映し、新しく生成された回路の問題を解決できます。

一度に 1 つのネットワーク ブロックを変更する組み合わせ方法とは異なり、Spielman と Teng の最適化方法では、一度にネットワーク全体のスキャンを完了します。これにより、各ステップがより効率的になり、最大値に到達するために必要な合計ステップ数が少なくなります。 2008 年、Google の Samuel Daitch 氏と Spielman 氏はこのアプローチを使用して、最大フロー m^1.5 という以前の限界に近づきました。 2013 年、Mądry は、このアプローチをさらに進化させ、低容量ネットワークの m^1.5 を突破し、実行時間を約 m^1.43 の倍数にまで増加させました。 「衝撃だ」とラオ氏は語った。

その後数年間、研究者たちはこの方法をさらに拡張しましたが、結果は m^1.33 のままでした。彼らは、この指数が根本的な限界であるかどうか疑問に思い始めました。

最大フロー アルゴリズムの考えられる最速の実行時間は、ネットワークの記述に m の倍数のステップが必要であるため、m 回 (つまり、m^1.0) になります。これを線形時間と呼びます。しかし、多くの研究者にとって、このような驚くほど高速なアルゴリズムは考えられないことでした。 「これが実現可能だと信じる十分な理由はない」とスピルマン氏は語った。

最小限に抑え、再利用し、リサイクルする

新しい論文の著者らは、ダイチ氏とスピルマン氏のアプローチにはさらなる利点があると主張している。 Mądry 氏は、最大フローの問題を解決するために必要なステップ数を削減するためにこれを使用しましたが、この削減にはコストがかかりました。各ステップで、ネットワーク全体を書き直し、電力フローの問題を最初から解決する必要がありました。

このアプローチでは、アルゴリズムが内部で何を実行しているかに関係なく、Spielman と Teng のアルゴリズムをブラック ボックスとして扱います。 6 人の研究者は、アルゴリズムの核心を詳しく調べ、そのコンポーネントを最大フロー問題に適応させることを決定しました。研究者たちは、これらのコンポーネントによって、与えられた量の材料を輸送する最も安価な方法を見つけるという、より難しい「最小コスト問題」さえも解決できるのではないかと考えている。コンピューター科学者は、最小コストアルゴリズムであれば最大フロー問題を解決できることをずっと前から知っていた。

他の最適化手法と同様に、研究者らは、リンク コストと容量の関数であるフローの「エネルギー」という概念を提案しました。トラフィックを高価な低容量リンクから安価な大容量リンクに移行すると、システムの総エネルギーが削減されます。

流れをより低いエネルギー状態へ素早く動かす方法を見つけるために、研究者たちはこの最適化アプローチと従来の組み合わせの考え方を組み合わせました。後者は、一度にネットワークの一部のみを変更するため、以前のステップの作業の一部を再利用できる可能性が提供されます。

各ステップで、アルゴリズムはエネルギーを削減するサイクル、つまり同じポイントで開始および終了するパスを探します。基本的な考え方は単純です。シカゴからニューヨークまで有料道路を建設し、その後、より安価な高速道路があることを発見したとします。この時点で、ニューヨークがループに追加され、シカゴまでの高価な道路に沿って走り、その後、より安価なルートに沿って戻ってループを形成します。これにより、高価な経路が置き換えられ、交通の総コストが削減されます。

この方法は電気的方法よりも多くのステップを必要とするため、一見すると「後戻りしているように」聞こえると、カナダのビクトリア大学のヴァレリー・キング氏は言う。これを補うために、アルゴリズムはネットワーク全体を調べるのにかかる時間よりも速く、各ステップで適切なサイクルを見つける必要があります。

これが Spielman と Teng のアルゴリズムの仕組みです。彼らのアルゴリズムは、「低伸張スパニングツリー」を使用した新しいアプローチを提供します。これはアルゴリズムの鍵であり、ネットワークの最も顕著な特徴の多くを捉えることができます。このようなツリーが与えられた場合、ツリーの外側にリンクを追加することで、少なくとも 1 つの良好なサイクルを構築することが常に可能です。したがって、スケーリングの低いスパニング ツリーを使用すると、考慮する必要があるサイクルの数を大幅に減らすことができます。

それでも、アルゴリズムを高速に実行するために、チームは各ステップで完全に新しいスパニングツリーを構築することはできませんでした。代わりに、以前の計算のほとんどが再利用されるように、各新しいサイクルがスパニング ツリーに小さな波及効果しか与えないようにする必要があります。このレベルの制御を達成することは「根本的な困難」だと、スタンフォード大学の大学院生で論文の著者の一人であるヤン・リウ氏は述べた。

最終的に、研究者らは「ほぼ線形」な時間で実行されるアルゴリズムを作成しました。これは、ネットワークが大きくなるにつれて実行時間が m に近づくことを意味します。

このアルゴリズムは、Spielman 氏と Teng 氏から多くのアイデアを借用し、それらを組み合わせてまったく新しいものにしています。スピルマン氏は、これまで馬車しか見たことがない人にとって、今日のアルゴリズムは自動車のようなものだと語った。 「私は、それに座る場所があり、車輪があり、何か動かすものがあったことを知りました。しかし、馬の代わりにエンジンが付いていました。」

チームの分析は長くて複雑だが、他の研究者もすぐにこの問題を単純化するために取り組むだろうとラオ氏は推測している。 「今後数年間ですべてがより清潔になり、より良くなるだろうというのが私の考えです」と彼は語った。

アルゴリズムが簡素化されると、コンピューター科学者はそれをさまざまな問題を解決するアルゴリズムのサブルーチンとして使い始めるかもしれないとスピルマン氏は言う。 「これを迅速に実行できることがわかったので、人々はこれまで考えもしなかったさまざまなアプリケーションを見つけるでしょう。」

さらに、最大フロー問題に対するアルゴリズムの驚異的な高速化は、アルゴリズム理論における他の中核問題に対するスピルマンの希望となった。「他に何ができるだろうか？」