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 |