BÚSQUEDA A CIEGAS

INTRODUCCIÓN

Consiste en buscar un estado concreto entre un conjunto determinado, al cual se lo conoce como 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 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.

cONTENIDO

Representación del espacio de estados

El conjunto de estados que el agente debe recorrer, generalmente se representa mediante un grafo, aunque en algunos casos concretos utilizaremos árboles. Siguiendo con nuestro ejemplo, cada nodo del grafo representará a uno de los baldosines de la habitación, y dos nodos serán adyacentes si también lo son sus baldosines correspondientes.

La 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.

La 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

CONCLUSIONES

El algoritmo de búsqueda en ANCHURA SE BASA EN NIVELES LO CUAL OCUPA MAYOR ESPACIO EN MEMORIA SIENDO AUN MENOS EFICIENTE QUE EL ALGORITMO DE BÚSQUEDA PRIMERO EN  PROFUNDIDAD EL CUAL SE BASA EN CAMINOS DESDE EL NODO RAÍZ  EN EL CASO QUE NO ENCUENTRE LA SOLUCIÓN DARÁ UN RETROCESO  Y TOMARA OTRA RUTA Y LO YA RECORRIDO NO LO MANTENDRÁ EN MEMORIA SIENDO MAS EFICIENTE QUE LA OTRA BÚSQUEDA.

BIOGRAFÍA

Palma M., José; Marin M. Roque. 2008. Inteligencia artificial, técnicas métodos y aplicaciones. Primera Edición. Mc Graw Hill. Chile.