INTRODUCCIÓN
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.
OBJETIVO
La siguiente clase tiene como objetivo comprender las estrategias de Búsqueda no informada.
ESTRATEGIAS DE BÚSQUEDA NO INFORMADA
Esta sección trata cinco estrategias de búsqueda englobadas bajo el nombre de búsqueda no informada (llamada también búsqueda a ciegas). El término significa que ellas no tienen información adicional acerca de los estados más allá de la que proporciona la definición del problema. Todo lo que ellas pueden hacer es generar los sucesores y distinguir entre un estado objetivo de uno que no lo es.
Búsqueda en amplitud
La técnica de búsqueda primero en amplitud
La búsqueda primero en amplitud o en anchura es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, después sus sucesores, etc.
En general, se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel.
La búsqueda primero en anchura se puede implementar utilizando una estructura de tipo cola primero en entrar primero en salir, asegurándose que los nodos primeros visitados serán los primeros expandidos.
La principal desventaja de la búsqueda en anchura es los requisitos de memoria para almacenar todos los nodos que no han sido expandidos durante la búsqueda.
Continuaremos con el ejemplo del problema del agente de viajes con la misma formulación vista en la búsqueda en profundidad.
Si tenemos una estructura de datos de tipo cola para implementar esta estrategia de búsqueda:
La búsqueda primero en amplitud o en anchura es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, después sus sucesores, etc.
En general, se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel.
La búsqueda primero en anchura se puede implementar utilizando una estructura de tipo cola primero en entrar primero en salir, asegurándose que los nodos primeros visitados serán los primeros expandidos.
La principal desventaja de la búsqueda en anchura es los requisitos de memoria para almacenar todos los nodos que no han sido expandidos durante la búsqueda.
Búsqueda de costo uniforme
La búsqueda primero en anchura es óptima cuando todos los costos son iguales, porque siempre expande el nodo no expandido más superficial. Con una extensión sencilla, podemos encontrar un algoritmo que es óptimo con cualquier función costo. En vez de expandir el nodo más superficial, la búsqueda de costo uniforme expande el nodo n con el camino de costo más pequeño. Notemos que si todos los costos son iguales, es idéntico a la búsqueda primero en anchura.
La búsqueda de costo uniforme no se preocupa por el número de pasos que tiene un camino, pero sí sobre su coste total. Por lo tanto, éste se meterá en un bucle infinito si expande un nodo que tiene una acción de coste cero que conduzca de nuevo al mismo estado. Podemos garantizar completitud si el costo de cada paso es mayor o igual a alguna constante positiva pequeña e. Esta condición es también suficiente para asegurar optimización. Significa que el costo de un camino siempre aumenta cuando vamos por él. De esta propiedad, es fácil ver que el algoritmo expande nodos que incrementan el coste del camino. Por lo tanto, el primer nodo objetivo seleccionado para la expansión es la solución óptima. (Recuerde que la búsqueda en árboles aplica el test objetivo sólo a los nodos que son seleccionados para la expansión.)
Búsqueda en profundidad
Evaluación de una búsqueda
La evaluación de la eficiencia de una técnica de búsqueda esta fuera del alcance de este curso ya que puede ser muy complicada. De hecho, esta evaluación se lleva gran parte de la investigación en IA. Sin embargo, veremos dos medidas elementales que son importantes para obtener una idea de las ventajas y desventajas de utilizar una u otra técnica:
1. La rápidez con que se encuentra la solución.
2. La calidad de la solución.
Hay varios tipos de problemas para los cuales lo principal es encontrar una solución con el mínimo esfuerzo.
Para ese tipo de problemas, la primera medida es importante. Sin embargo, en otras situaciones, lo más importante es que la solución sea lo más aproximado a una solución óptima.
Tanto la longitud del camino para la solución como el número real de nodos que atraviesa, determina
la velocidad de búsqueda.
Es importante entender la diferencia entre encontrar una solución óptima y una solución buena. La diferencia radica en el hecho de que encontrar una solución óptima a menudo nos exige una búsqueda exhaustiva porque puede que sea este el único camino para determinar si hemos encontrado o no la mejor solución. No obstante, encontrar una buena solución significa encontrar una que esté inmersa en un conjunto de restricciones(sin importar si hay o no una mejor solución)
Búsqueda de profundidad limitada
Se puede aliviar el problema de árboles ilimitados aplicando la búsqueda primero en profundidad con un límite de profundidad t predeterminado. Es decir, los nodos a profundidad i se tratan como si no tuvieran ningún sucesor. A esta aproximación se le llama búsqueda de profundidad limitada. El límite de profundidad resuelve el problema del camino infinito. Lamentablemente, también introduce una fuente adicional de incompletitud si escogemos € < d, es decir, el objetivo está fuera del límite de profundidad. (Esto no es improbable cuando es desconocido.) La búsqueda de profundidad limitada también será no óptima si escogemos i > d. Su complejidad en tiempo es 0(kf) y su complejidad en espacio es 0(bí). La búsqueda primero en profundidad puede verse como un caso especial de búsqueda de profundidad limitada.
Aveces, los límites de profundidad pueden estar basados en el conocimiento del problema.
Búsqueda primero en profundidad con profundidad
iterativa
La búsqueda con profundidad iterativa (o búsqueda primero en profundidad con profundidad iterativa) es una estrategia general, usada a menudo en combinación con la búsqueda primero en profundidad, la cual encuentra el mejor límite de profundidad. Esto se hace aumentando gradualmente el límite (primero 0, después 1, después 2, etcétera) hasta que encontramos un objetivo. Esto ocurrirá cuando el límite de profundidad alcanza d, profundidad del nodo objetivo. La profundidad iterativa combina las ventajas de la búsqueda primero en profundidad y primero en anchura. En la búsqueda primero en profundidad, sus exigencias de memoria son muy modestas: La búsqueda primero en anchura, es completa cuando el factor de ramificación es finito y óptima cuando el coste del camino es una función que no disminuye con la profundidad del nodo.
Búsqueda bidireccional
La idea de la búsqueda bidireccional es ejecutar dos búsquedas simultáneas: una hacia delante desde el estado inicial y la otra hacia atrás desde el objetivo, parando cuando las dos búsquedas se encuentren en el centro. La motivación es que bd/2 + tí112 es mucho menor que tí1, o en la figura, el área de los dos círculos pequeños es menor que el área de un círculo grande centrado en el inicio y que alcance al objetivo.
La búsqueda bidireccional se implementa teniendo una o dos búsquedas que comprueban antes de ser expandido si cada nodo está en la frontera del otro árbol de búsqueda; si esto ocurre, se ha encontrado una solución. Por ejemplo, si un problema tiene una solución a profundidad d = 6, y en cada dirección se ejecuta la búsqueda primero en anchura, entonces, en el caso peor, las dos búsquedas se encuentran cuando se han expandido todos los nodos excepto uno a profundidad 3. Para b = 10, esto significa un total de 22.200 nodos generados, comparado con 11.111.100 para una búsqueda primero en anchura estándar. Verificar que un nodo pertenece al otro árbol de búsqueda se puede hacer en un tiempo constante con una tabla h a sh, así que la complejidad en tiempo de la búsqueda bidirecdonal es 0 ( tfi/2). Por lo menos uno de los árboles de búsqueda se debe mantener en memoria para que se pueda hacer la comprobación de pertenencia, de ahí que la complejidad en espacio es también OÍZ^2). Este requerimiento de espacio es la debilidad más significativa de la búsqueda bidirecdonal. El algoritmo es completo y óptimo (para costos uniformes) si las búsquedas son primero en anchura; otras combinaciones pueden sacrificar la completitud, optimización, o ambas. La reducción de complejidad en tiempo hace a la búsqueda bidireccional atractiva, pero ¿cómo busca hacia atrás? Esto no es tan fácil como suena. Sean los predecesores de un nodo n, Pred(n), todos los nodos que tienen como un sucesor a n. La búsqueda bidireccional requiere que Pred{rí) se calcule eficientemente. El caso más fácil es cuando todas las acciones en el espacio de estados son reversibles, así que Pred[rí) = Succ{rí). Otro caso puede requerir ser ingenioso.
Evitar estados repetidos
Hasta este punto, casi hemos ignorado una de las complicaciones más importantes al proceso de búsqueda: la posibilidad de perder tiempo expandiendo estados que ya han sido visitados y expandidos. Para algunos problemas, esta posibilidad nunca aparece; el espacio de estados es un árbol y hay sólo un camino a cada estado. La formulación eficiente del problema de las ocho reinas (donde cada nueva reina se coloca en la columna vacía de más a la izquierda) es eficiente en gran parte a causa de esto (cada estado se puede alcanzar sólo por un camino). Si formulamos el problema de las ocho reinas para poder colocar una reina en cualquier columna, entonces cada estado con n reinas se puede alcanzar por n\ caminos diferentes.
Para algunos problemas, la repetición de estados es inevitable. Esto incluye todos los problemas donde las acciones son reversibles, como son los problemas de búsqueda de rutas y los puzles que deslizan sus piezas. Los árboles de la búsqueda para estos problemas son infinitos, pero si podamos parte de los estados repetidos, podemos cortar el árbol de búsqueda en un tamaño finito, generando sólo la parte del árbol que atraviesa el grafo del espacio de estados. Considerando solamente el árbol de búsqueda hasta una profundidad fija, es fácil encontrar casos donde la eliminación de estados repetidos produce una reducción exponencial del coste de la búsqueda. En el caso extremo, un espacio de estados de tamaño d + 1 se convierte en un árbol con 2rf hojas Un ejemplo más realista es la rejilla rectangular como se ilustra en la Figura. Sobre una rejilla, cada estado tiene cuatro sucesores, entonces el árbol de búsqueda, incluyendo estados repetidos, tiene 4 hojas; pero hay sólo 2a* estados distintos en cada pasos desde cualquier estado. Para d = 20, significa aproximadamente un billón de nodos, pero aproximadamente 800 estados distintos. Entonces, si el algoritmo no detecta los estados repetidos, éstos pueden provocar que un problema resoluble llegue a ser irresoluble. La detección por lo general significa la comparación del nodo a expandir con aquellos que han sido ya expandidos; si se encuentra un emparejamiento, entonces el algoritmo ha descubierto dos caminos al mismo estado y puede desechar uno de ellos.
Para la búsqueda primero en profundidad, los únicos nodos en memoria son aquellos del camino desde la raíz hasta el nodo actual. La comparación de estos nodos permite al algoritmo descubrir los caminos que forman ciclos y que pueden eliminarse inmediatamente. Esto está bien para asegurar que espacios de estados finitos no hagan árboles de búsqueda infinitos debido a los ciclos; lamentablemente, esto no evita la proliferación exponencial de caminos que no forman ciclos, en problemas como los de la Figura. El único modo de evitar éstos es guardar más nodos en la memoria. Hay una compensación fundamental entre el espacio y el tiempo. Los algoritmos que olvidan su historia están condenados a repetirla.
Problema:
El mismo estado puede repetirse varias veces en el árbol de búsqueda
Puede generarse el mismo subárbol varias veces
Soluciones:
Ignorarlo
Evitar ciclos simples:
No añadir el padre de un nodo al conjunto de sucesores
Evitar ciclos generales:
Np añadir un antecesor de un nodo al conjunto de sucesores
Evitar todos los estados repetidos:
No añadir ningún nodo existente en el árbol al conjunto de sucesores
CONCLUSIÓN
Las estrategias de búsquedas vistas en esta unidad nos dan una idea de cómo los investigadores en IA proponen diferentes formas de solución para los problemas. Estas técnicas son clásicas de la IA y es por ello que deben ser conocidas por todos aquellos que están relacionados con programación de soluciones por computadora. Estas técnicas son clásicas de la IA y es por ello que deben ser conocidas por todos aquellos que están relacionados con programación de soluciones por computadora. Todos ellos requieren de una mayor complejidad de computación y mayor conocimiento e información del problema. En la mayoría de las estrategias contempladas en el cápitulo, debe utilizarse médios para evitar estados repetidos, de esta forma se ahorrara espacio de almacenamiento y tiempo de recorrido. Los algoritmos que olvidan su historia están condenados a repetirla.
El mundo real es más complejo de lo que se formula en los problemas para solucionar por computadora, sin embargo asumimos que los seres humanos para encontrar soluciones tampoco requieren de mucha información, o al menos no requiere conocer todo el universo para encontrar soluciones buenas. Por ejemplo, no requerimos de mucha información, ni de mucho tiempo para seleccionar una botella de refresco que compramos en el supermercado. Esto justifica en parte lo que hacemos cuando reducimos nuestro problema. Aún cuando por su simplicidad sean problemas de juguete.
Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.
Universidad de Castilla - La Mancha 2010, Búsqueda no informada. (En línea). EC. Consultado, 15 de Octubre. 2014. Formato PDF. Disponible en: http://www.sanchezcrespo.org/Docencia/IA/IA%20-%20Tema%203B%20-%20Busquedas%20v1.3.pdf
García D 2009. Búsqueda no informada. (En línea). EC. Consultado, 15 de Octubre. 2014. Formato PDF. Disponible en: http://www.unistmo.edu.mx/~daniel.garcia/unidadiii_ia.pdf
Hermoso, R y Vasirani, M. 2012. Búsqueda no informada. (En línea). EC. Consultado, 15 de Octubre. 2014. Formato PDF. Disponible en: http://www.ia.urjc.es/cms/sites/default/files/userfiles/file/ia4/2011/IA4_%5BBusq_No_Inf%5D.pdf
No hay comentarios.:
Publicar un comentario