アウトオブキルタ法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/05 15:31 UTC 版)
アウトオブキルタ法（アウトオブキルタほう、英: out-of-kilter algorithm）とは、フローネットワークにおける最小費用流問題を解くアルゴリズムの一種である。1961年にデルバード・レイ・ファルカーソンにより初めて提案された解法である[1][2]。頂点と枝からなるネットワークにおいて定常流を求める問題は、さまざまな事象を記述するために応用することができる。例として輸送システムや人員の配置割当などが挙げられる。一般的に枝には費用および容量が与えられている。そして、容量制約付きネットワーク内においてある2点間の最短経路を求めることがしばしば発生する。アウトオブキルタ法ではアウトオブキルタな枝を特定し、すべての枝がインキルタとなり、最小費用のフローが得られるまでその時点で得られているフローを修正していくこととなる。そのため、制約付きの有向ネットワークにおいて総費用が最小となるフローを求めることができる。
アルゴリズム
始めに、アウトオブキルタ法では単一の閉路およびその頂点の集合を得る。そしてアウトオブキルタな枝を探す。もしキルタ内の枝においてフローを増加あるいは減少させられるならば、それぞれフローを増加あるいは減少させる道を求める。もしそのような道が存在しなければ、実行可能なフローは存在しない。この手順はすべての枝がインキルタになるまで続け、やがて最適なフローが求まる。
今、
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) |
|||||
|---|---|---|---|---|---|
| グラフ理論 |
|
||||
| フローネットワーク |
|
- アウトオブキルタ法のページへのリンク
