III. Espacio de busqueda
Espacio de busqueda
Cuando resolvemos un problema, normalmente buscamos una solucion que sea la mejor entre todos los candidatos posibles. El conjunto de todas las soluciones factibles (es decir, el conjunto de objetos entre los cuales se encuentra la solucion deseada) se llama espacio de busqueda (tambien llamado espacio de estados). Cada punto del espacio de busqueda representa una solucion factible. Cada solucion factible puede "marcarse" por su valor o aptitud para el problema. Nuestro objetivo es encontrar la solucion, que corresponde a uno o mas puntos del espacio de busqueda.
Por lo tanto, buscar una solucion equivale a buscar algun extremo (un minimo o maximo) en el espacio de busqueda. Puede que se conozca todo el espacio de busqueda cuando se esta resolviendo el problema, pero mas a menudo solo conocemos unos pocos puntos y vamos generando otros adicionales a medida que continua la busqueda.
Ejemplo de un espacio de busqueda
El problema es que esta busqueda puede ser muy complicada. A menudo no esta claro donde empezar ni donde buscar la solucion. Existen muchos metodos para encontrar una solucion adecuada (es decir, no necesariamente la mejor solucion), como la escalada de colinas (hill climbing), la tabu search, el recocido simulado (simulated annealing) y el algoritmo genetico. La solucion encontrada por estos metodos suele considerarse buena, porque con frecuencia es imposible demostrar cual es el optimo real.
Problemas NP-hard
Ejemplos de problemas dificiles que no pueden resolverse de una manera "tradicional" son los problemas NP.
Hay muchas tareas para las cuales conocemos algoritmos rapidos (polinomiales). Tambien hay algunos problemas que no pueden resolverse algoritmicamente en tiempo polinomial. Para algunos problemas se ha demostrado que no existe una solucion en tiempo polinomial.
Pero hay muchas tareas importantes para las cuales es muy dificil encontrar una solucion, aunque una vez que la tenemos, es facil verificarla. Este hecho dio origen a la clase de problemas NP-completos. NP significa polinomial no determinista, lo que quiere decir que es posible "adivinar" una solucion (usando algun algoritmo no determinista) y luego verificarla, ambas cosas en tiempo polinomial. Si tuvieramos una maquina capaz de adivinar, podriamos encontrar una solucion en un tiempo razonable.
Para simplificar, el estudio de los problemas NP-completos suele restringirse a problemas en los que la respuesta solo puede ser si o no. Como tambien existen tareas con salidas mas complejas, se introdujo la clase de problemas NP-hard. Esta clase es mas amplia que la clase de problemas NP-completos.
Los problemas NP suelen caracterizarse por el hecho de que, a primera vista, es obvio un algoritmo sencillo para encontrar una solucion: simplemente probar todas las soluciones posibles. Pero este algoritmo es muy lento (a menudo O(2^n)) y, incluso para instancias un poco mas grandes del problema, se vuelve totalmente impractico.
Hoy nadie sabe si existe algun algoritmo exacto mas rapido. Demostrarlo o refutarlo sigue siendo un gran reto para los investigadores. Muchas personas piensan hoy que ese algoritmo no existe y, por eso, buscan metodos alternativos, como los algoritmos geneticos.
Ejemplos de problemas NP incluyen el problema de satisfacibilidad, el problema del viajante de comercio y el problema de la mochila. Hay un compendio de problemas NP disponible.
·