「歴史的なアルゴリズムが最短経路問題の突破口を開くのに役立つ」

歴史的なアルゴリズムが最短経路問題の突破口を開くのに役立つ can be condensed to 歴史的なアルゴリズムが最短経路問題に役立つ

.fav_bar { float:left; border:1px solid #a7b1b5; margin-top:10px; margin-bottom:20px; } .fav_bar span.fav_bar-label { text-align:center; padding:8px 0px 0px 0px; float:left; margin-left:-1px; border-right:1px dotted #a7b1b5; border-left:1px solid #a7b1b5; display:block; width:69px; height:24px; color:#6e7476; font-weight:bold; font-size:12px; text-transform:uppercase; font-family:Arial, Helvetica, sans-serif; } .fav_bar a, #plus-one { float:left; border-right:1px dotted #a7b1b5; display:block; width:36px; height:32px; text-indent:-9999px; } .fav_bar a.fav_de { background: url(../images/icons/de.gif) no-repeat 0 0 #fff } .fav_bar a.fav_de:hover { background: url(../images/icons/de.gif) no-repeat 0 0 #e6e9ea } .fav_bar a.fav_acm_digital { background:url(‘../images/icons/acm_digital_library.gif’) no-repeat 0px 0px #FFF; } .fav_bar a.fav_acm_digital:hover { background:url(‘../images/icons/acm_digital_library.gif’) no-repeat 0px 0px #e6e9ea; } .fav_bar a.fav_pdf { background:url(‘../images/icons/pdf.gif’) no-repeat 0px 0px #FFF; } .fav_bar a.fav_pdf:hover { background:url(‘../images/icons/pdf.gif’) no-repeat 0px 0px #e6e9ea; } .fav_bar a.fav_more .at-icon-wrapper{ height: 33px !important ; width: 35px !important; padding: 0 !important; border-right: none !important; } .a2a_kit { line-height: 24px !important; width: unset !important; height: unset !important; padding: 0 !important; border-right: unset !important; border-left: unset !important; } .fav_bar .a2a_kit a .a2a_svg { margin-left: 7px; margin-top: 4px; padding: unset !important; }

コンピュータサイエンスのパイオニアであるエドスガー・ダイクストラのアルゴリズムは、その優れた効率性により、多くのコンピュータサブルーチンの基盤となっています。しかし、要件のわずかな変更でも、これらの概念的にシンプルな定式化は正確な答えを提供できなくなることがあります。代替アルゴリズムは正しい答えを提供しますが、頻繁に数桁遅くなります。

組合せ技術の最近の突破により、これらの初期のアルゴリズムを復活させる方法が示されました。

最短経路問題は、アルゴリズムの要件の具体的な内容に対する感度の良い例を提供します。ナビゲーションからチップのレイアウトまで多くのアプリケーションの基盤となるこれらの問題は、次のホップごとに適用される重みに基づいて最低コストを提供するネットワークのパスを見つけるというシンプルな基本的な命題を提供します。その重み付けは、物理的な世界では常に正の値を反映します。

• 「UCサンディエゴのコンピュータサイエンティストが、毎年15億台の廃棄されたスマートフォンの問題に取り組む」
• 「AIパワーパラドックス」 AI（人工知能）パワーパラドックス
• このスタートアップは、クラウドコンピューティングからの廃熱を巧妙に再利用する方法を開発しました

問題は、パスに負の重みがあるネットワークに遭遇した場合に発生します。ニュージャージー州ニューブランズウィックのラトガーズ大学のコンピュータサイエンス助教授であるアーロン・バーンスタインは、「エッジの重みがコストに対応する状況では、負の重みは自然です」と述べています。

例えば、金融では、通貨やオプション取引で、あるシーケンスでの買い物や売り物が別の経路よりも収益性が高い場合があります。これらは、検索アルゴリズムが十分に高速であれば、負の重みを使用してモデル化することができます。しかし、これらの負の重みは、ダイクストラの最短経路アルゴリズムを混乱させる可能性があります。

問題は、1950年代に開発されたアルゴリズムの効率的な利巧さにあります。このアルゴリズムは、しばしば負の重みのパスを考慮から除外します。それは順番に各頂点を処理し、戻らないため、高い重みと負の重みを持つものが低い重みの1つのホップよりも低いコストを持つかどうかを考慮しないかもしれません。

改訂された手法、通常はベルマン-フォードアルゴリズムとして知られています。負の重みの接続を正しく処理しますが、ノードの処理能力に依存しているため、ダイクストラの技術のような生の効率を持ちません。ベルマン-フォードアルゴリズムでは、多くのステップが必要です。その合計は、ノードと頂点の数の積に基づいています。

コンピュータ科学者は、これらの長年のアルゴリズムで使用される組み合わせ技術と類似した手法を使用して、この問題の効率的な解決策を見つけようと試みましたが、それらを大幅に縮小することには失敗しました。過去数十年にわたり、グラフを行列の係数として表現し、線形代数のツールを使用することで、より大きな進展がなされてきました。このような技術は、最短経路の特定だけでなく、パイプや輸送路のネットワークを通じたフローの最大化など、さまざまな経路関連の問題に対して成功を収めています。これは、昨年のコンピュータ科学基礎シンポジウム（FOCS）で発表された論文で示されています。

ジョージア工科大学の博士課程の学生であるLi Chenは、スイスのETHチューリッヒ、スタンフォード大学、トロント大学の数学者と共同で、ニューラルネットワークのトレーニングに使用されるアプローチと同じ勾配降下法に基づくメカニズムを開発しました。このアルゴリズムは、ネットワークを最大化するための最適な解答に徐々に移動することに成功しました。このアルゴリズムは、計算時間をほぼ線形のパフォーマンスにまで短縮しました。

最適化に基づく最近開発された手法の欠点は、従来の組み合わせアルゴリズムよりも実装と理解が困難であることです。「このタイプのアプローチでは、多くの動的アルゴリズムが使用されることが多く、複雑になりがちです。多くの動くパーツを組み合わせる必要があります」と、ドイツのザールブリュッケンにあるマックス・プランク計算機科学研究所の所長であるDanupon Nanongkaiは述べています。

ベルマン-フォードアルゴリズムは、負の重みの接続を適切に処理しますが、ダイクストラの手法と比べて効率が低いです。

Bernstein、Nanongkai、およびコペンハーゲン大学のコンピュータ科学の准教授であるChristian Wulff-Nilsenは、負の重みを持つ単一ソース最短経路問題に効率的な組み合わせ解を見つけることができるかどうかを確認したかったです。

チームは最初に、Andrew Goldbergと同僚たちによる1990年代初頭の論文に目を向けました。この論文では、重みの値を正にスケーリングしてダイクストラの手法を使用して最短経路を見つけることを可能にするように複雑さを削減していました。「最初の目標は、Goldbergの結果を少し改善するだけでしたが、最終的にはすべてが整った後にすべてができることがわかりました」と、Nanongkaiは述べています。

スケーリングのための長年の手法の1つは価格関数の使用ですが、価格を効率的に割り当て、重み間の関係を歪めない方法が難しい場合があります。チームは、低直径を持つ特定のタイプのグラフに効率的なアルゴリズムを見つけました。それが大きなブレイクスルーの鍵となり、他の問題に対してより効率的な組み合わせ解を見つける手助けをする可能性があります。

低直径グラフは、パスが短く、互いに強く接続されているように見える構造です。低直径の特性は、グラフを複数のコンピュータに分散処理できるようにセクションに分割する方法を見つけるための重要な要素となっています。強く接続されたコンポーネントを同じマシンに保つことで、ネットワークトラフィックを最小限に抑えることができます。

チームは、入力グラフを低直径の部分グラフのクラスタに分割し、価格関数の一連のステップを使用して重みを逐次的に再構築することで、ほぼ完全にダイクストラのアルゴリズムを使用して処理できる再構築されたグラフを作成することができることを見つけました。これには、強く接続されたクラスタを互いに接続しない正方向のパスのみを持つ有向非巡回グラフに変換するための、負の重みを持つパスのランダムな削除が含まれます。この形式は、最速のアルゴリズムの使用を可能にするツールへの入り口を開くために選択されました。後のフェーズでは、欠けている負の重みのエッジを再導入します。これらのパスの数は、実行時間に比較的少ない影響を与えるベルマン-フォードアルゴリズムで処理することができます。

有向グラフのために構築された低直径分解の形式は、解決策に基本的な役割を果たしましたが、Bernsteinは、それが最初から明らかではなかったと述べています。伝統的な分解は、無向グラフに対して開発されたものでした。「これを調べ始めたとき、この文脈での低直径分解が何を意味するのかは明確ではなく、関連のある概念であるとは思いつきませんでした。異なる方向から取り組み始め、低直径の特性を持つグラフに取り組んでいることがわかったため、それがどのように使用できるかが見えてきました」と彼は述べています。

この分解により、価格関数の計算を複数のステップに分割することが可能になり、1つのステップアプローチによる歪みのリスクを冒さずに効率的に行うことができました。

「ある意味では、私たちのアルゴリズムはグラフを分解し、いくつかの負のエッジ重みで問題を解決し、それを修正し、次に進むということを続けています。常に負のエッジ重みが少ないことを確認し、それらを解決し、次に進み、ますます少なくなるようにしています」とBernsteinは付け加えています。

コアアルゴリズムは、グラフ内の頂点の数に対して対数的な依存関係を持ついくつかの要素を持ち、それぞれ改善の余地があります。

ウルフ・ニルセンは、「この進行的な改善は、価格関数を何度も使用してエッジを変更することによって行われます。したがって、単一の価格点を見つけるだけではありません」と述べています。

その結果、このアルゴリズムはほぼ線形の性能を持ち、昨年の同じFOCSイベントで陳が発表した最大フローの最適化技術と比較して、わずかに優れた性能を持っています。両者はシンポジウムでベストペーパー賞を共有し、その相対的な簡易性のために、多くの教師が組み合わせアルゴリズムと同僚を自分たちの授業に取り入れています。

ただし、コアアルゴリズムはほぼ線形ですが、グラフ内の頂点の数に対して対数的な依存関係を持つ要素がいくつかあり、それぞれ改善の余地があります。サールランド大学のカール・ブリングマンとアレハンドロ・カシスは、イスラエルのワイツマン科学研究所のニック・フィッシャーと協力し、4月に発表された論文で8つの対数要因のうち6つを最適化することに成功しました。それらのうちいくつかは単純なものとして考えられ、例えば要素を基にしたダイクストラアルゴリズムに提示される順序を変更するなどですが、他のものは「より複雑」でした。

ブリングマンと同僚の研究では、より効率的なアルゴリズムのためのより直接的な分解形式と、この特定の問題には使用しなかった異なる形式の低直径分解を提案しました。

このようなアプローチは、無向グラフの作業と同様に有向グラフに対しても低直径分解として有用なものになるかもしれません。バーンスタインは、「低直径分解がこのように使用されることに興奮している人々がいました。人々は他の有向グラフの問題にこれを使用することについて私たち全員に話しかけてくれました」と述べています。

低直径分解をフルサークルで取り上げると、バーンスタイン、ナノンカイ、およびその他の研究者は、最短経路計算の分散アルゴリズムを示す論文を3月に発表しました。しかし、フロー最大化などの問題に対する効率的な組合せ的な解決策を見つけることは依然として困難であり、より複雑さが増し、動的データ構造の操作を必要とする技術に依存する最適化ベースのアプローチは、コンピュータサイエンスの主要なツールのままです。

バーンスタインは、「最適化技術は、一部の問題を解決するための唯一の方法です。私たちのアルゴリズムは1つの問題に対する組合せ的な解決策を示しましたが、それはまだ特定の問題です。例えば、最小コストフローの場合、私たちはまだ組合せ的にどのように行うかのアイデアを持っていません」と述べています。

さらに読む

Bernstein, A., Nanongkai, D., and Wulff-Nilsen, C. Negative-Weight Single-Source Shortest Paths in Near-Linear Time Proceedings of the 63 rd IEEE Annual Symp. on Foundations of Computer Science (2022), 600–611

Chen, L., Kyng, R., Liu, Y.P., Peng, R., Probst Gutenberg, M., and Sachdeva, S. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time Proceedings of the 63 rd IEEE Annual Symp. on Foundations of Computer Science (2022), 612–623

Bringmann, K., Cassis, A., and Fischer, N. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! ArXiv 2304.05279 (2023)

Linial, N. and Saks, M. Low-Diameter Graph Decompositions Combinatorica 13 (4) (1993) 441–454

トップへ戻る

著者

クリス・エドワーズは、イギリスのサリーを拠点とするライターで、電子機器、IT、合成生物学について報告しています。

©2023 ACM 0001-0782/23/8

この作品の一部または全部を個人的または教室利用のためにデジタルまたは印刷物の複製することは、料金が発生せずに許可されますが、複製物が営利または商業的な利益のために作成または配布されず、複製物にはこの通知と最初のページの完全な引用が含まれていることが条件です。ACM以外の所有者によるこの作品の著作権は尊重されなければなりません。クレジット付きで要約することは許可されています。それ以外の場合は、事前に具体的な許可と/または料金が必要です。許可を求めるには、[email protected]に連絡するか、ファックス（212）869-0481に送信してください。

デジタル図書館はAssociation for Computing Machineryによって公開されています。著作権所有者：© 2023 ACM, Inc.

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!