¿Existe algún otro algoritmo cuyo peor tiempo de ejecución sea exponencial mientras que funcione muy bien en la práctica que no sea el algoritmo Simplex?

9

Generalmente llamamos a un algoritmo "buen algoritmo" si su tiempo de ejecución es polinómico en el peor de los casos. Pero en algunos casos (por ejemplo, el algoritmo Simplex), aunque el peor de los casos del algoritmo es exponencial, podría funcionar muy bien en la práctica.

¿Hay algún ejemplo (determinista) de esta situación que no sea el algoritmo Simplex?

ds.algorithms Arman
fuente
1
Puede interesarle una pregunta relacionada: cstheory.stackexchange.com/questions/305/…
Radu GRIGore

Respuestas:

13

Los algoritmos modernos de resolución de SAT pueden resolver la mayoría de las instancias bastante rápido, aunque el peor tiempo de ejecución es, por supuesto, exponencial. En este caso, sin embargo, la velocidad práctica es más el resultado de años de ingeniería de algoritmos, más que la de un algoritmo elegante único. Si bien he entendido que el aprendizaje de cláusulas controladas por conflictos causó un salto importante en el rendimiento de los solucionadores de SAT, las mejoras posteriores se han logrado a menudo mediante el uso inteligente de varias heurísticas en los algoritmos.

Janne H. Korhonen
fuente
13

El algoritmo medias para la agrupación es demostrablemente exponencial incluso en el plano, pero funciona muy bien en la práctica.k

Suresh Venkat
fuente
13

La inferencia de tipo Hindley-Milner es EXPTIME-complete, pero en los programas que la gente suele escribir es bastante lineal.

Neel Krishnaswami
fuente
1
¿No es esto un poco diferente? Recuerdo que podríamos caracterizar una condición necesaria para que Hindley-Milner funcione mal (let profundamente anidado) y, por lo tanto, HM es bueno en la práctica es que esta anidación es, en la práctica, limitada bastante baja (usualmente sangramos más a medida que avanzamos) profundizamos en las ataduras y nos ponemos nerviosos a medida que nos dirigimos hacia el borde más a la derecha de la pantalla ...) De acuerdo, he hecho este reclamo de memoria antes y recientemente no pude recuperar la referencia para ello.
Rob Simmons
2
No, esa no es una condición necesaria. Puede dar una secuencia de enlaces de let (¡sin anidamiento!) De modo que cuadre el tamaño del tipo inferido con cada entrada adicional en la secuencia. Consulte cstheory.stackexchange.com/questions/2428/… para ver un ejemplo.
Neel Krishnaswami
El ejemplo está en SML, y estoy más familiarizado con la forma de hacer las cosas de OCaml, pero si esa secuencia de enlaces fuera "let", entonces creo que estarían anidados. Es solo porque definen funciones globales que no son, pero hay un anidamiento implícito aquí: una definición dada tiene acceso a todas las definiciones anteriores y ninguna de las siguientes.
amnn
1
@amnn: La anidación a la que se hace referencia fue anidando en la forma que se está vinculando, es decir, let z = (let y = e in e') in e''en lugar de que let y = e in let z = e' in e''.
Neel Krishnaswami
9

El programa nauty de Brendan McKay (No AUTomorphisms, Yes?) Resuelve el problema de etiquetado canónico de los gráficos (resolviendo simultáneamente los problemas de isomorfismo gráfico y automatismo gráfico) y tiene un rendimiento exponencial en el peor de los casos (Miyazaki, 1996). Sin embargo, funciona muy rápidamente para la mayoría de los gráficos, especialmente aquellos con algunos automorfismos.

Específicamente, el algoritmo comienza dividiendo los vértices por grado, luego por el grado entre cada parte. Cuando este proceso se estabiliza, se debe elegir distinguir un vértice en una parte no trivial, y esto conduce al comportamiento exponencial. En la mayoría de los gráficos, la profundidad de este procedimiento de ramificación es pequeña.

Derrick Stolee
fuente
Pensé que nauty también usó algo de aleatoriedad para ayudar en el refinamiento En ese caso, esto podría ser muy análogo al algoritmo simplex (aunque obviamente no existe una noción de análisis suavizado para el isomorfismo gráfico).
Joshua Grochow
1
No utiliza aleatoriedad, ya que necesita hacer un etiquetado canónico consistente. Sin embargo, puede usar un procedimiento de invariante de vértices personalizado para ayudar a dividir los vértices. A veces, este invariante parece aleatorio cómo se produjo (con frecuencia, es una función complicada en secuencias de grados de distancia), pero eso es solo para reducir las colisiones.
Derrick Stolee
1
Este vértice invariante se puede comparar con las reglas anti-ciclismo del algoritmo simplex.
Derrick Stolee
4

Varios algoritmos para juegos estocásticos simples funcionan bien en la práctica, a pesar de que tienen tiempos de ejecución exponenciales en el peor de los casos. Por supuesto, este problema está relacionado en cierto sentido con la programación lineal, aunque no se sabe que esté en tiempo polinómico.

Peter Shor
fuente
1

Hay un algoritmo para encontrar equilibrios mixtos de Nash que es similar al algoritmo simplex para LP. (Olvidé el nombre). Tiene una complejidad exponencial en el peor de los casos, pero tengo un vago recuerdo de que a menudo se comporta bien en la práctica.

Warren Schudy
fuente
¿Te refieres al algoritmo de Lemke-Howson?
Rahul Savani
1

El empaquetado de contenedores (muchas variantes) es un problema cuya complejidad se sabe que es NP-hard:

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

Sin embargo, muchas heurísticas cuando se aplican a versiones "prácticas" funcionan muy bien. Para el embalaje de contenedores unidimensionales, algunas de estas heurísticas, como primer ajuste; primer ajuste decreciente; mejor ajuste; la disminución de mejor ajuste es muy atractiva como temas para mostrar a los estudiantes. Los estudiantes a menudo pueden descubrir algunas de las heurísticas básicas por sí mismos.

Joseph Malkevitch
fuente
Hay muchos ejemplos, incluso si el problema es NP-completo, pueden resolverlo algoritmos simples. Especialmente con algoritmos de aproximación. Pero en realidad estoy buscando algoritmos de tiempo exponencial, su ejemplo está relacionado con un problema difícil que es fácil de resolver con algoritmos simples. Tal vez haya un algoritmo de tiempo exponencial para resolver el empaquetado Bin (u otro problema) exactamente; y en la práctica lleva tiempo polinómico.
Arman el
0

El algoritmo de persistencia (originario de Edelsbrunner-Letscher-Zomorodian, con muchas variaciones desde entonces) es el peor de los casos cúbicos, pero parece que, por experimentación, generalmente se ejecuta en tiempo lineal.


fuente