シンプレックスアルゴリズムは、指数関数的な最悪の場合の時間計算量を持っていると言われています。それでも、実際にはまだよく使用されています。特定の問題の平均時間計算量をどのように決定できますか（シンプレックスで解決されます）。
たとえば、シンプレックスアルゴリズムで解決される最大フロー問題の平均時間計算量はどれくらいですか。（Wikiには、他のすべてのアルゴリズムの時間計算量があります）
お時間をいただきありがとうございます。
質問する
3490 次
2 に答える
6
平均的なケースの複雑さを分析するのはかなり難しく、線形計画法の分布に依存します。いくつかの一般的な分布の下では、多項式時間であることがわかったと思います。私は現在、その論文を見つけることができません。
編集：はい、ここにソースがあります：
Nocedal、J.およびWright、SJ数値最適化。ニューヨーク：Springer-Verlag、1999年。
Forsgren、A .; ギル、PE; and Wright、MH「非線形最適化のための内点法」。SIAM Rev. 44、525-597、2002。
私は最初の本でそれを読みました、そして明らかにそれは別の論文（Forsgren）で証明されました。どちらも大学の図書館で見つけることができます。
于 2011-12-28T00:05:32.923 に答える
2
それでも面白いなら。シンプレックスの時間計算量はO（（n + m）* n）です。
n-変数の数。
m-不等式制約。
なんで？頂点数の上限であるnの場合、反復回数はn+m以下である可能性があるためです。
しかし、この上限はnで指数関数的です。
于 2015-12-05T14:40:50.417 に答える