ıllı Portal de Psicología y NeuroCiencias

Portal wikinfo sobre psicología y neurociencias.

Enciclopedia/Diccionario de Psicología y Neurociencias:

ıllı Búsquedas no informadas wiki: info, libros pdf y vídeos

Detalles: Categoría: PSICOLOGIA (WIKINFO)

psicologia y neurociencias

Búsquedas no informadas

Un inconveniente propio de la Inteligencia Artificial consiste en buscar un estado específico entre un conjunto determinado, al que se le llama espacio de estados. Imaginemos, por servirnos de un ejemplo, una habitación con baldosines en la que hay un libro. Un robot se quiere mover por la habitación con la intención de llegar a dicho libro. ¿De qué forma lo va a hacer? Es en este punto donde entran en juego las estrategias y los algoritmos de busca.

Cuando el sistema agente (en un caso así, el robot) tiene algún género de información del medio, se usan técnicas de buscas informadas; no obstante, si carece de conocimiento alguno, se van a deber emplear algoritmos de busca no informadas. En nuestro ejemplo, y para este último caso, podemos imaginar un robot que no tenga ningún género de visión artificial, que solamente sea capaz de moverse en horizontal o bien vertical de un baldosín a otro y advertir si en el baldosín se encuentra el libro.

En general los algoritmos ciegos son más ineficientes en tiempo y memoria que otros métodos, como los heurísticos o bien la busca con adversario:

El conjunto de estados que el agente (en nuestro ejemplo, el robot) debe recorrer, por norma general se representa a través de un grafo, si bien en ciertos casos específicos utilizaremos árboles. Siguiendo con nuestro ejemplo, cada nodo del grafo representará a uno de los baldosines de la habitación, y 2 nodos van a ser lindantes si asimismo lo son sus baldosines pertinentes.

El grafo del dibujo en la parte inferior representa el tablero de forma parcial, y cada nodo es identificado por un número. Suponemos que la situación inicial del robot es el baldosín marcado con el número 1.En este grafo se aplica una correspondencia entre los nodos del mismo y los baldosines numerados de igual forma. Como se puede observar en el tablero, por servirnos de un ejemplo, el baldosín 1 es lindante al dos y al cinco, y este hecho queda plasmado en el dibujo mostrado.

Búsqueda en profundidad

Busca en profundidad

Supongamos que nuestro robot no tiene ninguna capacidad singular para poder moverse por la habitación de una forma eficaz (ignora cualquier información de utilidad para poder llegar al libro de la manera más corta): entonces va a deber proseguir un algoritmo de busca no informada (“un procedimiento ciego”) para llegar hasta él. Por norma general, esta clase de algoritmos recorre el espacio de estados de una manera específica hasta dar con la meta (en un caso así, el libro). Nuestro primer procedimiento se llama busca en profundidad.

Supongamos el árbol del dibujo representando un espacio de estados cualquiera. Vemos que, teniendo este árbol delante con sus nodos numerados, tenemos diferentes formas de recorrerlo. ¿De qué forma lo hacemos en profundidad? Siendo el 1 el nodo inicial y siete el nodo objetivo que se debe lograr, hacemos lo siguiente: vamos a buscar en todas y cada una de las ramas que cuelgan, de izquierda a derecha, y exploramos cada rama hasta llegar a una hoja. Para cada hijo procuramos por su parte en profundidad, parando cuando se halle el propósito. En este caso de ejemplo, la secuencia a continuar está indicada por el número de los nodos: 1-> dos-> tres-> cuatro-> cinco-> seis-> siete.

Si el camino tiene longitud k y factor de ramificación r, la dificultad espacial del algoritmo está en O bien (kr). Su dificultad 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 dificultad temporal está en O bien (n^p); es, por ende, un costo exponencial.

Este algoritmo de busca, además de esto, no es completo, en tanto que si existe solución y se mete por una rama infinita es posible que no concluya jamás. Tampoco es inmejorable, puesto que puede localizar la solución mas haciendo un recorrido mayor del preciso por norma general. Se ha utilizado una estructura pila LIFO para incorporarlo.

halla_objetivo_profundidad (A: espacio_de_busquedas)

Búsqueda en anchura

Busca en anchura

Otra opción para recorrer el espacio de estados sin conocer ninguna información sobre el mismo es recorrerlo en anchura. Como su nombre señala, el recorrido efectuado se hace visitando todos y cada uno de los nodos de un nivel, de izquierda a derecha, pasando más tarde al nivel siguiente, hasta el momento en que se halle el nodo objetivo, instante en el que se detiene el algoritmo. Lo vemos en el dibujo con exactamente el mismo ejemplo de ya antes, numerando los nodos con el orden que les toca conforme el recorrido en anchura.

En efecto, los nodos que con este algoritmo se visitan hasta localizar la meta (ocho) son: 1-> dos-> tres-> cuatro-> cinco-> seis-> siete-> 8

Su dificultad tanto espacial como temporal es exponencial, y está en O bien (n^p), siendo n el número medio de sucesores, y p el nivel donde se alcanza la solución; por este motivo, esta estrategia es solo aplicable a inconvenientes no demasiado extensos.

Este procedimiento es completo, en tanto que hallará siempre y en toda circunstancia una solución si la hay, mas por norma general no es perfecto. Para incorporarlo se ha hecho empleo de una cola FIFO.

halla_objetivo_anchura (A: espacio_de_busquedas)

Búsqueda en profundidad limitada

Busca en profundidad limitada

Es una variación de la busca en profundidad, donde se establece un límite de profundidad.

Búsqueda en profundidad iterativa

Busca en profundidad iterativa

Es una variación de la busca en profundidad limitada, donde la cota de profundidad escogida va incrementando si no halla una solución.

Búsqueda en costo uniforme

Busca de costo uniforme

La busca empieza por el nodo raíz y sigue visitando el próximo nodo que tiene menor costo total desde la raíz, esto es con menor costo amontonado. Se controla el amontonado, mas no se estima lo que falta (para esto habría de ser un algoritmo heurístico. Es una variación del algoritmo de Dijkstra. Asimismo es una variación de la busca en anchura donde el costo es la profuncidad del camino.

Se trata de una busca completa, si no se generan bucles. Del mismo modo, es una busca perfecta, si es función del costo.