Algoritmos potentes demasiado complejos para implementar

67

¿Cuáles son algunos algoritmos de utilidad legítima que son simplemente demasiado complejos para implementar?

Permítanme ser claro: no estoy buscando algoritmos como el algoritmo de multiplicación de matriz óptima asintótica actual (Coppersmith-Winograd), que es razonable de implementar pero tiene una constante que lo hace inútil en la práctica. Estoy buscando algoritmos que posiblemente tengan un valor práctico, pero que sean tan difíciles de codificar que nunca se hayan implementado, solo se hayan implementado en entornos extremadamente artificiales o solo para aplicaciones extraordinariamente especiales.

También son bienvenidos los algoritmos casi imposibles de implementar que tienen buenos asintóticos pero que probablemente tengan un rendimiento real deficiente.

ds.algorithms ds.data-structures big-list implementation Elliot Jans
fuente
1
haciendo este CW, ya que podría ser una larga lista.
Suresh Venkat
44
¿Existe una métrica para "casi imposible de implementar"? ¿Existe alguna teoría que lo defina?
Ritwik Bose
@Mechko, quizás un límite inferior en el tamaño de la máquina de Turing más pequeña que genera una descripción de una máquina de Turing que es una implementación del algoritmo. :)
Radu GRIGore
@Radu GRIGore ¿Es esta una métrica aceptada o una que debería desarrollarse? Supongo que (por ahora) hay una línea simple e inamovible que define 'meh, no vale la pena' ...: D
Ritwik Bose
44
Me interesa la sugerencia de que Coppersmith-Winograd es razonable de implementar. ¿Alguien ha visto alguna vez una implementación escrita incluso en pseudocódigo de alto nivel y alguien ha estimado las constantes?
Raphael

Respuestas:

33

Chazelle dio un algoritmo de tiempo lineal para triangular un polígono simple . Skiena escribió (p. 575, Algorithm Design Manual) que es "lo suficientemente desesperado para implementar que califica más como una prueba de existencia"

Yaroslav Bulatov
fuente
3
¿El algoritmo tiene constantes razonables?
jbapple
¿Es este el único algoritmo de tiempo lineal conocido para el problema?
Thomas Ahle
2
@ThomasAhle Creo que es el único algoritmo de tiempo lineal determinista conocido. Amato, Goodrich y Ramos tienen uno aleatorio más simple: cs.princeton.edu/courses/archive/fall05/cos528/handouts/…
Sasho Nikolov
El algoritmo de triangulación de polígono simple de tiempo lineal de Chazelle, que yo sepa, nunca se ha implementado y probablemente nunca lo será debido a su complejidad y también porque las constantes son altas, por lo que no podrá competir con alternativas en la práctica. Logro teórico importante sin embargo. Ralph Boland
Ralph Boland
Preguntaré nuevamente: ¿el algoritmo tiene constantes razonables?
user1271772
29

El algoritmo de Risch para calcular antiderivadas elementales. Según Wikipedia, no se conoce ningún paquete de software para implementar el algoritmo completo debido a su complejidad.

Mark Reitblatt
fuente
3
Wikipedia también señala que esto no es un algoritmo sino un semi-algoritmo porque requiere heurística para resolver el problema constante.
sclv
¿Qué es la heurística? ¿Puedes dar algún enlace para leer más al respecto?
zygimantus
22

Cualquier algoritmo que use los resultados de Robertson-Seymour para inferir un algoritmo "polytime" para cosas que involucran gráficos que excluyen a un menor fijo está pidiendo problemas. La constante oculta en su resultado es "galáctica".

Suresh Venkat
fuente
3
¿Esto también es difícil de implementar o simplemente tiene una gran constante?
Lev Reyzin
55
Sí, esto no parece un buen ejemplo. Si entiendo correctamente, la pregunta es sobre algoritmos que podrían ser prácticos (por lo tanto, constantes 'pequeñas') pero que son demasiado complejos para implementar. Por supuesto, toda la pregunta está abierta a diferentes interpretaciones :-)
Aryabhata
55
El problema es que la constante proviene de la gran lista de menores que hay que excluir para una propiedad en particular. No conozco ninguna forma de generar la lista deseada de menores excluidos para una propiedad determinada, por lo que no es solo un problema de escala.
Suresh Venkat
2
Por ejemplo, ni siquiera conocemos la lista de menores excluidos para gráficos incrustados en el toro.
Derrick Stolee
17
El problema aquí parece más profundo: no se conoce una forma efectiva de generar la lista de menores, por lo que en realidad esto no produce un algoritmo en absoluto. La mayoría de las propiedades cerradas menores producen una lista infinita de menores excluidos, si uno traduce la expresión lógica directamente. El teorema de Robertson-Seymour (conjetura de Wagner) nos dice que una lista finita de menores excluidos está al acecho dentro de esa lista infinita, pero el teorema no proporciona absolutamente ninguna ayuda para encontrarlos. Por lo tanto, Robertson-Seymour por lo general conduce a una prueba de existencia pura.
András Salamon
16

El "Algoritmo de control de densidad de Dan Willard para realizar inserciones y eliminaciones en un archivo ordenado secuencialmente en el peor de los casos" describe un algoritmo para mantener un conjunto ordenado en una matriz de tamaño con inserción y eliminación en peor de los casos, donde es el tamaño de la página.O ( log 2 nO(n)BO(log2⁡nB)B

El documento tiene 55 páginas y su conclusión señala varias mejoras en las constantes que el autor no describe por razones de espacio. Esto me hace sospechar que quizás las constantes no son tan galácticas, y que esta estructura de datos sería de "utilidad legítima", especialmente porque se ha citado muchas veces.

revs jbapple
fuente
12

El algoritmo de unificación de patrones de orden superior de tiempo lineal de Qian nunca se ha implementado debido a su complejidad AFAIK.

Dominic Mulligan
fuente
Afortunadamente, todavía hay algoritmos prácticos para ello. El manual de razonamiento automatizado dice que se puede hacer en polytime (justo al lado de donde se cita el algoritmo de Qian), por lo que es bastante impresionante.
Jake
11

Algoritmo de tiempo lineal para verificar si un gráfico se puede incrustar en una superficie fija.

Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed: un algoritmo de tiempo lineal más simple para incrustar gráficos en una superficie arbitraria y el género de gráficos de ancho de árbol acotado. FOCS 2008: 771-780.

Bojan Mohar: Un algoritmo de tiempo lineal para incrustar gráficos en una superficie arbitraria. SIAM J. Matemáticas discretas. 12 (1): 6-26 (1999)

alguien
fuente
1
Es poco probable que tenga un valor práctico incluso si se implementa, debido a la gran dependencia exponencial (sic) del género.
Jeffε
8

No estoy seguro de lo útil que podría ser en la práctica (aunque estoy pensando en el plegamiento y la comparación de proteínas, así como en la predicción de la estructura secundaria de ARN), pero Wolfgang Haken dio el primer algoritmo de tiempo polinómico para decidir si un nudo es un bucle simple ( Theorie der Normalflächen. Acta Math. 105, 1961, pp. 245-375). Según recuerdo, todavía es demasiado complicado para implementarse todas esas décadas más tarde.

Si se debe creer en Wikipedia, más tarde se proporcionaron varios otros algoritmos, y "Comprender la complejidad de estos algoritmos es un campo de estudio activo".

Anthony Labarre
fuente
44
Haken dio el primer algoritmo, pero no se ejecuta en tiempo polinómico; de hecho, no se conoce ningún algoritmo de poli-tiempo (o resultado de dureza NP). El trabajo más reciente ha reducido la trivialidad del nudo (a través de la formulación de superficie normal de Haken) a la programación de enteros, que generalmente es rápida de resolver en la práctica.
Jeff el
3

Descomposición de los árboles , y quizás montones de Fibonacci .

Peter Boothe
fuente
14
Los montones de Fibonacci ciertamente no son demasiado complicados de implementar; han sido implementados y probados. El problema con ellos es más bien que su rendimiento práctico no es tan bueno como algunos otros montones debido a factores constantes de gran tamaño en su tiempo de ejecución.
David Eppstein
1
Escribí un paquete para encontrar la descomposición del árbol, y no creo que sea difícil implementar yaroslavvb.blogspot.com/2011/01/building-junction-trees.html
Yaroslav Bulatov el
2
Mi código es solo una descomposición heurística de árbol, no es óptimo como los enfoques de programación dinámica y ramificada ... ¿Supongo que te refieres al "Algoritmo de tiempo lineal ..." de Bodlaender? No he visto ninguna implementación de eso
Yaroslav Bulatov
44
El algoritmo de tiempo lineal de Bodlaender utiliza un algoritmo de programación dinámica de un artículo anterior como una subrutina: ese algoritmo calcula una descomposición óptima del árbol en algo como tiempo, cuando se le da una descomposición aproximada del árbol de ancho k como entrada. Creo recordar que Hans Bodlaender me dijo una vez que implementaron este algoritmo de programación dinámica que se usa como subrutina, pero que ya era demasiado lento para k = 3. La programación dinámica es la parte principal del algoritmo de tiempo lineal, por lo que el algoritmo de Bodlaender no es demasiado difícil de implementar, sino demasiado lento. 2O(k3)O(n)
Bart Jansen
3
Creo que este es el mejor esfuerzo de implementación: hein.roehrig.name/dipl
Diego de Estrada
1

La construcción hash perfecta ( https://en.wikipedia.org/wiki/Perfect_hash_function#Construction ) se aplicaría a cualquier caso de uso con claves estáticas o que cambian con poca frecuencia (por ejemplo, nombres de dominio de nivel superior en enrutadores, palabras clave en compiladores o nombres de funciones en bibliotecas estándar) pero la última vez que busqué no pude encontrar ninguna implementación.

La búsqueda paramétrica puede resolver muchos problemas difíciles de optimización, incluidos algunos que podrían parecer NP-hard, en tiempo polinómico. La bien conocida búsqueda paramétrica en papel hecha práctica implementa una variante de búsqueda paramétrica, pero aún no creo que se haya implementado en un software práctico.

El algoritmo óptimo para la intersección del segmento de línea por Chazelle y Edelsbrunner encuentra todas las intersecciones de segmentos de línea en el tiempo , pero es complejo. CGAL es una sofisticada biblioteca de algoritmos de geometría, pero implementa un algoritmo más simple que es .n O ( n log n + k ) O ( ( n + k ) log n )knO(nlog⁡n+k)O((n+k)log⁡n)

Kevin A. Wortman
fuente
1
Me niego a creer que la construcción de FKS sea demasiado compleja de implementar. En realidad es bastante sencillo. Quizás no sea práctico, pero ciertamente no es demasiado complejo de implementar.
Sasho Nikolov