1) Reducir el espacio del problema
Por ejemplo, si no podemos resolver TSP en gráficos generales, intentemos resolverlo solo para gráficos que obedecen a una métrica de distancia euclidiana.
2) Algoritmos de aproximación
- Cómo comprender claramente el propósito de los lenguajes regulares (informática)
- ¿Cómo se estructura un virus informático?
- Desde la perspectiva de la interacción hombre-computadora, ¿qué sentimientos / emociones debe evocar un sitio web para atraer a un usuario?
- En Xcode, ¿por qué no puedes construir y ejecutar un archivo C ++? Por ejemplo, ¿por qué tiene que crear un proyecto completo si lo único que desea ejecutar es un archivo C ++ para programar concursos, etc.?
- ¿Cuál es el proceso de venta de patentes relacionadas con la informática y la tecnología?
Algunos problemas NP-hard admiten algoritmos de aproximación de tiempo polinomial. A veces, esto solo da una aproximación de factor constante en el mejor de los casos, como MAX-CUT o Metric TSP, y a veces produce un Esquema de aproximación de tiempo polinómico, por el cual se puede cambiar el tiempo de ejecución adicional por una mejor aproximación. (Es el tiempo polinómico en n con 1 / épsilon en el exponente). En el caso de Euclidean TSP, hemos tenido dicho algoritmo desde 2010.
3) Algoritmos aleatorios
Esto no se trata únicamente de resolver problemas difíciles de NP, ya que existen razones legítimas para usar algoritmos aleatorios para acelerar la resolución de problemas en P también. Sin embargo, la aleatorización ofrece un camino para resolver los problemas NP-hard más rápidamente. La idea es eliminar la garantía de que el algoritmo funcione siempre, pero que tenga éxito al menos 2/3 del tiempo, dependiendo de la suerte del sorteo. Al volver a ejecutar el algoritmo hasta que tenga éxito o aumente nuestra confianza al nivel deseado, podemos obtener una probabilidad arbitrariamente alta de una respuesta correcta. Esta táctica probablemente nos permite resolver algunos problemas difíciles de NP en la teoría de control robusta y la teoría de matrices en tiempo polinómico. La principal ventaja de los algoritmos aleatorios es la simplicidad. Estos algoritmos son frecuentemente muy simples de describir e implementar. A veces, se pueden transformar en algoritmos deterministas complicados que mantienen sus garantías de aproximación. Con frecuencia, nos permiten muestrear el espacio del problema para crear una solución en un conjunto de entrada más pequeño, para tratar de extrapolar la solución al espacio más grande. También pueden permitirnos reducir la dimensionalidad de un problema mientras mantenemos parte de su estructura.
4) Algoritmos de tiempo exponencial mejorados
El hecho de que un problema sea NP-completo no significa que tengamos que forzarlo por fuerza bruta. Incluso si debemos usar un algoritmo de tiempo exponencial, no todos estos algoritmos son iguales, por lo que siempre estamos en busca de mejoras en dichos algoritmos. Considere el Tamiz de campo de número general para factorizar. (Sí, sé que no se ha demostrado que el factoring sea NP-difícil, sigue siendo un buen ejemplo). Se necesita bastante tiempo para ejecutarlo, exponencial en el tamaño del número que se va a factorizar, pero está a pasos agigantados. de, digamos, división de prueba. Se pueden tener en cuenta números muy grandes en la computadora de su hogar en un día o dos.
A veces, los algoritmos de tiempo exponencial realmente se ejecutan bastante rápido en la práctica. Por ejemplo, el algoritmo simplex para programas lineales todavía se usa a pesar de su tiempo de ejecución exponencial en el peor de los casos, ya que es muy simple de implementar y extremadamente rápido en la mayoría de los ejemplos del mundo real.
5) ¡Paralelo!
Las máquinas se están volviendo masivamente paralelas, y cada parte paralela se está volviendo más rápida por sí misma. Se pueden realizar millones de operaciones simultáneas en la GPU o FPU (o matrices de las mismas) en computadoras modernas. Cuando los cálculos para un problema se pueden hacer en paralelo, deja de importar que exponencialmente se deban hacer muchos cálculos. En el mundo real, lo que importa es la hora del reloj de pared. Por supuesto, no todos los problemas admiten soluciones fácilmente paralelizables …
6) ¡Solo fuerza bruta!
Incluso los procesadores en serie son cada vez más rápidos. Incluso si tiene que usar un algoritmo de tiempo exponencial lento Y realizar todos los cálculos en secuencia, como mínimo, puede obtener una supercomputadora moderna cegadoramente rápida para que lo haga por usted. Nuevamente, lo que importa es el tiempo del reloj de pared, no el número de pasos en el cálculo.