アウトオブキルタ法

アウトオブキルタ法について

アウトオブキルタ法（英: out-of-kilter algorithm）は、フローネットワークの最小費用流問題に対処するためのアルゴリズムの一つです。このアルゴリズムは1961年にデルバード・レイ・ファルカーソンによって最初に提案されました。この方法は、ネットワーク内の流れを最適化する際に非常に有用であり、さまざまな分野に応用されています。特に輸送システムや人員配置などの問題に広く利用されています。

フローネットワークとは、頂点と枝から構成される構造で、各枝には一定の費用と容量が設定されています。その中で、特定の2点間における最短経路を求める問題が発生します。アウトオブキルタ法では、「アウトオブキルタ」と呼ばれる状態の枝を特定し、それに基づいて流れを修正していきます。この過程は、すべての枝が「インキルタ」となるまで続き、その結果として最小費用のフローが得られるようになります。

アルゴリズムの詳細

アウトオブキルタ法のプロセスは、まず初めに単一の閉路とその頂点の集合を取得することから始まります。この段階で、アウトオブキルタな枝を見つけ出します。次に、もしキルタ内の枝に対してフローを増加または減少させる余地があれば、フローを調整するための道を探します。このような道が存在しない場合、実行可能なフローは存在しないと判断されます。

この手順を繰り返し、全ての枝がインキルタになるまで続けます。その結果、最適なフローが得られるという仕組みです。

ネットワークの表現

一般的に、ネットワークはn個の頂点とm個の有向枝から成り立っています。例として、ある枝jが始点iと終点i1を持つ場合、これはj(i, i1)と表記されます。ここで、x(j)は枝jに流れるフローの量を示します。また、c−(j)とc+(j)はそれぞれ枝jのフローの下限および上限を示します。これによって、容量制約を設けることができます。

最適化問題

最低限のフロー量を把握することは重要であり、それに基づいて流れを制御します。もし与えられたフローxが特定の条件を満たす場合、フローは保存され循環フローと言われます。逆に別の条件を満たす場合、フローは実行可能と見なされます。

計算の複雑性

アウトオブキルタ法の計算量に関しては、反復処理がO(mU)という計算量になります。この計算は、主に最短経路の計算によって占められます。全体の計算量はO(m²U + mUn log(n))になります。

このアルゴリズムは、多くのフローネットワークの問題に対し効果的な解決策を提供するため、研究と実践の両方で広く利用されています。参考文献としては、藤重悟の『グラフ・ネットワーク・組合せ論』などが挙げられます。

もう一度検索