Der Simplex-Algorithmus soll eine exponentielle Zeitkomplexität im ungünstigsten Fall haben. Dennoch wird es in der Praxis immer noch oft verwendet. Wie können Sie die durchschnittliche Zeitkomplexität für ein bestimmtes Problem bestimmen (gelöst mit Simplex).
Zum Beispiel, was ist die durchschnittliche Zeit Komplexität des maximalen Strömungsproblems mit Simplex-Algorithmus gelöst wird. (Wiki hat Zeitkomplexität für alle anderen Algorithmen)
Danke für Ihre Zeit.
Die durchschnittliche Fallkomplexität ist ziemlich schwierig zu analysieren und hängt von der Verteilung Ihres linearen Programms ab. Ich glaube, dass es unter einigen gebräuchlichen Verteilungen zu einer Polynomzeit wurde. Derzeit kann ich das Papier jedoch nicht finden.
BEARBEITEN : Ja, hier sind die Quellen:
Nocedal, J. und Wright, S. J. Numerische Optimierung. New York: Springer-Verlag, 1999.
Forsgren, A .; Gill, P. E .; und Wright, M. H. "Interior Methoden für die nichtlineare Optimierung." SIAM Rev. 44, 525-597, 2002.
Ich habe es im ersten Buch gelesen und anscheinend wurde es in einer separaten Zeitung (Forsgren) nachgewiesen. Sie können entweder in einer Universitätsbibliothek finden.
Wenn es noch interessant ist. Die Zeitkomplexität von Simplex ist O ((n + m) * n).
n - Anzahl der Variablen.
m - Ungleichheitsbedingungen.
Warum? Weil die Anzahl von Iterationen im Fall von n nicht mehr als n + m sein könnte Das ist eine obere Grenze für die Anzahl der Ecken.
Aber diese obere Grenze ist exponentiell in n.
Tags und Links algorithm time-complexity big-o simplex