Búsquedas no informadas

Un robot se desea desplazar por la habitación con el fin de llegar a dicho libro.

En este grafo se aplica una correspondencia entre los nodos del mismo y los baldosines numerados de igual forma.

Supongamos que nuestro robot no tiene ninguna capacidad especial para poder moverse por la habitación de una manera eficiente (desconoce cualquier información útil para poder llegar al libro de la forma más corta): entonces deberá seguir un algoritmo de búsqueda no informada (“un método ciego”) para llegar hasta él.

Supongamos el árbol del dibujo representando un espacio de estados cualquiera.

En este ejemplo, la secuencia a seguir está indicada por el número de los nodos: 1-> 2-> 3-> 4-> 5-> 6-> 7.

Si el camino tiene longitud k y factor de ramificación r, la complejidad espacial del algoritmo está en O (kr).

Tampoco es óptimo, ya que puede encontrar la solución pero haciendo un recorrido mayor del necesario en general.

En efecto, los nodos que con este algoritmo se visitan hasta encontrar el objetivo (8) son: 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8 Su complejidad tanto espacial como temporal es exponencial, y está en O (n^p), siendo n el número medio de sucesores, y p el nivel donde se alcanza la solución; por ello, esta estrategia es sólo aplicable a problemas no demasiado amplios.