Simplex算法据说具有指数级最坏时间复杂度。尽管如此，它仍经常在实践中使用。如何确定使用Simplex解决某个问题的平均时间复杂度。
例如，使用Simplex算法解决最大流问题的平均时间复杂度是多少？（维基百科上有所有其他算法的时间复杂度）
感谢您花费时间。
如何确定单纯形时间复杂度（即最大流）
10
- Ben
2
听起来像是作业/测试问题。 - Jonathon Reinhart
3这实际上是一个非常深奥的问题，我不确定是否有人在此之前解决过。我非常想知道答案。+1 - templatetypedef
2个回答
6
平均情况下的复杂度很难分析，且取决于您的线性程序分布。我相信在一些常见分布下，其被证明为多项式时间。但我目前无法找到相关文件。
编辑：是的，这里是参考文献：
Nocedal，J.和Wright，S.J. 数值优化。纽约：Springer-Verlag，1999年。
Forsgren，A .; Gill，P.E。;和Wright，M.H. “非线性优化的内部方法。” SIAM Rev. 44，525-597，2002年。
我在第一本书中读到了这一点，显然它是在另一篇文章（Forsgren）中证明的。您可以在大学图书馆找到任一文献。
编辑：是的，这里是参考文献：
Nocedal，J.和Wright，S.J. 数值优化。纽约：Springer-Verlag，1999年。
Forsgren，A .; Gill，P.E。;和Wright，M.H. “非线性优化的内部方法。” SIAM Rev. 44，525-597，2002年。
我在第一本书中读到了这一点，显然它是在另一篇文章（Forsgren）中证明的。您可以在大学图书馆找到任一文献。
- tskuzzy
2
如果您还感兴趣的话，单纯形法的时间复杂度为O((n+m)*n)。
其中：
n - 变量的数量。
m - 不等式约束的数量。
为什么？因为在n是顶点数的上限的情况下，迭代次数不会超过n + m。
但是这个上限在n方面呈指数级增长。
其中：
n - 变量的数量。
m - 不等式约束的数量。
为什么？因为在n是顶点数的上限的情况下，迭代次数不会超过n + m。
但是这个上限在n方面呈指数级增长。
- Aivaras Gončarovas
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接