En ciencias de la computación, los métodos de búsqueda no informados o ciegos son estrategias de búsqueda en las cuales se evalúa el siguiente estado sin conocer a priori si este es mejor o peor que el anterior.
Representación del espacio de estados
Un problema típico de la Inteligencia Artificial consiste en buscar un estado concreto entre un conjunto determinado, al que se le llama espacio de estados. Imaginemos, por ejemplo, una habitación con baldosines en la que hay un libro. Un robot se desea desplazar por la habitación con el fin de llegar a dicho libro. ¿De qué manera lo hará? En este punto es donde entran en juego las estrategias y los algoritmos de búsqueda.
Cuando el sistema agente (en este caso, el robot) posee algún tipo de información del medio, se utilizan técnicas de búsquedas informadas; sin embargo, si carece de conocimiento alguno, se deberán emplear algoritmos de búsqueda no informadas. En nuestro ejemplo, y para este último caso, podemos imaginar un robot que no posea ningún tipo de visión artificial, que únicamente sea capaz de moverse en horizontal o vertical de un baldosín a otro y detectar si en el baldosín se halla el libro.
En general los algoritmos ciegos son más ineficientes en tiempo y memoria que otros métodos, tales como los heurísticos o la búsqueda con adversario.
Tipos de métodos de búsqueda no informada
Búsqueda en profundidad
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. En general, este tipo de algoritmos recorre el espacio de estados de una forma concreta hasta dar con el objetivo (en este caso, el libro). Nuestro primer método se denomina búsqueda en profundidad.
Supongamos el árbol del dibujo representando un espacio de estados cualquiera. Vemos que, teniendo este árbol delante con sus nodos numerados, tenemos distintas formas de recorrerlo. ¿Cómo lo hacemos en profundidad? Siendo el 1 el nodo inicial y 7 el nodo objetivo que se debe alcanzar, hacemos lo siguiente: buscaremos en todas las ramas que cuelgan, de izquierda a derecha, y exploramos cada rama hasta llegar a una hoja. Para cada hijo buscamos a su vez en profundidad, parando cuando se encuentre el objetivo. En este ejemplo, la secuencia a seguir está indicada por el número de los nodos: 1-> 2-> 3-> 4-> 5-> 6->
Si el camino tiene longitud k y factor de ramificación r, la complejidad espacial del algoritmo está en O (kr). Su complejidad temporal depende tanto del factor de ramificación como de la profundidad de la solución. Siendo n el número medio de hijos expandidos, y si la solución se alcanza en el nivel p, la complejidad temporal está en O (n^p); es, por tanto, un coste exponencial.
Este algoritmo de búsqueda, además, no es completo, ya que si existe solución y se mete por una rama infinita puede que no termine nunca. Tampoco es óptimo, ya que puede encontrar la solución pero haciendo un recorrido mayor del necesario en general. Se ha usado una estructura pila LIFO para implementarlo.
Búsqueda en anchura
Otra opción para recorrer el espacio de estados sin conocer ninguna información acerca del mismo es recorrerlo en anchura. Como su nombre indica, el recorrido realizado se lleva a cabo visitando todos los nodos de un nivel, de izquierda a derecha, pasando posteriormente al nivel siguiente, hasta que se encuentre el nodo objetivo, momento en el que se detiene el algoritmo. Lo vemos en el dibujo con el mismo ejemplo de antes, numerando los nodos con el orden que les corresponde según el recorrido en anchura.
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.
Este procedimiento es completo, ya que encontrará siempre una solución si es que la hay, pero en general no es óptimo. Para implementarlo se ha hecho uso de una cola FIFO.
Búsqueda en profundidad limitada
Es una variante de la búsqueda en profundidad, donde se establece un límite de profundidad.
Búsqueda en profundidad iterativa
Es una variante de la búsqueda en profundidad limitada, donde la cota de profundidad elegida va aumentando si no encuentra una solución.
Búsqueda en coste uniforme
La búsqueda comienza por el nodo raíz y continúa visitando el siguiente nodo que tiene menor costo total desde la raíz, es decir con menor costo acumulado. Se controla el acumulado, pero no se estima lo que falta (para ello debería ser un algoritmo heurístico. Es una variante del algoritmo de Dijkstra. También es una variante de la búsqueda en anchura donde el coste es la profundidad del camino.
Se trata de una búsqueda completa, si no se producen bucles. Así mismo, es una búsqueda óptima, si es función del coste.
Búsqueda bidireccional
Es un método en el cual se realiza simultáneamente una búsqueda desde el estado inicial y otra búsqueda desde el estado objetivo.
Si quieres conocer otras notas parecidas a Comparación: búsqueda informada vs no informada puedes visitar la categoría Inteligencia.