Buena parte de los esfuerzos invertidos en el área de la búsqueda han quedado en la determinación de la estrategia de búsqueda adecuada para un problema. Se utiliza para hallar una solución "sin información".

• Búsqueda preferente por amplitud
• Búsqueda de costo uniforme
• Búsqueda preferente por profundidad
• Búsqueda limitada por profundidad
• Búsqueda por profundización iterativa
• Búsqueda birideccional

Para explicar mejor las estrategias imaginemos un problema sencillo como : "Ir en auto de Arad a Bucarest utilizando las carreteras del mapa de Rumania"

Primero se expande el nodo más superficial del árbol de búsqueda. Es un método completo, óptimo para operadores de costo unitario. Su complejidad espacio-temporal es O(b^d). En muchos casos, la complejidad espacial impide que sea práctico.

Debo expandir la profundidad (d) antes de expandir la profundidad siguiente (d+1) empezando por la izquierda.

d = profundidad

nodo raíz = estado inicial

Primero se expande el nodo hoja de menor costo. Es un método completo y, a diferencia de la búsqueda preferente por amplitud, es óptimo incluso si el costo de cada uno de los operadores es distinto. Su complejidad espacio-temporal es la misma que la de la búsqueda preferente por amplitud.

Siempre se tiene un costo o unidades. Los costos deben ser positivos, caso contrario no se aplica esta búsqueda.

Tómese el caso del problema de la determinación de ruta que radica en ir de S a G.

Respuesta: S-B-G

Primero se expande el nodo más profundo del árbol de búsqueda. No es un método completamente óptimo; su complejidad temporal O(b^m) y su complejidad espacial es O(bm), en donde m es la profundidad máxima. Los árboles de búsqueda cuya profundidad es muy grande o infinita, invalidan la utilidad de este método.

Sólo si la búsqueda conduce a un callejón sin salida (un nodo sin meta que no tiene expansión), se revierte la búsqueda y se expanden los nodos de niveles menos profundos.

El genérico problema de los misioneros y caníbales puede exponerse de la siguiente manera: tres misioneros y tres caníbales están en una de las márgenes de un río, junto a una lancha en la que sólo caben una o dos personas. Hay que encontrar la manera de pasarlos a todos al otro lado del río, pero teniendo cuidado de que en ningún momento quede un grupo de misioneros junto con un grupo de caníbales, siendo la cantidad de misioneros menor a la de los caníbales.

Se pone un límite a la búsqueda preferente por profundidad. Si el límite fuera igual a la profundidad del estado meta más superficial, se reduce al mínimo la complejidad espacio-temporal.

Se emplea la búsqueda con límite de profundidad, pero los límites van aumentando hasta encontrar una meta. Es completa y óptima; su complejidad temporal es O(b^d) y su complejidad espacial es O(bd).

Ayuda a reducir notablemente la complejidad temporal, aunque no siempre pueda utilizársele. La cantidad de memoria que necesita puede hacerla poco práctica.

Es básicamente, una búsqueda simultánea 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.