BUSQUEDA PRIMERO EN PROFUNDIDAD

BÚSQUEDA PRIMERO EN PROFUNDIDAD O BÚSQUEDA CON VUELTA ATRÁS


 

Esta estrategia intenta seguir un camino hasta la mayor profundidad posible, retrocediendo cuando acaba el camino y retomando la última posibilidad de elección disponible.

El principal problema de este algoritmo es que no acaba si existe la posibilidad de que hayan caminos infinitos. Una variante de este algoritmo que evita este problema es el algoritmo de profundidad limitada (Búsqueda en profundidad prioritaria), éste impone un límite máximo de profundidad que determina la longitud máxima de los caminos recorridos. Esta limitación garantiza que el algoritmo acaba, pero no garantiza encontrar la solución, ya que ésta puede estar a mayor profundidad que el límite impuesto. (UNIVERSIDAD POLITÉCNICA DE CATALUNYA, 2013)

Este método sólo genera un sucesor del nodo en cada paso y cada nodo llevará  una marca que indique qué operadores se pueden utilizar especificando el orden de aplicación, hasta llegar a una profundidad límite. Lo que se busca con esta profundidad límite es no realizar una búsqueda innecesaria; es decir desecha los las partes del grafo donde el nodo objetivo este muy lejano al nodo inicial.

Los nodos están ordenados según su profundidad, en orden creciente: los más profundos al principio, los menos profundos al final, conviertiendose en una PILA: los datos que primero entran son los últimos en salir. (Rubio et al. 1998)

Al igual que sucedía en la búsqueda en anchura, los nodos de igual profundidad se ordenan arbitrariamente, según el orden de las reglas u operadores.

Entonces este método también se lo conoce como vuelta atrás (cronológica) porque se establece la profundidad y al llegar al nodo límite sin alcanzar el nodo objetivo habría que regresar al nodo inmediatamente superior (el nodo límite ya revisado se lo debe desechar porque es obvio que no se pueden crear más sucesiones de él) y volver a realizar una búsqueda en este nodo y como este vendría a ser el nodo límite-1 podemos desprender otro nodo (último) y si en ésta parte del grafo tampoco se encuentra se realiza el mismo procedimiento anteriormente mencionado.

Figura 2. Generación de los primeros nodos en la búsqueda  primero en profundidad Autor: Nils, J. (2001)

La Búsqueda en profundidad iterativa lo que se hace es repetir sucesivamente el algoritmo de profundidad limitada, aumentando a cada iteración la profundidad máxima a la que le permitimos llegar. Este algoritmo obtendría el mismo efecto que el recorrido en anchura en cada iteración, ya que a cada paso recorremos un nivel más del espacio de búsqueda. (UNIVERSIDAD POLITÉCNICA DE CATALUNYA, 2013)

La ventaja de este proceso (Búsqueda en profundidad) es que el coste en memoria crece de forma lineal. La contraparte de esta estrategia es que el ir del límite hacia el inicio no asegura que la solución encontrada sea la óptima (más cercana o de menor profundidad) o el hecho de revisar varias partes del grafo que se encuentren lejanas, pudiendo estar cerca la solución.

BIBLIOGRAFÍA

Nils J. Nilsson. 2001. INTELIGENCIA ARTIFICIAL. Una nueva síntesis.  ISBN: 1-55860-467-7.  1era ed. Copyright MCMXCVIII by Morgan Kaufmann Publishers, Inc.

Bibliografía Complementaria

UNIVERSIDAD POLITÉCNICA DE CATALUNYA, 2013. Departament de Llenguatges i Sistemes Informátics. APUNTS D’INTEL.LIGE`NCIA ARTIFICIAL. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/ia/material/teoria/ApuntesIA.pdf

Rubio, J; Muro, P. y Bañares, J. 1998. Inteligencia Artificial e Ingeniería del Conocimiento I. BÚSQUEDA. Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza. Curso 96-97. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/iia/iabusq.pdf

BUSQUEDA PRIMERO EN ANCHURA

BÚSQUEDA PRIMERO EN ANCHURA

 

Se convierte en una cola (o fila de espera) que expande primero el nodo raíz, posteriormente todos los sucesores del nodo raíz, después sus sucesores, etc., expandiendo todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel (Russell y Norvig. 2004).

Los nodos de igual profundidad se ordenan arbitrariamente. Ese orden arbitrario es directamente heredado del que exista entre los operadores del sistema de producción. Mediante esta estrategia, el árbol de búsqueda se va generando por niveles de profundidad. Hasta que todos los nodos de un nivel no han sido revisados no se revisa ninguno del siguiente nivel (Rubio et al. 1998); es decir, cuando todos sus predecesores y sus hermanos anteriores en orden de generación ya se han visitado. (UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013)  

Las búsquedas a ciegas aplican los operadores (modelos de los efectos de las acciones, que al aplicarlos crean nodos sucesores) sin conocer bien el problema. La búsqueda por anchura es el método más simple de búsquedas a ciegas.  Este procedimiento actúa de forma uniforme construyendo un grafo de estados explícito desde el nodo inicial a cada uno de los predecesores con la propiedad de que una vez encontrado el nodo objetivo, se habrá encontrado el camino más corto, pero para esto tiene que almacenar el árbol completo y esto es un inconveniente puesto que el tamaño crece de manera exponencial respecto a la profundidad del nodo objetivo (menos profundo) (Nils, J. 2001)

Russell y Norvig (2004) puntualiza el siguiente punto que se debe considerar antes de elegir un método de búsqueda:

-          La cantidad de tiempo y memoria que utiliza para completar una búsqueda.

-          Son un problema más grande los requisitos de memoria para realizar una búsqueda por anchura que el tiempo de ejecución. Pero existen otras estrategias que requieren menos memoria.

-          Los problemas de búsqueda de complejidad exponencial no pueden resolverse por métodos a ciegas (sin información) salvo los casos pequeños.

A continuación se expresa el método de búsqueda primero en anchura utilizando un puzzle de 8 piezas, en el que se muestra el nodo inicial y el nodo objetivo, así mismo el orden como se genera un árbol de búsqueda mediante el uso de los operadores (mover la celda vacía a la izquierda, arriba, a la derecha y abajo) y la solución óptima para llegar al objetivo.   

Figura 1. Búsqueda primero en anchura para un puzzle de ocho piezas

Autor: Nils, J. (2001)

Si un estado objetivo es alcanzable, la búsqueda en anchura lo encuentra. La demostración es sencilla: el estado objetivo aparecerá en un cierto nivel de profundidad y, en un número finito de pasos (suponiendo un número finito de operadores y un número finito de posibles aplicaciones de un operador sobre un estado), llegará a ese nivel. Este mismo razonamiento muestra que la búsqueda en anchura siempre encuentra la secuencia solución más corta (una de las que tienen el mínimo número de aristas). Pero esto no significa en absoluto que realice un número pequeño de operaciones. Se trata de una propiedad de la secuencia solución encontrada, no del proceso por el que ha sido construida; de hecho, la búsqueda en anchura puede llegar a ser extremadamente ineficaz. (Rubio et al. 1998)

BIBLIOGRAFÍA

Nils J. Nilsson. 2001. INTELIGENCIA ARTIFICIAL. Una nueva síntesis.  ISBN: 1-55860-467-7.  1era ed. Copyright MCMXCVIII by Morgan Kaufmann Publishers, Inc.

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Bibliografía Complementaria

UNIVERSIDAD POLITÉCNICA DE CATALUNYA, 2013. Departament de Llenguatges i Sistemes Informátics. APUNTS D’INTEL.LIGE`NCIA ARTIFICIAL. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/ia/material/teoria/ApuntesIA.pdf

Rubio, J; Muro, P. y Bañares, J. 1998. Inteligencia Artificial e Ingeniería del Conocimiento I. BÚSQUEDA. Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza. Curso 96-97. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/iia/iabusq.pdf

ESTRATEGIAS DE BUSQUEDAS

INTRODUCCIÓN

Problemas en el mundo real existen (y muchos), así mismo existen soluciones para estos, pero no todas nos llevan a esta esperada solución con la misma eficiencia. Es por esto que se hace necesario conocer las técnicas de resolución, abstraer sus características más significativas para poder decidir cuál es la adecuada frente a cada problema.  

En este caso se desea dar solución a problemas de búsqueda en inteligencia artificial, para esto existen técnicas heurísticas (cuando se dispone de información) y técnicas a ciegas (o no informadas, cuando apenas se tiene la descripción del problema).

Los temas propuestos y la explicación de la docente se orientan a que el estudiante comprenda el funcionamiento básico de las técnicas de búsqueda para luego tener la capacidad de aplicarlos en problemas del mundo real, identificando el método de búsqueda adecuado para la resolución de problemas, dependiendo si se tiene o no información.  

MARCO TEÓRICO

Un problema de búsqueda en Inteligencia Artificial tiene algoritmos que trabajan con estructuras de datos llamadas nodos que contienen en particular información sobre un estado. Un problema de búsqueda consta de:

-          Un espacio de estados, que es el conjunto de estados factibles para un problema junto a la estructura de adyacencia definida implícitamente por los operadores o reglas. (Rubio et al. 1998)

-          Un conjunto de operadores (acciones, con costes). La finalidad de una secuencia de operadores es transformar el estado inicial en el estado objetivo.

-          Un estado inicial (punto de partida de la búsqueda).

-          Una función objetivo (comprueba si el estado actual corresponde a una solución del problema). La solución consiste en una secuencia de operadores que transforman el estado inicial en el estado objetivo. (Rubio et al. 1998)

La búsqueda la realiza un programa (o agente). El espacio de búsqueda será un grafo dirigido en el que cada nodo representa un posible estado del sistema. Dependiendo del problema, cada nodo incluirá una descripción completa del sistema, o bien sólo las modificaciones necesarias para pasar de un nodo padre a su hijo. (Berzal, F. s.f.)

Debido a que la búsqueda es el núcleo de muchos procesos inteligentes, es necesario escoger la estructura de control apropiada con el fin de que el proceso de búsqueda sea eficiente. La inteligencia artificial proporciona varias técnicas de búsqueda que tienen una formulación matemática, la cual hace posible su implementación computacional bajo el esquema de programación estructurada. (Molina et al. 2008)

Rubio et al (1998) indican las restricciones sobre las secuencias solución:

-          Encontrar la secuencia más corta.

-          Encontrar la secuencia menos costosa (en este caso se supondrá que los disparos de las reglas tienen asociado un coste o, equivalentemente, que el espacio de estados tiene pesos en las aristas).

-          Encontrar cualquier secuencia lo más rápido posible.

Al evaluar una estrategia habrá que tener en cuenta lo siguiente:

Tiempo de cálculo <==> Calidad de la solución.

Un punto muy importante que señalan estos autores es que todos los problemas de búsqueda requieren no sólo que se encuentre un camino solución, sino todos los que existan (probablemente para poder aplicar estrategias, por ejemplo en un juego de ajedrez).

Existen diversos métodos de realizar búsquedas, a continuación se muestran dos grandes grupos que son búsqueda informada o heurística y la búsqueda a ciegas o no informada.

HEURÍSTICAS

Las heurísticas son criterios, métodos o principios para decidir cuál de entre varias acciones promete ser la mejor para alcanzar una determinada meta. (Berzal, F. s.f.)

Es el tipo de estrategia que sabe si un estado no objetivo es más prometedor que otro, permitiendo reducir la búsqueda (Russell y Norvig. 2004); es decir, como disponen de alguna información sobre la proximidad de cada estado a un estado objetivo, se pueden explorar en primer lugar los caminos más prometedores. (Rubio et al. 1998)

Según Rubio et al (1998), los métodos heurísticos son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial.

BÚSQUEDA NO INFORMADA O BÚSQUEDA A CIEGAS

Engloba las estrategias de búsqueda que no cuentan con información adicional sobre los estados, aparte de la definición del problema. Estas sólo pueden generar los sucesores y distinguir entre un estado objetivo de un estado no objetivo. Las estrategias que saben que un estado no objetivo es más prometedor que otros se llaman por lo contrario búsqueda informada o búsqueda heurística. Sin embargo, todas las estrategias se distinguen por el orden de expansión de los nodos (Russell y Norvig. 2004).

A continuación se muestran dos métodos de búsqueda no informada:

- Búsqueda Primero en Anchura 
- Búsqueda Primero en Profundidad

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Bibliografía Complementaria

Berzal, F. s.f. Búsqueda en Inteligencia Artificial. DECSAI (Departamento de Ciencias de la Computación e I.A.). Universidad de Granada. Formato (PDF). Disponible en: http://elvex.ugr.es/decsai/iaio/slides/A3%20Search.pdf

Molina, J.; Torres, C. y Restrepo, C. 2008. TÉCNICAS DE INTELIGENCIA ARTIFICIAL PARA LA SOLUCIÓN DE LABERINTOS DE ESTRUCTURA DESCONOCIDA. Scientia et Technica Año XIV, No 39. Universidad Tecnológica de Pereira. ISSN 0122-1701. Formato (PDF). Disponible en: http://revistas.utp.edu.co/index.php/revistaciencia/article/viewFile/3171/1933

Rubio, J; Muro, P. y Bañares, J. 1998. Inteligencia Artificial e Ingeniería del Conocimiento I. BÚSQUEDA. Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza. Curso 96-97. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/iia/iabusq.pdf

PRESENTACION

ESCUELA SUPERIOR POLITÉCNICA AGROPECUARIA DE MANABÍ MANUEL FÉLIX LÓPEZ

CARRERA: INGENIERÍA INFORMÁTICA

INTELIGENCIA ARTIFICIAL

TEMA:

ESTRATEGIAS DE BÚSQUEDA NO INFORMADA:

BÚSQUEDA PRIMERO EN ANCHURA

BÚSQUEDA PRIMERO EN PROFUNDIDAD

AUTORA:

MENDOZA MARCILLO ENA KATHERINE

CATEDRÁTICO:

ING. HIRAIDA SANTANA

MISIÓN

Formación de profesionales íntegros que conjuguen ciencia, tecnología y valores en su accionar, comprometidos con la sociedad en el manejo adecuado de programas y herramientas computacionales de última generación.

VISIÓN

Ser referente en la formación de profesionales de prestigio en el desarrollo de aplicaciones informáticas y soluciones de hardware.

CALCETA, OCTUBRE 2014

SILABO DE INTELIGENCIA ARTIFICIAL