Introducción a los Algoritmos y Heurísticas de Búsqueda

Introducción a los Algoritmos

Un algoritmo es "polinomial" si el número de operaciones que realiza para procesar n datos es directamente proporcional a un polinomio f(n) = n^k.

Problemas P y NP

• Problemas P: Problemas (no algoritmos) que pueden resolverse en un tiempo polinomial en una máquina determinista (ante la misma entrada siempre dan el mismo resultado). Ej. Potencias.
• Problemas NP: Existe algún algoritmo que puede averiguar una solución y a continuación verificar si esa solución es correcta en tiempo polinomial. Ej. Raíz cuadrada.
• Problemas NP-completos: Los más difíciles de NP. Se ha demostrado que están en P todos los problemas completos de NP o no está ninguno. Ej. Problema del viajante.

Búsqueda Heurística

En griego significa descubrir o encontrar. Un heurístico es una ayuda para guiar el proceso de búsqueda. Con la utilización de heurísticos no se van a conseguir siempre resultados óptimos, pero sí se van a conseguir resultados de buena calidad en media en un tiempo razonable.

Se utilizan en problemas complejos donde aparece el problema de la explosión combinatoria. En algunas ciencias, es una manera de buscar la solución de un problema mediante métodos no rigurosos, como por tanteo, reglas empíricas, intuición.

Tipos de Heurísticos

Podemos clasificar los heurísticos en 2 grupos:

• Generales: Válidos para muchos problemas diferentes (ej. vecino más próximo).
• Específicos: Diseñados para un problema particular.

Ventajas de los Heurísticos

• Evitan la explosión combinatoria.
• En problemas complejos no necesitamos soluciones óptimas sino suficientemente buenas.
• No se da normalmente el caso peor en que las aproximaciones conseguidas con heurísticos no sean buenas.
• Entender por qué funciona un heurístico nos da un conocimiento mayor del problema que intentamos resolver.

Una buena función heurística permite disminuir notablemente la complejidad tanto espacial como temporal.

Búsqueda Primero el Mejor

Esta sección muestra cómo una estrategia de búsqueda informada puede encontrar soluciones de una manera más eficiente que una estrategia no informada.

Se expande primero el nodo que proporciona un mejor valor (f<) para la función de evaluación (se expanden primero los nodos más cercanos al objetivo).

Búsqueda Avara

No es óptima. Es incompleta (puede ir hacia abajo en un camino ∞ y nunca volver). Complejidad temporal O(b^m), complejidad espacial O(b^m).

El Algoritmo A*

Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo pasando por n.

A* es óptimo y completo si h(n) es una heurística admisible: con tal de que h(n) nunca sobrestime el coste de alcanzar el objetivo.

El tiempo computacional no es la principal desventaja sino la memoria (se queda sin mucho espacio antes de quedarse sin tiempo). A* no es práctico para problemas grandes.

Shakey el Robot (1966-1972)

Es un robot móvil, construido en el Stanford Research Institute (SRI), equipado con sensores de tacto y cámaras. Shakey habita en una de varias habitaciones interconectadas, en medio de un montón de bloques de madera.

Si a Shakey se le pide mover un objeto, desde un origen a un destino determinado, éste busca la manera más óptima de llevarlo a cabo utilizando los medios más apropiados.