Estrategias de búsqueda

Búsqueda preferente por amplitud: 

En esta búsqueda todos los nodos que están en la profundidad d del árbol de búsqueda se expanden antes de los nodos que estén en la profundidad d+1.

• Si son varias las soluciones, este tipo de búsqueda permitirá siempre encontrar primero el estado meta más próximo a la raíz. 

• En esta búsqueda el tiempo y la cantidad de memoria necesaria crece exponencialmente con respecto a la profundidad. 

• Es óptima y completa.

Búsquedas de costo uniforme: 

En esta búsqueda se modifica la estrategia preferente por amplitud en el sentido de expandir siempre el nodo de menor costo en el margen (medido por el costo de la ruta g(n)) en vez del nodo de menor profundidad.

Este tipo de búsqueda permitirá siempre encontrar la solución mas barata siempre y cuando el costo de ruta nunca disminuya conforme avanzamos por la ruta.

En esta búsqueda el tiempo y la cantidad de memoria necesaria crece exponencialmente con respecto a la profundidad.

• Es óptima y completa.

Búsqueda preferente por profundidad:

En esta búsqueda siempre se expande uno de los nodos que se encuentren en los mas profundo del árbol. Solo si la búsqueda conduce a un callejón sin salida, ser revierte la búsqueda y se expanden los nodos de niveles menos profundos.

Esta búsqueda o se queda atorada en un bucle infinito y nunca es posible regresar al encuentro de una solución, o a la larga encontrará una ruta de solución mas larga que la solución óptima.

• En esta búsqueda el tiempo necesario crece exponencialmente con respecto a la profundidad, mientras que el espacio requerido en memoria lo hace en forma lineal

• No es óptima ni completa. 

Búsqueda limitada por profundidad: 

Esta búsqueda es similar a la búsqueda preferente por profundidad con la diferencia que se impone un límite a la profundidad máxima de una ruta.Se utilizan operadores que informan constantemente de la profundad del nodo. 

• En esta búsqueda el tiempo necesario crece exponencialmente con respecto a la profundidad, mientras que el espacio requerido en memoria lo hace en forma lineal

• No es óptima, pero si completa cuando la profundidad del límite es menor o igual a la profundidad de la solución. 

Búsqueda por profundización iterativa: 

Esta búsqueda es similar a la búsqueda limitada por profundidad con la diferencia que se repiten las búsquedas dando en cada iteración un valor distinto de profundiad para la misma.

En esta búsqueda el tiempo necesario crece exponencialmente con respecto a la profundidad, mientras que el espacio requerido en memoria lo hace en forma lineal

Es óptima y completa. 

Búsqueda bidireccional: 

Esta es una búsqueda que avanza a partir del estado inicial y que retrocede a partir de la meta y que se detiene cuando ambas búsquedas se encuentran en algún punto intermedio. 

En esta búsqueda el tiempo y el espacio requerido en memoria crecen exponencialmente con respecto a la mitad de la profundidad (bd/2). 

Es óptima y completa.