APUNTE DE MA. ELENA FECHA: 09-06-09

ESTRATEGIAS DE BUSQUEDA

En general, los algoritmos de búsqueda deben implementar 2 tareas para la consecución del objetivo final:

1. Permitir la transición de un estado a otro mediante operadores o acciones.
2. Controlar en cierto modo esos movimientos, porque habitualmente responden a decisiones que se han ido tomando.

La búsqueda aleatoria puede funcionar en algunos problemas, pero en general, la búsqueda debe ser organizada, debe realizarse de forma metódica para que sea más eficiente y tener control de la misma. Por eso, las tareas de búsqueda se clasifican en dos grandes grupos según sea la situación inicial o el planteamiento del problema a resolver:

· La búsqueda sistemática que no utiliza información sobre el problema para ayudarse en esa búsqueda directa en el espacio de estados, es la llamada búsqueda ciega o fuerza bruta. Es decir, no hay cambios prioritarios en el recorrido hacia el objetivo final. La única diferencia entre las distintas técnicas que se aplica este tipo de búsqueda es el distinto orden en el que los nodos se expanden. Pero en este caso, incluso cambios muy pequeños pueden tener un impacto decisivo en el comportamiento del algoritmo.
· Los algoritmos de búsqueda que utilizan información sobre el problema, como el coste o la distancia al estado final, se denominan heurísticos o búsqueda dirigida o respaldada con información. La principal ventaja de estos es que se puede seleccionar con más fundamento con cual siguiente nodo que debe expandirse, lo que mejora la eficiencia de la búsqueda.

Para juzgar la eficiencia de una búsqueda e incluso determinar si se trata de una búsqueda a ciegas o una búsqueda heurística, hay algunos conceptos a considerar, por ejemplo:

Ø Coste de un ario
Ø Coste de un nodo
Ø Factor de ramificación
Ø Longitud de trayectoria
Ø Profundidad

BUSQUEDA HEURISTICA

Las estrategias de búsqueda se caracterizan por la tendencia a limitar el tiempo y el espacio en donde buscar la respuesta a problemas complejos, y asumir que aceptaremos cuando una buena solución, que no puede ser óptima. En este sentido, se aplican reglas heurísticas o empíricas para determinar a lo largo de un recorrido cuál es el trayecto que con mayor probabilidad nos lleve a una solución.
Los algoritmos vistos anteriormente (en profundidad y en anchura) se denominan en general algoritmos de generación y prueba. En su implementación más básica, los pasos para ejecutarla son:
1. Generar una posible solución, ya sea un nuevo estado o un camino a través del espacio de búsqueda.
2. Probar si ese nuevo estado a camino generado es una solución comparándolo con un conjunto de estados objetivo.
3. Si es la solución, terminar. En otro caso volver al paso 1.
Se debe observar que la principal desventaja radica en que no hay ninguna información relativa a en qué dirección orientar la búsqueda, lo que hizo necesario desarrollar otras estrategias para incorporar este tipo de conocimiento con el uso de las funciones heurísticas.

La búsqueda heurística utiliza información adicional sobre el problema específico, como el coste o la distancia al estado final. Para tener en cuenta esta información los métodos heurísticos utilizan las denominadas funciones de evaluación heurísticas (f) que calculan o evalúan el valor de cada nodo particular en el árbol de búsqueda dando una idea de lo cerca o lejos que se encuentra el nodo objetivo.

Con estos valores se puede estimar el coste que llevaría a recorrer sus ramificaciones, guiando la búsqueda hacia aquellos caminos que parecen más prometedores. Los métodos heurísticos principales son:

· Ascensión a la cima o gradiente
· Primero el mejor
· Búsqueda avara
· Algoritmo A*
· Algoritmos genéticos