Antes de dar un ejemplo, debo aclarar algo de terminología. Su pregunta indica que tal vez esté un poco confundido acerca de lo que se entiende por “algoritmo heurístico”, porque los algoritmos heurísticos a menudo tienen tiempos de ejecución de gran O muy grandes; Por eso necesitamos una heurística. El tiempo de ejecución Big-O es (tradicionalmente / por defecto) el peor tiempo de ejecución; Utilizamos una heurística para hacer que un algoritmo se ejecute rápidamente en los casos más comunes. En otras palabras, la heurística captura algo sobre el dominio del problema para que los problemas que realmente encuentre no sean el peor de los casos.
Veamos ejemplos. El Boolean Satisfiability Problem (SAT) es un problema clásico de NP completo, por lo que cada algoritmo conocido tiene un tiempo de ejecución exponencial en el peor de los casos. El problema consiste en decidir si las variables en una expresión booleana dada (variables ANDed, ORed y NOTed juntas) pueden asignarse valores de verdad de modo que toda la expresión sea verdadera. Por ejemplo, “a AND b” es trivialmente satisfactoria; “A AND NOT a” es trivialmente insatisfactorio.
¿Dónde podríamos necesitar resolver este problema? Bueno, a menudo queremos simplificar alguna expresión booleana. Esto sucede en el diseño de circuitos integrados, por ejemplo, que en gran medida se realiza por software en estos días. Tenga en cuenta que simplificar completamente una expresión booleana es al menos tan difícil como decidir si es satisfactoria, porque si no lo es, se simplifica a FALSO.
- ¿Qué es un algoritmo para programar un torneo para que termine en el menor tiempo posible, dado un torneo round robin (donde cada jugador juega entre sí) entre n jugadores (n es par) que puede representarse con un gráfico completo?
- ¿Es posible hackear usando el lenguaje de programación C?
- ¿Cuál es la mejor manera de estudiar la estructura de datos de árbol?
- ¿Cómo se puede resolver el coeficiente binomial usando programación dinámica y tabla hash?
- ¿Cuáles son los mejores proyectos de estructura de datos para los estudiantes?
Para obtener la respuesta a su pregunta, resolvemos este problema utilizando algoritmos con una complejidad de tiempo exponencial, como picosat (entre muchos otros) y, sin embargo, a menudo lo resolvemos para expresiones muy grandes. Los algoritmos utilizados son a menudo fundamentalmente bastante simples (adivinar y dar marcha atrás cuando se encuentra un conflicto; véase, por ejemplo, el aprendizaje de cláusulas controladas por conflictos), pero se hacen rápidamente en casos comunes (por ejemplo, muchas cláusulas OR juntas, con pocos AND y NOTs) por heurística sobre qué variables elegir y cómo retroceder.
El punto clave es que el tiempo de ejecución Big-O no lo es todo. Si lo fuera, los algoritmos de tiempo exponencial simplemente serían inviables con entradas suficientemente grandes. Tal como están las cosas, las entradas generalmente están restringidas a pequeños subconjuntos del dominio que pueden resolverse en un tiempo razonable.
Hay muchos otros problemas para los cuales se toman enfoques similares. En particular:
- Para el famoso problema de la mochila, tenemos un algoritmo que es de tiempo lineal tanto en el número de pesos de entrada como en el peso total. Este es un tiempo técnicamente exponencial, porque el tamaño de entrada es logarítmico en el peso total utilizando una representación binaria.
- El isomorfismo gráfico, nuevamente utilizado en EDA, para el cual existen algoritmos eficientes para prácticamente todos los gráficos comunes pero que no tiene un algoritmo de tiempo polinomial conocido.
