Estrategias de búsqueda óptima: BPA, BCU, BP, BPI y bidireccional

Resumen

El documento presenta las estrategias de búsqueda óptima para encontrar soluciones en un árbol de búsqueda con el menor coste posible. Describe los criterios de evaluación (completitud, optimalidad y complejidades temporal y espacial) y explica la búsqueda en anchura, de coste uniforme, en profundidad, progresiva y bidireccional. También compara cuándo conviene usar la búsqueda en profundidad o en anchura.

Puntos clave

Una estrategia de búsqueda óptima explora la menor parte del árbol para alcanzar el objetivo con el menor coste.
Criterios de evaluación: completitud, optimalidad, complejidad temporal y complejidad espacial.
La búsqueda primero en anchura (BPA) asegura encontrar el camino más corto a la solución.
La búsqueda de coste uniforme (BCU) expande el nodo con menor coste de ruta g(n); con costes iguales equivale a la BPA.
La búsqueda progresiva (BPI) combina las ventajas de BP y BPA: memoria lineal y garantía de encontrar el objetivo más cercano.
La búsqueda bidireccional realiza una búsqueda hacia adelante desde el inicio y otra hacia atrás desde el objetivo, terminando cuando ambas se encuentran.

Ponte a prueba

Estrategias de Búsqueda Óptima

Una estrategia de búsqueda óptima es aquella que explora la menor parte del árbol de búsqueda para alcanzar el objetivo con el menor coste posible. Se basa en dos principios fundamentales:

Explorar todos los nodos del camino a seguir.
No explorar un mismo nodo más de una vez.

Criterios de Evaluación

Completitud: Indica si la estrategia garantiza encontrar una solución.
Optimalidad: Indica si la solución encontrada es la mejor.
Complejidad Temporal: Indica el tiempo necesario para encontrar una solución.
Complejidad Espacial: Indica la memoria necesaria para encontrar una solución.

Búsqueda Primero en Anchura (BPA)

Se aplican todos los operadores al nodo inicial, generando sus sucesores.
Se aplican los operadores a cada nodo en el orden de creación.

Esta estrategia asegura encontrar el camino más corto a la solución.

Búsqueda de Coste Uniforme (BCU)

Utiliza una función de coste de ruta que asigna un coste a cada ruta (ej. km). Por defecto, el coste es 1. Se expande el nodo con menor coste de ruta g(n). Si los costes de todos los arcos son iguales, es equivalente a la BPA. Es útil en problemas donde las aristas tienen costes diferentes.

Búsqueda Primero en Profundidad (BP)

Se expande solo un sucesor del nodo en cada paso. Es eficaz cuando hay muchas soluciones, están lejos del estado inicial y son igualmente deseables.

Búsqueda Progresiva (BPI)

Combina ventajas de BP y BPA. Aprovecha los requisitos de memoria lineales de BP y garantiza encontrar el nodo objetivo más cercano al inicial. Realiza sucesivas búsquedas en profundidad, aumentando la profundidad límite en cada paso. Es más rápida que BPA, a pesar de la repetición de estados. Es el método preferido cuando el espacio de búsqueda es grande y se desconoce la profundidad de la solución.

Búsqueda Bidireccional (BB)

Se realiza una búsqueda hacia adelante (desde el inicio) y otra hacia atrás (desde el objetivo). La búsqueda termina cuando ambas se encuentran en un estado intermedio. Se pueden usar estrategias diferentes en cada dirección.

Conclusión

La BP es útil con muchas metas alejadas del inicio, mientras que la BPA es útil con metas cercanas y pocas.

Preguntas frecuentes

¿Cuándo es útil la búsqueda primero en profundidad?

Es útil cuando hay muchas metas alejadas del estado inicial y son igualmente deseables. Se expande un solo sucesor en cada paso.

¿Cuándo conviene usar la búsqueda primero en anchura?

Es útil cuando las metas están cercanas al inicio y son pocas. Garantiza encontrar el camino más corto a la solución.

¿Qué ventaja tiene la búsqueda progresiva?

Aprovecha los requisitos de memoria lineales de la búsqueda en profundidad y garantiza encontrar el nodo objetivo más cercano al inicial. Es el método preferido cuando el espacio es grande y se desconoce la profundidad de la solución.