Ineficiencia e Intratabilidad
Problemas algorítmicos para los que no existe una solución satisfactoria
Ejemplos
Torres de Hanoi
Puzzle del mono
Torres de Hanoi
Dadas tres estacas y N anillos, secuencia de movimientos para transferir los anillos de una a otra siguiendo ciertas reglas
El procedimiento recursivo implica un movimiento de aro y dos llamadas recursivas
¿Cuántos movimientos son necesarios?
2N-1
Si fuéramos capaces de mover un millón de anillos cada segundo, para N=64. ¿cuánto tiempo tardaríamos?
Medio millón de años
Torres de Hanoi
El puzzle del mono
Nos limitamos a problemas de decisión
N cartas, N=M*M, con orientación fija, ¿existe alguna combinación que forme un cuadrado de M*M en el que todas las mitades estén casadas?
El puzzle del mono
Con N=25 y un computador capaz de construir y evaluar un millón de posibilidades por segundo. Cuanto tiempo tardaría el algoritmo en el caso peor?
Para colocar la primera, 25 posibilidades, para la segunda 24, …. 25!, resultaría que nuestro computador tardaría 490 billones de años en calcular todas las posibilidades
El puzzle del mono
Existen conjuntos de cartas para los que la solución siempre existe, para otros nunca.
¿Existe una manera mejor de resolver el problema?
Probablemente no, pero no estamos seguros
Tiempo razonable/irrazonable
N
Función
Polinomial
Exponencial
El número de protones en el universo tiene 79 dígitos. El número de microsegundos desde el Big Bang tiene 24 dígitos
Admiten algoritmos razonables
No admiten algoritmos razonables
(Gp:) Problemas intratables
(Gp:) Problemas
tratables
Tiempo razonable/irrazonable
Una función polinomial en N es aquella que esta limitada por Nk, para algún k.
Un algoritmo cuyo tiempo de ejecución esta acotado por una función polinomial lo consideramos razonable. En otro caso irrazonable.
En términos de problemas algorítmicos diremos que son problemas tratables o intratables
Problemas NP_Completos
El problema del puzzle, que hemos visto, es realmente un problema intratable?
Quizá es cuestión de esperar que lo computadores sean mas rápidos
Puede ser causa de nuestra incompetencia para idear buenos algoritmos?
No tiene valor el esfuerzo, este problema es un problema especifico, no es importante.
Problemas NP_Completos
Existen cerca de 1000 problemas algorítmicos con características parecidas
Sus limites inferiores son lineales y sus limites superiores exponenciales.
La clasificación de estos problemas es desconocida no sabemos a que lado de la línea están.
Vamos a denotar esta clase como NPC, significando NP-completos.
Problemas NP_completos
Problemas de encontrar caminos
Problema del viajante de comercio: El viajante tiene que visitar N ciudades, hallar el camino mas corto que conecta todas ellas sin que se visite dos veces la misma ciudad.
Problemas NP_completos
El problema del ciclo Hamiltoniano: dado un grafo, existe un camino que pase por todos los puntos exactamente una vez?
Página siguiente |