Gibt es einen anderen Algorithmus, dessen Laufzeit im ungünstigsten Fall exponentiell ist, während er in der Praxis sehr gut funktioniert, außer dem Simplex-Algorithmus?

9

Wir nennen einen Algorithmus im Allgemeinen "guten Algorithmus", wenn seine Laufzeit im schlimmsten Fall polynomisch ist. In einigen Fällen (z. B. Simplex-Algorithmus) kann der Worst-Case des Algorithmus zwar exponentiell sein, in der Praxis jedoch sehr gut funktionieren.

Gibt es andere (deterministische) Beispiele für diese Situation als den Simplex-Algorithmus?

ds.algorithms Arman
quelle
1
Sie könnten an einer verwandten Frage interessiert sein: cstheory.stackexchange.com/questions/305/…
Radu GRIGore

Antworten:

13

Moderne SAT-Lösungsalgorithmen können die meisten Instanzen recht schnell lösen, obwohl die Laufzeit im ungünstigsten Fall natürlich exponentiell ist. In diesem Fall ist die praktische Geschwindigkeit jedoch eher ein Ergebnis jahrelanger Algorithmusentwicklung als die eines einzelnen eleganten Algorithmus. Während ich verstanden habe, dass konfliktgesteuertes Klausellernen einen großen Leistungssprung bei SAT-Lösern verursachte, wurden die späteren Verbesserungen oft durch den geschickten Einsatz verschiedener Heuristiken in den Algorithmen erreicht.

Janne H. Korhonen
quelle
13

k

Suresh Venkat
quelle
13

Die Inferenz vom Hindley-Milner-Typ ist EXPTIME-vollständig, aber in den Programmen, die normalerweise geschrieben werden, ist sie ziemlich linear.

Neel Krishnaswami
quelle
1
Ist das nicht ein bisschen anders? Ich erinnere mich, dass wir eine notwendige Bedingung für eine schlechte Leistung von Hindley-Milner charakterisieren könnten (tief verschachtelte Lets). Der Grund, warum HM in der Praxis gut ist, ist, dass diese Verschachtelung in der Praxis ziemlich niedrig ist (normalerweise rücken wir im Laufe der Zeit mehr ein tiefer in die Bindungen eintauchen und nervös werden, wenn wir uns dem rechten Rand des Bildschirms nähern ...) Zugegeben, ich habe diese Behauptung schon einmal aus dem Gedächtnis gemacht und konnte zuletzt die Referenz dafür nicht wiederherstellen.
Rob Simmons
2
Nein, das ist keine notwendige Bedingung. Sie können eine Folge von Let-Bindungen (ohne Verschachtelung!) Angeben, sodass die Größe des abgeleiteten Typs mit jedem zusätzlichen Eintrag in der Folge quadriert wird. Ein Beispiel finden Sie unter cstheory.stackexchange.com/questions/2428/… .
Neel Krishnaswami
Das Beispiel ist in SML, und ich bin besser mit der Art und Weise vertraut, wie OCaml Dinge tut, aber wenn diese Folge von Bindungen "let" wäre, dann denke ich, dass sie verschachtelt wären . Nur weil sie globale Funktionen definieren, sind sie es nicht, aber hier findet eine implizite Verschachtelung statt: Eine bestimmte Definition hat Zugriff auf alle darüber liegenden Definitionen und keine der unten aufgeführten.
Amnn
1
@amnn: Die Verschachtelung, auf die Bezug genommen wurde, war Verschachtelung in der Form, die gebunden wird - dh let z = (let y = e in e') in e''im Gegensatz zu als let y = e in let z = e' in e''.
Neel Krishnaswami
9

Brendan McKays Nauty - Programm (No AUTomorphisms, Yes?) Löst das kanonische Beschriftungsproblem von Graphen (gleichzeitige Lösung der Probleme mit Graph Isomorphism und Graph Automorphism) und weist eine exponentielle Worst-Case-Leistung auf (Miyazaki, 1996). Es funktioniert jedoch sehr schnell für die meisten Grafiken, insbesondere für solche mit einigen Automorphismen.

Insbesondere beginnt der Algorithmus mit der Aufteilung der Eckpunkte nach Grad und dann nach Grad zwischen den einzelnen Teilen. Wenn sich dieser Prozess stabilisiert, muss eine Auswahl getroffen werden, um einen Scheitelpunkt in einem nicht trivialen Teil zu unterscheiden, und dies führt zu einem exponentiellen Verhalten. In den meisten Diagrammen ist die Tiefe dieses Verzweigungsvorgangs gering.

Derrick Stolee
quelle
Ich dachte, dass Nauty auch etwas Zufälliges benutzt, um bei der Verfeinerung zu helfen? In diesem Fall ist dies möglicherweise sehr analog zum Simplex-Algorithmus (obwohl es offensichtlich keine Vorstellung von einer geglätteten Analyse für den Graphisomorphismus gibt).
Joshua Grochow
1
Es wird keine Zufälligkeit verwendet, da eine konsistente kanonische Kennzeichnung erforderlich ist. Es kann jedoch eine benutzerdefinierte vertexinvariante Prozedur verwenden, um die Partitionierung der Vertices zu erleichtern. Manchmal sieht diese Invariante zufällig aus, wie sie erzeugt wurde (häufig ist sie eine komplizierte Funktion bei Sequenzen mit Entfernungsgrad), aber das dient nur dazu, Kollisionen zu reduzieren.
Derrick Stolee
1
Diese Vertex-Invariante kann mit den Anti-Cycling-Regeln des Simplex-Algorithmus verglichen werden.
Derrick Stolee
4

Einige Algorithmen für einfache stochastische Spiele funktionieren in der Praxis gut, obwohl sie exponentielle Worst-Case-Laufzeiten haben. Natürlich hängt dieses Problem in gewissem Sinne mit der linearen Programmierung zusammen, obwohl nicht bekannt ist, dass es sich um eine Polynomzeit handelt.

Peter Shor
quelle
1

Es gibt einen Algorithmus zum Auffinden gemischter Nash-Gleichgewichte, der dem Simplex-Algorithmus für LPs ähnelt. (Ich vergesse den Namen.) Es hat eine exponentielle Worst-Case-Komplexität, aber ich habe ein vages Gedächtnis, dass es sich in der Praxis oft gut verhält.

Warren Schudy
quelle
Meinen Sie den Lemke-Howson-Algorithmus?
Rahul Savani
1

Das Verpacken von Behältern (viele Varianten) ist ein Problem, dessen Komplexität als NP-hart bekannt ist:

http://en.wikipedia.org/wiki/Bin_packing_problem

Viele Heuristiken, wenn sie auf "praktische" Versionen angewendet werden, sind jedoch sehr gut. Für das eindimensionale Verpacken von Behältern werden einige dieser Heuristiken wie die Erstanpassung verwendet. First-Fit abnehmend; beste Passform; Best-Fit-Abnahmen sind als Themen, die den Schülern gezeigt werden sollen, sehr ansprechend. Die Schüler können oft einige der grundlegenden Heuristiken für sich selbst entdecken.

Joseph Malkevitch
quelle
Es gibt viele Beispiele, auch wenn das Problem NP-vollständig ist, können einfache Algorithmen damit umgehen. Insbesondere mit Approximationsalgorithmen. Aber ich suche tatsächlich nach Exponentialzeitalgorithmen. Ihr Beispiel bezieht sich auf ein schwieriges Problem, das mit einfachen Algorithmen leicht zu lösen ist. Vielleicht gibt es einen exponentiellen Zeitalgorithmus, um das Packen von Behältern (oder ein anderes Problem) genau zu lösen. und in der Praxis dauert es Polynomzeit.
Arman
0

Der Persistenzalgorithmus (ursprünglich von Edelsbrunner-Letscher-Zomorodian, mit vielen Variationen seitdem) ist im schlimmsten Fall kubisch, scheint jedoch vom Experimentieren normalerweise in linearer Zeit zu laufen.


quelle