鉄道・道路・電力などあらゆる種類のネットワークについて最小のコストで最大のトランスポートフローを最高速で計算できるアルゴリズムが爆誕

スイス連邦工科大学チューリッヒ校のラスムス・キン氏率いる研究チームが鉄道、道路、電力など、あらゆる種類のネットワークにおいて最小のコストで最大の輸送フローを計算するほぼ完璧なアルゴリズムを作成しました。計算速度は、「数学的にこれ以上は不可能」という速さだとのことです。

Researchers at ETH Zurich develop the fastest possible flow algorithm | ETH Zurich
https://ethz.ch/en/news-and-events/eth-news/news/2024/06/researchers-at-eth-zurich-develop-the-fastest-possible-flow-algorithm.html

輸送フローアルゴリズムとは、例を挙げると東京から大阪までできるだけ多くの商品を輸送できる最速かつ最安のルートを探すようなアルゴリズムです。キン氏のアルゴリズムは鉄道や道路を使用した物品の輸送だけでなく、水やインターネットなどあらゆる種類のネットワークにおける最適な輸送フローを高速に計算することが可能です。

これまでも多数の研究者が輸送フローの最適化問題に取り組んできましたが、ネットワークが大きく複雑になるにつれて必要な計算量が爆発的に増加し、一定以上の規模のネットワークについては計算できなくなっていました。

キン氏のアルゴリズムでは計算量がネットワークのサイズにほぼ比例するとのこと。ランダウの記号で表すとネットワークのサイズをmとして2000年代まではO(m^1.5)の計算量が必要だったのが、2004年にO(m^1.33)になり、キン氏のアルゴリズムではネットワークのサイズが大きくなるにつれてO(m)に漸近します。

ネットワークを読み込むためにはO(m)の線形時間が必ず必要になるため、これ以上計算量を減らすことがほとんど不可能であり、「ほぼ完璧」なアルゴリズムだと評価されています。

キン氏のチームが2022年にこのアルゴリズムを発表した時点では接続が有向である固定された静的ネットワーク、つまり全ての道路が一方通行の都市のようなネットワークにのみ適用可能でしたが、研究チームは発表後も研究を重ね、2024年には時間とともに変化するネットワークや、新しい接続が追加されたり削除されたりするようなネットワークの最適化を行うことが可能になりました。

キン氏のアルゴリズムにより、最大フロー問題や最小コスト問題を始め、重要なネットワークフロー問題は全て最小コストフロー問題の特殊ケースとして処理できるようになったとのこと。キン氏の超高速アルゴリズムは、生物学における分子や脳内ネットワークのほか、人間の友情など動的かつ非常に急速に変化する複雑でデータ量の多いネットワーク問題を扱うための重要なステップとして評価されています。