Tema

Búsqueda no informada

IA clásica
Nivel base

La búsqueda no informada recorre el grafo de estados usando solo la estructura del problema, y sus tres variantes de examen son anchura, profundidad y coste uniforme, que expande siempre el nodo de menor coste acumulado.

Nombre en inglés

Uninformed search

Intuición

Conviene imaginar una mancha de tinta que se extiende desde el estado inicial. En anchura la mancha crece en círculos concéntricos por número de pasos, en coste uniforme crece en círculos por coste acumulado, y en profundidad se convierte en un hilo que baja hasta el fondo antes de probar la siguiente rama. Anchura encuentra el camino con menos pasos y profundidad gasta poca memoria, de ahí que la elección sea un canje entre memoria y garantías.

Fórmula

BFS cuesta O(b^d) en tiempo y O(b^d) en memoria.  DFS cuesta O(b^m) en tiempo y O(b m) en memoria.  UCS cuesta O(b^{1 + C*/e})

Ejemplo resuelto

Un árbol con factor de ramificación b igual a 2 y solución a profundidad d igual a 3 tiene 1 + 2 + 4 + 8 = 15 nodos hasta ese nivel. La búsqueda en anchura guarda en la frontera hasta 8 nodos, que son los del último nivel abierto, mientras que la búsqueda en profundidad guarda como mucho 3 niveles por 2 hijos, o sea 6 nodos. Con b igual a 10 y d igual a 6 la diferencia deja de ser anecdótica, porque anchura necesita del orden de un millón de nodos en memoria y profundidad necesita 60.

Errores frecuentes

Olvidar el conjunto de estados ya expandidos en un grafo con ciclos, con lo que la búsqueda repite trabajo sin fin aunque el espacio de estados sea pequeño.
Dar por óptima la búsqueda en anchura cuando los arcos tienen costes distintos, ya que el camino con menos aristas puede ser el más caro y ahí hace falta coste uniforme.
Comprobar si un nodo es meta al generarlo en coste uniforme en lugar de al expandirlo, error que devuelve un camino subóptimo cuando existe otra ruta más barata todavía en la frontera.

Ejercicio

En un grafo con arcos de coste 1 salvo uno de coste 10, la búsqueda en anchura devuelve un camino de 2 aristas y coste 11, y existe otro camino de 3 aristas y coste 3. Indica qué devuelve la búsqueda de coste uniforme y por qué.

Ver la solución

La búsqueda de coste uniforme ordena la frontera por el coste acumulado g(n), de modo que expande primero todos los nodos alcanzables con coste 3 antes de tocar el arco de coste 10. Al llegar a la meta por el camino de 3 aristas su coste acumulado es 3, que es menor que 11, y como la frontera no contiene ningún nodo con coste menor que 3 la solución devuelta es óptima.

Respuesta: El camino de 3 aristas y coste 3.