Leistungsstarke Algorithmen, deren Implementierung zu komplex ist

Was sind Algorithmen von legitimem Nutzen, die einfach zu komplex sind, um sie zu implementieren?

Lassen Sie mich klar sein: Ich suche nicht nach Algorithmen wie dem aktuellen asymptotischen optimalen Matrixmultiplikationsalgorithmus (Coppersmith-Winograd), der sinnvoll zu implementieren ist, aber eine Konstante hat, die es in der Praxis unbrauchbar macht. Ich bin auf der Suche nach Algorithmen, die plausibel einen praktischen Wert haben könnten, die aber so schwer zu codieren sind, dass sie nie implementiert wurden, nur in extrem künstlichen Umgebungen oder nur für bemerkenswert spezielle Anwendungen implementiert wurden.

Ebenfalls willkommen sind nahezu unmöglich zu implementierende Algorithmen, die eine gute Asymptotik aufweisen, aber wahrscheinlich eine schlechte reale Leistung aufweisen.

Chazelle gab einen linearen Zeitalgorithmus zur Triangulation eines einfachen Polygons an . Skiena schrieb (S.575, Algorithm Design Manual), dass es "genug hoffnungslos ist, um zu implementieren, dass es mehr als Existenzbeweis qualifiziert".

Der Risch-Algorithmus zur Berechnung elementarer Antiderivate. Laut Wikipedia ist aufgrund seiner Komplexität kein Softwarepaket bekannt, das den vollständigen Algorithmus implementiert.

Jeder Algorithmus, der die Robertson-Seymour-Ergebnisse verwendet, um einen "Polytime" -Algorithmus für Dinge abzuleiten, die Graphen beinhalten, die einen festen Nebeneffekt ausschließen, ist problematisch. Die in ihrem Ergebnis verborgene Konstante ist "galaktisch".

$O(n)$$O(\frac{\log^2 n}{B})$$B$

Das Papier ist 55 Seiten lang und enthält einige Verbesserungen der Konstanten, die der Autor aus Platzgründen nicht beschreibt. Dies lässt mich vermuten, dass die Konstanten möglicherweise nicht so galaktisch sind und dass diese Datenstruktur von "legitimem Nutzen" wäre, zumal sie oft zitiert wurde.

Der Linear Time Pattern Unification Algorithmus höherer Ordnung von Qian wurde aufgrund seiner Komplexität AFAIK nie implementiert.

Linearzeitalgorithmus zur Überprüfung, ob ein Diagramm in eine feste Oberfläche eingebettet werden kann.

Ken-ichi Kawarabayashi, Bruce A. Reed, Bojan Mohar: Ein einfacherer linearer Zeitalgorithmus zum Einbetten von Graphen in eine beliebige Oberfläche und die Gattung der Graphen mit begrenzter Baumbreite. FOCS 2008: 771 & ndash; 780.

Bojan Mohar: Ein linearer Zeitalgorithmus zum Einbetten von Graphen in eine beliebige Oberfläche. SIAM J. Discrete Math. 12 (1): 6-26 (1999)

Ich bin mir nicht sicher, wie nützlich es in der Praxis sein könnte (obwohl ich über Proteinfaltung und -vergleich sowie über die Vorhersage der RNA-Sekundärstruktur nachdenke), aber Wolfgang Haken gab den ersten Algorithmus zur Bestimmung der Polynomzeit an, um zu entscheiden, ob ein Knoten ein Knoten ist einfache Schleife ( Theorie der Normalflächen. Acta Math. 105, 1961, S. 245–375). Soweit ich mich erinnere, ist es immer noch zu kompliziert, um in all den Jahrzehnten später implementiert zu werden.

Wenn man an Wikipedia glauben will, wurden später mehrere andere Algorithmen angegeben, und "Die Komplexität dieser Algorithmen zu verstehen, ist ein aktives Forschungsgebiet."

Baumzerfall und vielleicht Fibonacci-Haufen .

Die perfekte Hash-Konstruktion ( https://en.wikipedia.org/wiki/Perfect_hash_function#Construction ) würde für jeden Anwendungsfall mit statischen oder sich selten ändernden Schlüsseln gelten (z. B. Domänennamen der obersten Ebene auf Routern, Stichwörter in Compilern oder Funktionsnamen) in Standardbibliotheken), aber als ich das letzte Mal nachgeschaut habe, konnte ich keine Implementierungen finden.

Die parametrische Suche kann viele schwierige Optimierungsprobleme lösen, einschließlich einiger Probleme, die in polynomialer Zeit NP-hart sein sollten. Die bekannte Veröffentlichung Parametric Search, die in der Praxis umgesetzt wurde, implementiert eine Variante der parametrischen Suche, aber ich glaube immer noch nicht, dass sie in der Praxis implementiert wurde.

$k$$n$$O(n \log n + k)$$O((n+k) \log n)$