Algorithmen aus dem Buch.

358

Paul Erdos sprach über das "Buch", in dem Gott den elegantesten Beweis für jeden mathematischen Satz aufbewahrt. Dies inspirierte sogar ein Buch (von dem ich glaube, dass es jetzt in der 4. Auflage vorliegt ): Proofs from the Book .

Wenn Gott ein ähnliches Buch für Algorithmen hätte, welche Algorithmen würden Sie für einen Kandidaten halten?

Wenn möglich, geben Sie bitte auch eine anklickbare Referenz und die wichtigsten Erkenntnisse an, die dafür sorgen, dass es funktioniert.

Bitte nur einen Algorithmus pro Antwort.

Aryabhata
quelle
11
Gute Frage! [Bearbeiten:} Eine Frage. Wo ziehen wir die Grenze zwischen Algorithmen und Datenstrukturen? Was ist, wenn die wichtigsten Erkenntnisse zu einem Algorithmus in engem Zusammenhang mit einer Datenstruktur stehen (z. B. UNION FIND in der inversen Ackermann-Funktion)?
Ross Snider
4
Eine gute Quelle und vielleicht ein Kandidat für ein solches Buch ist "Encyclopedia of Algorithms". springer.com/computer/theoretical+computer+science/book/…
Marcos Villagra
21
Ich bin ein wenig überrascht, dass Algorithmen, die ich für schwierig halte (KMP, lineare Suffix-Arrays), von anderen als "aus dem Buch" angesehen werden. "Aus dem Buch" bedeutet für mich einfach und offensichtlich, aber nur im Nachhinein. Ich bin gespannt, wie andere "elegant" interpretieren.
Radu GRIGore
49
@supercooldave Du musst nicht an Gott glauben, aber du solltest an sein Buch glauben. ;-)
Ross Snider
10
Während eines Vortrags im Jahr 1985 sagte Erdős: "Du musst nicht an Gott glauben, aber du solltest an das Buch glauben."
Robert Massaioli

Antworten:

116

Union-find ist ein schönes Problem, dessen bester Algorithmus / Datenstruktur ( Disjoint Set Forest ) auf einem Spaghetti-Stack basiert. Es war zwar sehr einfach und intuitiv genug, um es einem intelligenten Kind zu erklären, aber es dauerte mehrere Jahre, um seine Laufzeit genau zu bestimmen. Letztendlich wurde entdeckt, dass sein Verhalten mit der inversen Ackermann-Funktion zusammenhängt, einer Funktion, deren Entdeckung einen Perspektivwechsel in Bezug auf die Berechnung kennzeichnete (und tatsächlich in Hilberts On the Infinite enthalten war ).

Wikipedia bietet eine gute Einführung in Disjoint Set Forests .

Jukka Suomela
quelle
109

Knuth-Morris-Pratt- String-Matching. Die glattesten acht Codezeilen, die Sie jemals sehen werden.

Jukka Suomela
quelle
4
Es ist ein bisschen irrsinnig zu bemerken, dass dies etwas war, das zu irgendeinem Zeitpunkt nicht offensichtlich war und jetzt nur offensichtlich ist, weil sie es erfunden haben und wir es gelernt haben ... Ich denke, wir sollten Carrs Geschichtstheorie auf Mathematik und Informatik anwenden .
Ritwik Bose
1
Bei der Beschreibung würde ich sagen, dass dies mit der schnellen Teilstringsuche nach Boyer-Moore zusammenhängt.
Bart
2
@Mechko Die Tatsache, dass dieser Algorithmus gleichzeitig und unabhängig von verschiedenen Personen entdeckt wurde, ist ein Hinweis darauf, dass dies in gewissem Umfang offensichtlich ist. Ob etwas "offensichtlich" ist, hängt von den Projektbeschränkungen und der breiteren Programmierumgebung ab. Wenn Sie (1) eine schnelle Textsuche benötigen und (2) sich der Bedeutung von O (n) Algorithmen bewusst sind, und (3) Sie zuvor auf Text mit teilweisen Übereinstimmungen gestoßen sind und (4) die Zeit haben Um die Dinge "richtig" zu machen, ist dieser Algorithmus wahrscheinlich offensichtlich.
Matt Gallagher
In einem Interview sagte Knuth, dass die Idee für den Algorithmus aus der Untersuchung von Stephen Cooks Zweiwege-Automat für Palindrome stamme .
Kaveh
@Kaveh Bitte lesen Sie Abschnitt 7 (Historische Bemerkungen) aus dem Original-KMP-Papier. Es hat tolle Bemerkungen. Über Morris, der einen Texteditor schreibt, "der für andere Implementierer des Systems zu kompliziert war, um ihn zu verstehen". Über Knuth "Das erste Mal in Knuths Erfahrung, dass ihm die Automatentheorie beigebracht hatte, ein echtes Programmierproblem besser zu lösen, als er es zuvor hätte lösen können". Und "Knuth war verärgert, als er erfuhr, dass Morris den Algorithmus bereits entdeckt hatte, ohne Cooks Theorem zu kennen." SPASS.
Hendrik Jan
93

Der Algorithmus von Blum, Floyd, Pratt, Rivest und Tarjan , um das k- te Element einer unsortierten Liste in linearer Zeit zu finden, ist ein schöner Algorithmus und funktioniert nur, weil die Zahlen genau richtig sind , um in den Hauptsatz zu passen. Es geht wie folgt:

  1. Sortieren Sie jede Folge von fünf Elementen.
  2. Wählen Sie jeweils den Median aus.
  3. Wiederholen Sie diese Schritte, um den Median dieser Liste zu ermitteln.
  4. Drehpunkt auf dem Median der Mediane (wie in Quicksort)
  5. Wählen Sie die richtige Seite der Liste und die Position in dieser Liste aus und wiederholen Sie den Vorgang.
Derrick Stolee
quelle
3
1/ϵϵϵ
5
Übrigens, sobald Sie die Größe der Gruppen parametrisiert haben, sind die Konstanten nicht mehr so ​​magisch. sie sind natürlich optimiert, um im Hauptsatz das Richtige zu geben
Sasho Nikolov
Ruby-Implementierung, gist.github.com/chadbrewbaker/7202412 Gibt es eine Version des Algorithmus, die (Konstanten-, Protokoll-) Speicherplatz verwendet, oder müssen Sie linearen Scratch-Speicherplatz verwenden, um die Mediane zu halten?
Chad Brewbaker
2
5n13/40n5
88

Die binäre Suche ist der einfachste, schönste und nützlichste Algorithmus, dem ich jemals begegnet bin.

michalmocny
quelle
Ich würde elegant durch intuitiv ersetzen. Es gibt nichts Elegantes daran; Ihre Einfachheit ist ihre wahre Schönheit.
Robert Massaioli
@Robert Massaili: Ich habe elegant durch schön ersetzt. Da hast du recht gehabt.
Michalmocny
2
Und wahnsinnig schwer richtig zu schreiben - siehe " Sind Sie einer der 10% der Programmierer, die eine binäre Suche schreiben können? "
jon
In meinem ersten Kurs über Algorithmen hatten wir 15-minütige Tests, bei denen wir 2-3 Probleme von Hand lösen mussten. Das erste Quiz enthielt einen binären Suchbaum und zwei Fragen zu Haufen. Ich war verlegen und bestürzt zu erfahren, dass ich das Problem der binären Suche falsch verstanden hatte, bevor mir gesagt wurde, dass in einer Klasse von ungefähr 30 Personen zwei richtige Antworten vorlagen. Aber selbst wenn man das weiß, ist die Tatsache, dass die professionelle Community 15 Jahre gebraucht hat, um richtig zu werden, umwerfend.
Stella Biderman
84

Ich bin überrascht, den Floyd-Warshall-Algorithmus für die kürzesten Wege aller Paare hier nicht zu sehen :

d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

O(n3)O(n2)

user651
quelle
2
Dieser Algorithmus kann auch sehr gut verallgemeinert werden. Siehe z. B. r6.ca/blog/20110808T035622Z.html und cl.cam.ac.uk/~sd601/papers/semirings.pdf
Mikhail Glushenkov 25.11.13
73

Es mag etwas trivial erscheinen (besonders im Vergleich zu den anderen Antworten), aber ich finde, dass Quicksort wirklich elegant ist. Ich erinnere mich, als ich es das erste Mal sah, dachte ich, es sei wirklich kompliziert, aber jetzt scheint es mir alles zu einfach.

Jukka Suomela
quelle
10
Quicksort wirft auch interessante Fragen darüber auf, was genau das Wesen eines Algorithmus ist. Beispielsweise sieht die standardmäßige elegante Haskell-Implementierung genauso aus wie die standardmäßige Pseudocodedefinition, weist jedoch eine andere asymptotische Komplexität auf. Geht es in Quicksort also nur darum, sich zu teilen und zu erobern, oder ist das clevere In-Situ-Zeigerfummeln ein wesentlicher Bestandteil von Quicksort? Kann Quicksort überhaupt in einer rein funktionalen Umgebung implementiert werden oder erfordert es eine Wandlungsfähigkeit?
Jörg W Mittag
2
Die Idee des "Wesens" oder der "Moral" eines Algorithmus stammt natürlich aus dem schönen Artikel The Genuine Sieve of Eratosthenes von Melissa E. O'Neill ( cs.hmc.edu/~oneill/papers/Sieve-JFP. pdf ) und die QuickSort-Diskussion stammen aus der LtU-Diskussion dieses Papiers ( lambda-the-ultimate.org/node/3127 ) und beginnen mit diesem Kommentar: lambda-the-ultimate.org/node/3127/#comment-45549
Jörg W Mittag
8
@ Jörg: Das Implementieren von Quicksort auf verknüpften Listen ist absolut sinnvoll und hat die gleiche asymptotische Laufzeit wie die direkte Implementierung auf Arrays (zum Teufel, selbst die naive externe Implementierung auf Arrays hat die gleiche Laufzeit) - beide auf durchschnittlich und im schlimmsten Fall. In Bezug auf die Speicherplatznutzung ist dies in der Tat anders, aber es muss gesagt werden, dass selbst die "In-Place" -Version nicht konstanten zusätzlichen Speicherplatz benötigt (Aufrufstapel!), Eine Tatsache, die leicht übersehen wird.
Konrad Rudolph
Erwähnenswert ist auch Vladimir Yaroslavskis Dual-Pivot-Quicksort. Das sollte mindestens 20% schneller sein. Original quicksort permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/…
SaveTheRbtz
Theoretisch ist Quicksort einfach (kann in 4 Schritten beschrieben werden) und könnte in hohem Maße optimiert werden, aber in der Praxis ist es sehr schwierig, richtig zu programmieren. Welches ist, warum es nicht meine Stimme bekommt.
Dennis
50

Der Miller-Rabin-Primalitätstest (und ähnliche Tests) sollte im Buch stehen. Die Idee ist, die Eigenschaften von Primzahlen zu nutzen (dh Fermats kleines Theorem zu verwenden), um probabilistisch nach einem Zeugen dafür zu suchen, dass die Zahl keine Primzahl ist. Wird nach genügend zufälligen Tests kein Zeuge gefunden, wird die Zahl als Primzahl klassifiziert.

In diesem Sinne sollte der AKS-Primalitätstest , bei dem PRIMES in P vorkommt, auf jeden Fall im Buch stehen!

Jukka Suomela
quelle
49

Polynomidentitätstest mit dem Schwartz-Zippel-Lemma :

Wenn jemand Sie mitten in der Nacht aufweckte und Sie aufforderte, zwei univariate Polynomausdrücke auf Identität zu testen, würden Sie sie wahrscheinlich auf die normale Produktsummenform reduzieren und auf strukturelle Identität vergleichen. Leider kann die Reduzierung exponentielle Zeit in Anspruch nehmen. es ist analog zu booleschen Ausdrücken auf disjunktive Normalform zu reduzieren.

Angenommen, Sie sind der Typ, der randomisierte Algorithmen mag, besteht Ihr nächster Versuch wahrscheinlich darin, die Polynome an zufällig ausgewählten Punkten auf der Suche nach Gegenbeispielen auszuwerten und die Polynome für sehr wahrscheinlich identisch zu erklären, wenn sie genügend Tests bestehen. Das Schwartz-Zippel-Lemma zeigt, dass mit zunehmender Punktzahl die Wahrscheinlichkeit eines falschen Positivs sehr schnell abnimmt.

Es ist kein deterministischer Algorithmus für das Problem bekannt, der in Polynomialzeit abläuft.

Per Vognsen
quelle
Dies hätte schon vor langer Zeit vorgeschlagen werden sollen! Vielen Dank!
Arnab
1
Es gibt mehrere andere randomisierte Algorithmen, die einen herausragenden Platz im Buch verdienen. Für diese ist der Kontrast zwischen deterministischen und probabilistischen Alternativen weniger auffällig: Ein deterministischer Algorithmus existiert normalerweise, ist aber viel komplizierter.
Per Vognsen
Ich habe den gleichen Algorithmus unabhängig voneinander erfunden, als ich vor ein paar Jahren an einer Arbeit gearbeitet habe, bis mich jemand gefragt hat, ob es nicht Schwartz-Zippel-Lemma ist. Und ich sagte, was ist das? :)
Helium
46

Tiefe erste Suche . Es ist die Basis vieler anderer Algorithmen. Es ist auch täuschend einfach: Wenn Sie beispielsweise die Warteschlange in einer BFS-Implementierung durch einen Stapel ersetzen, erhalten Sie DFS?

Radu GRIGore
quelle
1
Es ist auch die Basis der Prolog-Ausführung!
Muad
1
Was ist der Sinn von BFS mit einem Stack, den ich vermisse? Ich hätte gedacht, dass die Antwort "Ja, Sie bekommen DFS" ist.
Omar Antolín-Camarena
1
Nun, jeder scheint zu denken, dass dieses Problem trivial ist. Außerdem scheint jeder der Meinung zu sein, dass die Antwort "Ja" ist, was falsch ist. Die Antwort lautet "hängt davon ab, mit welcher BFS-Implementierung Sie beginnen". Siehe cs.stackexchange.com/questions/329/… (Dies ist eine Frage, die ich gepostet habe, um bei der Beta-Phase von CS.SE zu helfen)
Radu GRIGore
Es wird hier auch kurz besprochen: ics.uci.edu//~eppstein/161/960215.html
Radu GRIGore
42

Dijkstra-Algorithmus : das Single-Source-Problem mit dem kürzesten Pfad für einen Graphen mit nichtnegativen Kantenpfadkosten. Es wird überall verwendet und ist einer der schönsten Algorithmen auf dem Markt. Das Internet könnte ohne es nicht geroutet werden - es ist ein Kernbestandteil der Routing-Protokolle IS-IS und OSPF (Open Shortest Path First).

  1. Weisen Sie jedem Knoten einen Abstandswert zu. Setzen Sie es für unseren Anfangsknoten auf Null und für alle anderen Knoten auf Unendlich.
  2. Markieren Sie alle Knoten als nicht besucht. Setzt den Anfangsknoten als aktuell.
  3. Berücksichtigen Sie für den aktuellen Knoten alle nicht besuchten Nachbarn und berechnen Sie deren vorläufigen Abstand (vom ursprünglichen Knoten). Wenn beispielsweise der aktuelle Knoten (A) einen Abstand von 6 hat und eine Kante, die ihn mit einem anderen Knoten (B) verbindet, 2 ist, beträgt der Abstand von B bis A 6 + 2 = 8. Wenn dieser Abstand geringer ist als der zuvor aufgezeichnete Abstand (Unendlich am Anfang, Null für den Anfangsknoten), überschreiben Sie den Abstand.
  4. Wenn wir alle Nachbarn des aktuellen Knotens berücksichtigt haben, markieren Sie ihn als besucht. Ein besuchter Knoten wird nie wieder überprüft. Die jetzt aufgezeichnete Distanz ist endgültig und minimal.
  5. Wenn alle Knoten besucht wurden, beenden Sie den Vorgang. Andernfalls legen Sie den nicht besuchten Knoten mit der geringsten Entfernung (vom Anfangsknoten) als nächsten "aktuellen Knoten" fest und fahren Sie mit Schritt 3 fort.
David Sifry
quelle
40

Gentrys vollständig homomorphes Verschlüsselungsschema (entweder über idealen Gittern oder über ganzen Zahlen) ist schrecklich schön. Damit kann ein Dritter beliebige Berechnungen für verschlüsselte Daten durchführen, ohne auf einen privaten Schlüssel zugreifen zu müssen.

Das Verschlüsselungsschema beruht auf mehreren genauen Beobachtungen.

  • Um ein vollständig homomorphes Verschlüsselungsschema zu erhalten, muss man nur ein Schema haben, das über Addition und Multiplikation homomorph ist. Dies liegt daran, dass Addition und Multiplikation (Mod 2) ausreichen, um UND-, ODER- und NICHT-Gatter zu erhalten (und damit die Vollständigkeit zu bestimmen).
  • Wenn ein solches Schema vorhanden wäre, aber aufgrund einiger Einschränkungen nur für Schaltkreise mit einer begrenzten Tiefe ausgeführt werden könnte, dann kann man das Entschlüsselungs- und Wiederaufnahmeverfahren homomorph auswerten, um die Begrenzung der Schaltkreistiefe zurückzusetzen, ohne die Privatsphäre des Schlüssels zu beeinträchtigen.
  • Dass durch "Quetschen" der Tiefe der Schaltungsversion der Entschlüsselungsfunktion für das Schema ein Schema ermöglicht werden könnte, das ursprünglich auf endliche, flache Schaltungen mit einer willkürlichen Anzahl von Berechnungen beschränkt war.

Craig Gentry hat in seiner Dissertation ein langjähriges (und großartiges) offenes Problem in der Kryptographie gelöst. Die Tatsache, dass ein vollständig homomorphes Schema existiert, erfordert, dass wir erkennen, dass die Berechenbarkeit eine gewisse Struktur aufweist, die wir sonst möglicherweise ignoriert haben.

http://crypto.stanford.edu/craig/craig-thesis.pdf

http://eprint.iacr.org/2009/616.pdf

http://portal.acm.org/citation.cfm?id=1666420.1666445

Ross Snider
quelle
38

Strassens Algorithmus zur Matrixmultiplikation.

Kaveh
quelle
Würde wahrscheinlich warten, bis wir wissen, ob es optimal ist.
Thomas Ahle
Zumindest asymptotisch ist es nicht optimal ... Ich denke, dass das Einbeziehen des Strassen-Algorithmus Sie dazu zwingt, zuerst den Karatsuba-Algorithmus einzubeziehen.
Timothy Sun
35

Der stabile Heiratsalgorithmus von Gale-Shapley . Dieser Algorithmus ist gierig und sehr einfach, es ist zunächst nicht klar, warum er funktionieren würde, aber dann ist der Beweis der Korrektheit wieder leicht zu verstehen.

Konrad Swanepoel
quelle
+1, weil es auch ein Kapitel in den veröffentlichten Beweisen aus dem Buch über Ehen gibt ...
ixtmixilix
34

Der lineare Zeitalgorithmus zum Erstellen von Suffix-Arrays ist wirklich wunderschön, obwohl er nicht die verdiente Anerkennung erhielt. Http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf

zotachidil
quelle
Ich kann denken , dass es hat die Anerkennung , die sie verdient - was Sie anders denken macht? Beispielsweise ist es in der C ++ - Sequenzanalysebibliothek SeqAn implementiert.
Konrad Rudolph
Es ist erwähnenswert, dass es jetzt eine Reihe anderer linearer und nichtlinearer Algorithmen zum Aufbau von Zeitsuffix-Arrays gibt, die zwar nicht annähernd so hübsch sind, in der Praxis jedoch erheblich schneller sein können. "Ein effizienter und vielseitiger Ansatz zur Sortierung von Suffixen", Journal of Experimental Algorithmics (JEA), Band 12, Juni 2008, enthält einige experimentelle Ergebnisse in diesem Sinne.
Raphael
@Raphael: Ich bin ein bisschen vorsichtig, dass auf p. 3 von diesem JEA-Papier geben sie nur an, was sie "glauben", ist eine "lose" Grenze von O (n ^ 2 log n) ... Kennen Sie Papiere mit nachweislich linearen Zeitalgorithmen, die in der Praxis schneller sind als die Skew-Algorithmus?
user651
32

Gaußsche Eliminierung. Es vervollständigt die Generalisierungssequenz vom euklidischen GCD-Algorithmus zu Knuth-Bendix.

Mitch
quelle
Übrigens, wie lautet die Verallgemeinerungssequenz und wo passt der Buchberger-Algorithmus für die Grobner-Basis hinein? (Es scheint analog zu Knuth-Bendix zu sein, aber ich habe irgendwo eine Erwähnung gesehen, dass es die Gaußsche Eliminierung irgendwie verallgemeinert ...)
ShreevatsaR
6
Die Sequenz lautet: Euklidische GCD -> Gaußsche Elimination -> Buchberger -> Knuth-Bendix. Man kann auch (anstelle der Gaußschen Elimination) eine univariate Polynomdivision und ein Modulo eingeben (in der Verallgemeinerungsreihenfolge ist es 'abgesehen' von der Gaußschen Elimination, GE ist ein multivariater Grad 1, Polynomring ist ein univariater unbegrenzter Grad, Buchbergers ist ein multivariater unbegrenzter Grad Der Verallgemeinerungssprung ist am größten von EGCD ​​nach GE oder Polynomring, weil Variablen
Mitch
+1: Der euklidische Algorithmus löst die berühmteste Gleichung ax-by = 1 in Mathe. Warum es in CS nicht öfter auftaucht, ist ein Rätsel.
Tegiri Nenashi
32

Ich war beeindruckt, als ich zum ersten Mal den Algorithmus für die Probenahme von Behältern und seinen Beweis sah. Es ist das typische "Brain Teaser" -Puzzle mit einer extrem einfachen Lösung. Ich denke, es gehört definitiv zum Buch, sowohl für Algorithmen als auch für mathematische Theoreme.

In Bezug auf das Buch heißt es, dass Erdös, als er starb und in den Himmel kam, darum bat, sich mit Gott zu treffen. Dem Antrag wurde stattgegeben und für das Treffen hatte Erdös nur eine Frage. "Darf ich in das Buch schauen?" Gott hat ja gesagt und Erdös dorthin geführt. Natürlich sehr aufgeregt, öffnet Erdös das Buch nur um folgendes zu sehen.

Satz 1: ...
Beweis: Offensichtlich.

Satz 2: ...
Beweis: Offensichtlich.

Satz 3: ...
Beweis: Offensichtlich.

Arnar
quelle
4
Satz 4:… Beweis: Übung für den Leser.
jon
31

Der Schildkröten- und Hasen-Algorithmus . Ich mag es, weil ich mir sicher bin, dass ich auf keinen Fall auf eine solche Idee kommen würde, selbst wenn ich mein ganzes Leben damit verschwendet hätte, sie zu finden.

Tobias Neukom
quelle
6
Kennen Sie den dummen Algorithmus, der das Problem mit der gleichen Asymptotik löst und einem algorithmischen Entwurfsmuster folgt? Ich spreche von iterativer Vertiefung. In der n-ten Iteration beginnen Sie mit dem 2 ^ n-ten Nachfolger der Wurzel und suchen 2 ^ n Nachfolger nach einer Wiederholung. Auch wenn Sie einige Ihrer Schritte bei jeder Iteration zurückverfolgen, hat die geometrische Wachstumsrate des Suchradius keinen Einfluss auf die Asymptotik.
Per Vognsen
30

Ein so grundlegendes und "triviales" Beispiel wie Euklids Beweis für unendlich viele Primzahlen:

2-Approximation für MAX-CUT - Ordnen Sie sie für jeden Scheitelpunkt unabhängig mit gleicher Wahrscheinlichkeit einer der beiden Partitionen zu.

Arnab
quelle
6
Ja, ein sehr schöner Algorithmus. Weniger trivial funktioniert dieser Algorithmus auf Kosten eines weiteren Faktors von 2 auch zur Maximierung einer beliebigen submodularen Funktion, nicht nur der Graphschnittfunktion. Dies ist ein Ergebnis von Feige, Mirrokni und Vondrak von FOCS 07
Aaron Roth
30

Ich war schon immer an Christofides 'Algorithmus interessiert , der eine (3/2) -Anäherung für metrische TSP liefert. Rufen Sie mich einfach bitte an, aber ich mochte sogar den 2-Approximations-Algorithmus, der davor war . Christofides 'Trick, durch Hinzufügen eines Matchings seiner Eckpunkte ungeraden Grades einen Euler-Baum mit minimalem Gewicht zu erstellen (anstatt alle Kanten zu duplizieren), ist einfach und elegant einer optimalen Tour.

James King
quelle
In der Tat gibt es auch viele andere einfache und elegante Approximationsalgorithmen mit angemessenen Approximationsgarantien.
Janne H. Korhonen
27

O(N)

Joe Fitzsimons
quelle
25

Algorithmen für die lineare Programmierung : Simplex-, Ellipsoid- und Innenpunktmethoden.

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Kaveh
quelle
In der Tat wurden mehrere Nobelpreise vergeben, um unser Verständnis dieser Probleme zu fördern.
Ross Snider
@Ross Kantorovich erhielt den Nobelpreis für Ökonomie für die Erfindung der LP und deren Anwendung auf die Ressourcenzuweisung. An welche anderen Preise haben Sie gedacht?
Mark Reitblatt
@ Mark Koopermans wurde mit Kantorovich der Nobelpreis verliehen, aber es war immer noch falsch von mir, "mehrere" zu sagen.
Ross Snider
22

Robin Moser-Algorithmus zum Lösen einer bestimmten Klasse von SAT-Instanzen. Solche Fälle können von Lovasz Local Lemma gelöst werden. Moser-Algorithmus ist in der Tat eine De-Randomisierung der Aussage des Lemmas.

Ich denke, in einigen Jahren wird sein Algorithmus (und die Technik für seinen Korrektheitsnachweis) gut verdaut und verfeinert sein, bis er ein brauchbarer Kandidat für einen Algorithmus aus dem Buch ist .

Diese Version ist eine Erweiterung seines Originalpapiers, das mit Gábor Tardos geschrieben wurde.

MassimoLauria
quelle
21

Marcus Hutters schnellster und kürzester Algorithmus für alle genau definierten Probleme .

Dies widerspricht dem Geist der anderen Angebote in dieser Liste, da es nur von theoretischem und nicht von praktischem Interesse ist, aber der Titel sagt schon alles. Vielleicht sollte es als Vorsichtsmaßnahme für diejenigen aufgenommen werden, die sich nur mit dem asymptotischen Verhalten eines Algorithmus befassen.

Kurt
quelle
21

Knuths Algorithmus X findet alle Lösungen für das genaue Deckungsproblem . Was daran so magisch ist, ist die von ihm vorgeschlagene Technik, um sie effizient umzusetzen: Dancing Links .

Diego de Estrada
quelle
20

Ich denke, wir müssen Schieber-Vishkins einbeziehen , der die niedrigsten gemeinsamen Vorfahrenabfragen in konstanter Zeit beantwortet und den Wald in linearer Zeit vorverarbeitet.

Ich mag Knuths Darstellung in Band 4, Fascicle 1, und sein Nachdenken . Er sagte, er habe zwei Tage gebraucht, um es vollständig zu verstehen, und ich erinnere mich an seine Worte:

Ich finde es ziemlich schön, aber erstaunlicherweise hat es eine schlechte Presse in der Literatur (..) Es basiert auf Mathematik, die mich begeistert.

Diego de Estrada
quelle
10
Warten Sie, es mag schön sein, aber wenn Knuth zwei Tage gebraucht hat, um es vollständig zu verstehen, ist es dann wirklich "aus dem Buch"?
ShreevatsaR
@ ShreevatsaR Das Buch hat Kleingedrucktes in den Fußnoten :)
hsmyers