コンピュータの基本的な問題、最大流量問題が画期的な進歩を遂げた: 新しいアルゴリズムは「途方もなく速い」

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

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

この質問は、インターネット データ ストリーミング、航空会社のスケジュール管理、さらには求職者と空きポジションのマッチングなど、さまざまな用途につながります。この新しい論文は、最大流量の問題と、コストを最小限に抑えながら最大流量を処理するというより一般的な問題の両方を扱います。これら 2 つの疑問は、長年にわたってアルゴリズム テクノロジーの多くの重要な進歩を引き起こしてきました。 「それが、私たちがアルゴリズムの分野で研究を続ける理由のほとんどです。」とシュピルマン氏は言いました。新しいアルゴリズムは両方の問題を「ほぼ直線的な」時間で解決します。つまり、アルゴリズムの実行時間は録音に必要な時間にほぼ比例します。ネットワークの詳細。これらの問題を解決する他のアルゴリズムは、考えられるすべてのネットワークでこの速度を達成できません。カリフォルニア大学バークレー校のサティシュ・ラオ氏は、この結果に飛び上がったと述べ、「ただただ驚くべきことだ。」と述べた。これまで考えたこともなかったさまざまな応用問題を解決することを考え始める時期が来ました。

アルゴリズム速度の改善は、現実世界で遭遇するネットワークよりもはるかに大規模なネットワークにのみ適用できるため、現時点では、新しい方法は主に理論的な改善です。交通問題は（少なくともコストの最小化を考慮せずに）すでにすぐに解決できます。開発者6人のうちの1人であるカナダのウォータールー大学のリチャード・ペン氏は、新しいアルゴリズムが1年以内に実用化される可能性があると予想している。

研究者の中には、今後数年のうちにコンピュータ科学者がそれをより実用的で、おそらくはさらに高速化する方法を見つけるかもしれないと信じている人もいます。

MITのアレクサンダー・マンドリー氏は、今後改良が加えられたとしても、新しい論文は「スラムダンクコンテストで最もエキサイティングなダンク」であると述べた。彼はそれが基本的に最高だったと言いました。」

One path at a time

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

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

次に、アルゴリズムは、セグメントの容量の一部が現在使用されていることを反映するように、これらのセグメントの容量を変更します。セグメントの容量から送られるトラックの数が減算されます。現在、高速道路の収容力は 3 ですが、2 車線の橋の収容力はゼロです。同時に、アルゴリズムはこれらの道路の逆方向の容量に 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への障壁は深く根付いています」と、新しい論文の著者の1人であるトロント大学のスシャント・サクデヴァ氏は述べた。さまざまな方法。

組み合わせから微積分へ

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

Spielman と Teng は、最大流量の問題ではなく、特定の抵抗を持つ各ワイヤを通過するという密接に関連した問題を解決する高速最適化アルゴリズムを開発しました。最低のエネルギー。サクデワ氏は、スピルマン氏とテン氏の進歩は「重大な瞬間」だと述べた。

# ネットワークの最大トラフィックと最小コストを決定する超高速アルゴリズムを作成したチーム メンバー (左上から時計回りに)コーナー）：ヤン・リウ、リー・チェン、ラスムス・キョ​​ン、マクシミリアン・プロブスト・グーテンベルク、リチャード・ペン、スシャント・サクデヴァ。

# 研究者たちはすぐに、この進歩を最大流量の問題に適用する方法を検討し始めました。道路網は、利用可能な容量があまりない道路に抵抗を追加し、電子が道路を通過するのを妨げるワイヤのネットワークとして考えてください。 Spielman と Teng の研究のおかげで、これらのワイヤを流れる電流を迅速に計算することができ、このモデルには高速道路を通る車両の流れを最大にするための大まかな特性が備わっています。 (現在の問題によりワイヤの容量に厳密な制限が設けられていないため、これらはまったく同じにはなりません。)

次に、この初期フローを生成した後、次のことができます。フォードとフルカーソンの組み合わせのようなことを行います。アルゴリズムは同じように容量を再スケールします。次に、各ワイヤの抵抗をリセットして、これらの変化量を反映し、新しく作成された回路の問題を解決します。

一度に 1 つのネットワーク ブロックを変更する組み合わせアプローチとは異なり、Spielman と Teng の最適化手法では、毎回ネットワーク全体のスキャンが完了します。これにより各ステップの効率が向上し、最大値に到達するために必要な合計ステップ数が少なくなります。 2008 年に、Google の Samuel Daich と Spielman がこの方法を使用しました。これは、基本的に以前の最大トラフィック制限である m^1.5 と一致していました。 2013 年、Mądry はこのアプローチをさらに進め、低容量ネットワーク向けに m^1.5 を超え、ランタイムを約 m^1.43 の倍数に改善しました。 「衝撃的だ」とラオさんは語った。

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

最大フロー アルゴリズムの場合、ネットワークの書き込みには m の倍数のステップが必要となるため、想像できる最速の実行時間は m 倍 (つまり、m^1.0) になるはずです。これを線形時間と呼びます。しかし、多くの研究者にとって、このような非常に高速なアルゴリズムは考えられないようでした。 「我々がこれを実現できると信じる正当な理由はない」とスピルマン氏は語った。

縮小、再利用、リサイクル

この新しい論文の著者は、Daitch と Spielman のアプローチにはさらなる利点があると信じています。 Mandry は、最大流量問題を解決するために必要なステップ数を減らすためにこれを使用していましたが、この削減には代償が伴いました。各ステップでネットワーク全体を書き直す必要があり、電力潮流問題を最初から解決する必要がありました。

このアプローチでは、アルゴリズム内で何が起こっているかに関係なく、Spielman と Teng のアルゴリズムをブラック ボックスとして扱います。 6 人の研究者は、アルゴリズムの核心を掘り下げ、そのコンポーネントを最大流量問題に合わせて調整することにしました。彼らは、これらのコンポーネントによって、より困難な「最小コスト問題」、つまり、与えられた量の物質を輸送する最も安価な方法を見つけることさえも解決できるのではないかと考えています。最大流量問題 質問

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

流れをより低いエネルギー状態に迅速に移行する方法を見つけるために、研究者らは、この最適化アプローチと古い組み合わせビューを組み合わせました。後者では、一度にネットワークの一部だけを変更するため、前のステップの作業の一部を再利用できるようになります。

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

この方法は「電気的方法」よりも多くの手順を使用するため、一見すると「後退しているように聞こえる」とカナダのビクトリア大学のヴァレリー・キング氏は言います。それを補うために、アルゴリズムはすべてのステップで、ネットワーク全体を調べるよりも速く、信じられないほど早く、適切なループを見つけなければなりません。

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

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

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

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

ラオチームの分析は長くて複雑だったが、他の研究者が問題を単純化するためにすぐに掘り下げてくれるだろうと推測した。 「私の感覚では、今後数年ですべてがよりクリーンになり、より良くなるだろう」とスピルマン氏は述べ、アルゴリズムが単純化されれば、コンピューター科学者はさまざまな問題を解決するアルゴリズムのサブルーチンとして使用され始める可能性があると述べた。 「これを非常に迅速に実行できることがわかったので、人々はこれまで思いつかなかったあらゆる種類のアプリケーションを見つけるでしょう。」

さらに、アルゴリズムは次のとおりです。最大流量問題により、スピルマンはアルゴリズム理論の他の核心問題を楽しみにしました。「他に何ができるだろうか?」

以上がコンピュータの基本的な問題、最大流量問題が画期的な進歩を遂げた: 新しいアルゴリズムは「途方もなく速い」の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。