Bei welchen Algorithmen besteht eine große Lücke zwischen der theoretischen Analyse und der Realität?

52

Es gibt zwei Möglichkeiten, die Effizienz eines Algorithmus zu analysieren

  1. eine asymptotische Obergrenze für die Laufzeit zu setzen, und
  2. um es auszuführen und experimentelle Daten zu sammeln.

Ich frage mich, ob es bekannte Fälle gibt, in denen eine signifikante Lücke zwischen (1) und (2) besteht. Damit meine ich, dass entweder (a) die experimentellen Daten eine engere Asymptotik nahelegen oder (b) Algorithmen X und Y existieren, so dass die theoretische Analyse nahelegt, dass X viel besser als Y ist und die experimentellen Daten nahelegen, dass Y viel besser als Y ist X.

Da Experimente normalerweise das Verhalten von Durchschnittsfällen aufzeigen, erwarte ich, dass sich die interessantesten Antworten auf die Durchschnittsobergrenzen beziehen. Ich möchte jedoch möglicherweise interessante Antworten nicht ausschließen, die über verschiedene Grenzen sprechen, wie beispielsweise Noams Antwort zu Simplex.

Datenstrukturen einbeziehen. Bitte geben Sie ein Algo / ds pro Antwort ein.

Radu GRIGore
quelle
Es wäre hilfreich, wenn Sie klären würden, über welche Art von Obergrenzen Sie sprechen. Sprechen Sie nur von Problemen, bei denen es eine erhebliche Lücke zwischen den bekanntesten Ober- und Untergrenzen für die Zeitkomplexität im ungünstigsten Fall gibt? Oder schließen Sie auch Probleme ein, bei denen enge Grenzen für die Zeitkomplexität im schlimmsten Fall bekannt sind, die typischen Laufzeiten jedoch erheblich kürzer sind? Es kann interessanter sein, die geglättete Komplexität als die Komplexität im schlimmsten Fall zu betrachten. Experimentelle Ergebnisse zu „typischen“ Eingaben oder zufälligen Eingaben können die Existenz pathologischer Eingaben kaum widerlegen.
James King
In diesem Fall sollten meines Erachtens zwei Fragen getrennt gestellt werden: eine zu Lücken zwischen Worst-Case-Komplexität und Average-Case / Smoothed-Komplexität und eine zu Lücken zwischen theoretischer Average-Case / Smoothed-Komplexität und praktischen experimentellen Ergebnissen. Bearbeiten: Sie haben eine Bearbeitung vorgenommen, um dies zu beheben, während ich meinen Kommentar schrieb :)
James King

Antworten:

37

Das eklatanteste Beispiel ist natürlich die Simplex-Methode, die in der Praxis schnell abläuft und Mehrfachzeit suggeriert, theoretisch aber exponentielle Zeit in Anspruch nimmt. Dan Spielman hat gerade den Nevanlinna-Preis für die Erklärung dieses Geheimnisses erhalten.

Im Allgemeinen können viele Instanzen der Integer-Programmierung mit Standard-IP-Solvern recht gut gelöst werden, z. B. könnten kombinatorische Auktionen für die meisten Distributionen, die mit Eingaben von beträchtlicher Größe versucht wurden, gelöst werden - http://www.cis.upenn.edu/~mkearns /teaching/cgt/combinatorial-auctions-survey.pdf

Noam
quelle
3
Wurde eine explizite Familie linearer Programme gefunden, für die Simplex exponentielle Zeit benötigt?
Opt
1
Soweit ich weiß, gibt es viele explizite Familien, die exponentielle Zeit benötigen (z. B. das erste, das von Klee und Minty gegeben wurde: "Wie gut ist der Simplex-Algorithmus?", 1972). Für diese Ergebnisse ist jedoch die Wahl der Pivot-Regel relevant. Ich vermute, dass die meisten Verweise auf diese Ergebnisse in Spielmans und Tengs Artikel zu finden sind ( arxiv.org/abs/cs/0111050 ).
MRA
In diesem Artikel
Igor Shinkar 17.10.13
26

Groebner Basen . Die Laufzeit im ungünstigsten Fall ist doppelt exponentiell (in der Anzahl der Variablen). In der Praxis sind jedoch insbesondere bei gut strukturierten Problemen die Algorithmen F4 und F5 wirksam (dh sie enden ziemlich schnell). Es ist immer noch ein aktives Forschungsgebiet, herauszufinden, was die richtige Vermutung für die durchschnittliche oder erwartete Laufzeit sein sollte. Es wird vermutet, dass es irgendwie mit dem Volumen des Newton-Polytops des zugrunde liegenden Ideals zusammenhängt.

Jacques Carette
quelle
Durchschnitt / erwartet unter welcher Verteilung? Ich dachte, selbst das Definieren der erwarteten Laufzeit wäre für algebraische Probleme schwierig ...
Joshua Grochow
1
Ich weiß nicht, welche Fälle mit den Methoden F4 und F5 schnell gelöst werden, aber es ist ziemlich einfach, ein Polynomensystem mit vielen Variablen und niedrigem Grad zu erstellen, das eine SAT-Instanz codiert. In diesem Fall ist mir nicht bekannt, dass der Algorithmus DPLL / DPLL + übertrifft. Ich würde wirklich gerne mehr über experimentelle Ergebnisse zu diesen Dingen erfahren!
MassimoLauria
@Joshua: Zu diesem Zeitpunkt schlägt jede Distribution, die Ergebnisse zulässt ... @Massimo: Codierungsproblem X als Instanz von Y fast nie spezialisierte Algorithmen für X! Da GB und DPLL jedoch im Wesentlichen gleichwertig sind, wäre ich besonders überrascht, einen wirksamen Unterschied festzustellen.
Jacques Carette
1
@ Massimo: Ja, GB-Berechnung ist NP-schwer. Abhängig von der Formulierung. Tatsächlich sind die meisten Fragen (Vervollständigung, ideale Mitgliedschaft, algebraisch geschlossenes Feld im Vergleich zu Booleschen Werten) PSPACE-vollständig oder schlechter (EXPSPACE-vollständig). Dies bedeutet, dass GB-Berechnungen voraussichtlich viel schwieriger sind als NP-vollständige Probleme (und selbst in diesem Fall würde ein Algorithmus wie F5 DPLL höchstwahrscheinlich nicht übertreffen).
Mitch
22

Ein großes und wenig bekanntes Beispiel für dieses Phänomen ist der Graphisomorphismus . Der bekannteste Algorithmus benötigt so etwas wie Zeit, aber der Graph-Isomorphismus ist in der Praxis in der Regel recht schnell lösbar. O(2((nlogn)))

Ich weiß nicht, ob es ein formales Ergebnis gibt, das die Komplexität des Problems durchschnittlich / geglättet hat, aber ich erinnere mich, dass ich gelesen habe, dass eines existiert hat - vielleicht kann jemand anderes ein formales Ergebnis nennen. Natürlich gibt es viele experimentelle Beweise und viele schnelle Löser. Ich bin auch neugierig, ob sich diese Eigenschaft auf andere Mitglieder der GI-complete-Familie erstreckt.

Anand Kulkarni
quelle
1
Ich kenne keine geglättete Analyse für GI - oder sogar wie das genau aussehen würde -, aber es gibt eine Analyse der bekanntesten praktischen Implementierung (nauty), die zeigt, dass sie im schlimmsten Fall exponentiell abläuft. Natürlich implementiert nauty den Algorithmus . Eine Referenz finden Sie unter cstheory.stackexchange.com/questions/3128/… . O(2nlogn)
Joshua Grochow
2
Oh! Vielleicht denken Sie an Babai-Kucera, das einen linearen Durchschnittsfall-Algorithmus für GI liefert
Joshua Grochow
Ja, Babai-Kucera ist derjenige! Danke für den Hinweis.
Anand Kulkarni
20

Von David Johnson, eine Diskrepanz zwischen theoretischem und experimentellem Näherungsverhältnis: Das Problem des Handlungsreisenden: Eine Fallstudie zur lokalen Optimierung, DS Johnson und LA McGeoch . In dieser Arbeit geben sie experimentelle Beweise für Asymptotika (da die Experimente bis zur Größe N = 10.000.000 laufen!), Die den theoretischen Asymptotika trotzen: Jon Bentleys "Greedy" - oder "Multi-Fragment" -Algorithmus (Worst-Case-Approximationsverhältnis mindestens logN / loglogN) schlägt Nearest Insertion und Double MST, die beide Worst-Case-Näherungsverhältnisse von 2 haben.

Joshua Grochow
quelle
20

Ein anderes Beispiel, das bis vor kurzem nicht gut verstanden wurde, ist die Laufzeit des Lloyd's k-means-Algorithmus , der (vom praktischen Standpunkt aus) seit mehr als 50 Jahren der Clustering-Algorithmus der Wahl ist. Erst vor kurzem, im Jahr 2009, wurde (von Vattani ) bewiesen, dass der Lloyd-Algorithmus im schlimmsten Fall eine Anzahl von Iterationen erfordert, die in Bezug auf die Anzahl der Eingabepunkte exponentiell sind. Andererseits ergab eine geglättete Analyse (von Arthur, Manthey und Röglin ), dass die geglättete Anzahl der Iterationen nur polynomisch ist, was die empirische Leistung erklärt.

MRA
quelle
10

Die Traversal-, Deque- und Split-Folgerungen der dynamischen Optimalitätsvermutung für Spreizbäume sind Beispiele für solche Lücken. Experimente stützen die Behauptung der linearen Zeit, aber es gibt keinen bekannten Beweis.

Radu GRIGore
quelle
3
Seth Pettie hat bewiesen, dass n Deque-Operationen nicht mehr als O (n alpha * (n)) Zeit benötigen, wobei "alpha *" die iterierte inverse Ackermann-Funktion ist, was eine ziemlich kleine Lücke ist.
Jbapple
9

Es gibt ein kleines Problem mit der Frage. Es gibt in der Tat mehr als zwei Möglichkeiten, einen Algorithmus zu analysieren, und eine der theoretischen Möglichkeiten, die vernachlässigt wurde, ist die erwartete Laufzeit und nicht die Laufzeit im schlimmsten Fall. Es ist wirklich dieses durchschnittliche Fallverhalten, das für die Durchführung von Experimenten relevant ist. Hier ist ein sehr einfaches Beispiel: Stellen Sie sich vor, Sie haben einen Algorithmus für eine Eingabe der Größe n, der für jede mögliche Eingabe der Größe n Zeit n benötigt, mit Ausnahme einer bestimmten Eingabe jeder Länge, die Zeit 2 ^ n benötigt. Hören Sie, dass die Laufzeit im ungünstigsten Fall exponentiell ist, der Durchschnittsfall jedoch [(2 ^ n -1) n + (2 ^ n) 1] / (2 ^ n) = n - (n-1) / 2 ^ n ist Grenzen zu n. Es ist klar, dass die beiden Analysetypen sehr unterschiedliche Antworten geben. Dies ist jedoch zu erwarten, da wir unterschiedliche Mengen berechnen.

Selbst wenn wir das Experiment einige Male ausführen, wird immer noch nur ein kleiner Teil des Bereichs möglicher Eingaben abgetastet, und wenn harte Instanzen selten sind, werden wir sie wahrscheinlich verpassen .

Es ist relativ einfach, ein solches Problem zu konstruieren: Wenn die ersten n / 2 Bits alle Null sind, lösen Sie die 3SAT-Instanz, die mit den letzten n / 2 Bits codiert ist. Ansonsten ablehnen. Wenn n groß wird, hat das Problem im schlimmsten Fall ungefähr die gleiche Laufzeit wie der effizienteste Algorithmus für 3SAT, wobei die durchschnittliche Laufzeit garantiert sehr niedrig ist.

Joe Fitzsimons
quelle
Ich habe James King bereits oben geantwortet, dass ich davon ausgehe, dass die interessantesten Antworten zur erwarteten Laufzeit vorliegen werden. Ich bearbeite die Frage, um sie besser sichtbar zu machen.
Radu GRIGore
9

Die Inferenz vom Damas-Milner-Typ ist nachweislich für die Exponentialzeit vollständig, und es gibt leicht konstruierte Fälle mit exponentiellem Aufblähen in der Größe eines Ergebnisses. Nichtsdestotrotz verhält es sich bei den meisten Eingaben in der realen Welt effektiv linear.

sclv
quelle
Gibt es eine Referenz, die Sie für dieses Ergebnis empfehlen würden? Ich würde gerne mehr darüber lesen.
Radu GRIGore
1
Ich habe es selbst nicht gelesen, aber der am häufigsten zitierte Artikel ist Harry G. Mairson, "Die Entscheidbarkeit der ML-Typisierung ist für die deterministische Exponentialzeit vollständig", 17. Symposium über Prinzipien von Programmiersprachen (1990).
sclv
9

Das PTAS für Steiner-Baum in planaren Graphen hat eine lächerliche Abhängigkeit von epsilon. Es gibt jedoch eine Implementierung , die in der Praxis eine überraschend gute Leistung zeigt.

zotachidil
quelle
8

Paarung von Heaps aus [1] - Sie implementieren Heaps, bei denen Einfügen und Zusammenführen die Komplexität von O (log n) amortisiert haben, aber als O (1) angenommen werden. In der Praxis sind sie äußerst effizient, insbesondere für Benutzer von Merge.

Ich habe sie erst heute beim Lesen von Sec entdeckt. 5.5 von C. Okasakis Buch "Rein funktionale Datenstrukturen", daher dachte ich, ich sollte Informationen darüber austauschen.

[1] Fredman, ML, Sedgewick, R., Sleator, DD und Tarjan, RE 1986. Der Paarungshaufen: eine neue Form des sich selbst anpassenden Haufens. Algorithmica 1, 1 (Januar 1986), 111-129. DOI = http://dx.doi.org/10.1007/BF01840439

Blaisorblade
quelle
Seit Okasaki wurden einige Fortschritte erzielt, und es gibt jetzt (zwingende) Pairing-Heaps mit O (0) meld, O (1) insert und findMin, O (lg lg n) reductionKey und O (lg n) deleteMin: arxiv. org / abs / 0903.4130 . Dieser Haufen verwendet einen anderen Paarungsmechanismus als die ursprünglichen Paarungshaufen von Fredman et al.
Jbapple
7

Verwandt ilyaraz Bemerkung über Zweig und gebunden, Pataki et al. zeigen, dass die Reduzierung von Verzweigung und Bindung plus Gitterbasis fast alle zufälligen IPs in polytime lösen kann.

Marco
quelle
6

Die Lin-Kernighan-Heuristik für den TSP ("Eine effektive Heuristik für das Problem des Handlungsreisenden", Operations Research 21: 489–516, 1973) ist in der Praxis sehr erfolgreich, es fehlt jedoch immer noch eine Durchschnittsfall- oder geglättete Analyse, um die Leistung zu erklären . Demgegenüber gibt es eine geglättete Analyse der 2-Opt-Heuristik für den TSP von Matthias Englert, Heiko Röglin und Berthold Vöcking (Algorithmica, erscheint).

Bodo Manthey
quelle
5

In der Praxis gibt es viele sehr schnelle und effiziente Verzweigungs- und gebundene Algorithmen für verschiedene NP-schwierige Probleme, die wir nicht genau analysieren können: TSP, Steinerbaum, Behälterpackung und so weiter.

Ω(nm)

Ilyaraz
quelle
Du meinst O (mn), oder bin ich verwirrt?
Radu GRIGore
O(nmlog(n2/m))