ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

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

videos internet

salud  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 el propósito 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 emplean 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, normalmente 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

Búsqueda 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 continuar un algoritmo de busca no informada (“un procedimiento ciego”) para llegar hasta él. Por norma general, este género de algoritmos recorre el espacio de estados de una manera específica hasta dar con el propósito (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é manera 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 proseguir 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 consiguiente, un costo exponencial.


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


halla_objetivo_profundidad (A: espacio_de_busquedas)


Búsqueda en anchura

Búsqueda 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 realiza 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 hallar 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 esta razón, esta estrategia es solo aplicable a inconvenientes no demasiado extensos.


Este procedimiento es completo, puesto que hallará siempre y en todo momento una solución si la hay, mas por lo 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

Búsqueda 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

Búsqueda 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

Búsqueda 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, o sea 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.


Búsqueda bidireccional


Es un procedimiento en el que se efectúa simultáneamente una busca desde el estado inicial y otra busca desde el estado objetivo.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Búsquedas no informadas wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas