Ejercicios

Transcript

3.1 Defina con sus propias palabras los siguientes términos: Estado: en el que comienza el agente Es toda aquella posibilidad de estado, si es un problema de agente viajero, pues es cuando el viajero está en alguna ciudad. Espacio de estados: Es la totalidad de estados en los que puede estar. Si es el problema viajero es cada una de las ciudades. Conjunto de todos los estados alcanzables desde el estado inicial. Implícitamente el espacio inicial y la función sucesor definen el espacio de estados del problema (conjunto de todos los estados alcanzables desde el estado inicial). El espacio de estado forma un grafo el cual los nodos son estados y los arcos entre nodos son acciones. Árbol de búsqueda: Es el Espacio de Estados generado al expandir las funciones sucesores de cada nodo de búsqueda. el objetivo es atravesar el árbol partiendo de un estado inicial hasta un estado objetivo, explicito generado por el estado inicial y la función sucesor, definiendo así el espacio de estado, en general se tiene un grafo de búsqueda más que un árbol, cuando el mismo estado puede alcanzarse desde varios caminos. Nodo de búsqueda: Es cada una de las paradas o estaciones o resultados que existen en los árboles árboles de búsqueda, prácticamente es cada estado posible representado en un Árbol de Búsqueda. Objetivo: Es el estado final de la búsqueda. Encontrar un camino que conecte al nodo inicial a un nodo objetivo. Es el estado que se quiere alcanzar partiendo desde un nodo inicial. Acción: Una descripción de las posibles acciones disponible por el agente. Utilizando una función sucesor. Es la función que el agente debe hacer, ya sea moverse, buscar, limpiar. Es lo que lo acerca (o en algunos casos, aleja) del objetivo. Función sucesor: Cada sucesor es un estado que puede alcanzarse aplicando la acción. Por eje o, s un agente está en una c udad y va a otra, la func n sucesor se ría ir a ciudad, estar en ciudad.     ¡ Facto ¥   d ¦ £  ¢  ¥   £  £ ¤   amifi cación: Cantidad de ramas que tiene un nodo en parti cular, también es el número de sucesores que posee un nodo. Es el número máximo de sucesores, a partir del estado inicial, que se realizarán antes de llegar al ob jetivo. 3.2 Explique por qué la formulación del problema debe seguir a la formulación del ob jetivo. 3.6 ¿Conduce siempre un espacio de estados finito a un árbol de búsqueda finito? ¿Cómo un espacio de estados finito es un árbol? ¿Pued e ser más preciso sobre qu é tipos de espacios de estados si empre conducen a arboles de búsqueda finitos? (adaptados d e V ender, 1996.) 3.7 Defina el estado inicial, test ob jetivo, función sucesor, y función costo para cada uno de los siguientes casos. Esco ja una formulación que sea suficiente precisa para ser implementada. a) Colore un mapa plano utilizando solo cuatro colores, de tal modo que dos r egiones adyacentes no tengan el mismo color. Test bjeti o: Se compru eba si la s regiones cercana s a él tienen el mismo color que el que tiene listo para pintar. Función suceso : Despu és de pintar, se mueve a la siguiente región cambiando al siguiente color listo para pintar. Función costo: Es 1 (Se mueve de uno en uno). ¨   §    ©   b) Un mono d e tres pies de alto está en una habitación en donde algunos plátanos están suspendidos del techo de ocho pies de alto. Estado El mono Inicial: está en cualquier lugar del cuarto. bjeti o: Comprobar si hay plátanos, ¿Si?, se comprueba si están a su alcance. Test Función suceso : Si está a su alcance lo corta y se lo come. ¿No?, busca las ca jas           apilables, las monta, corta y come el plátano (Va hacia el siguiente plátano). Función costo: Depend e d e dónd e dejó las ca jas o si las acarrea y la distancia que haya de un plátano a otro. c) Tien e tres jarros, con capacidades 1 2 galon es, o cho galones, y tres galones, y un grifo de agua. Usted puede llenar los jarros o va ciarlos de uno a otro o en el suelo. Tiene que obten er exactamente un galón. Estado Inicial: Test Los 3 jarros están vacíos. bjeti o: Comprobar si tiene 1 galón en los 3 jarros. Función suce so : si no hay 1 galón en ninguno de ellos, llenarlos, vaciarlos o compartir el contenido. Función costo: Depend e d el tiempo, esto d epend e del tiempo que tard e el grifo en llenar los jarrones y cuántas veces sea n ecesario hacer esto, así como el tiempo que se tard e en llegar hasta los demás jarrones y vaciarlos o traspasar el agua.           3.8 considere un espacio de estados donde el estado comienzo es el numero 1 y la función sucesor para el estado n devuelve 2 estados, los numero 2n y 2n +1. a) Dibu je el trozo del espacio de estados para los estados del 1 al 15. b) Supongamos que el estado ob jetivo es el 11 Enumere el orden en el que serán visitados los nodos por las búsqu edas primero en anchura, búsqu eda primero en profundidad con limite tres, y la búsqueda de profundidad iterativa. P imero en anchura: 1,2,3,4,5,6,7,8,9,10,11. Primero en profundidad: 1,2,4,8,9,5,10,11. Profundidad Iterati a:1,2,4,8,9,5,10,11 ni el 0 : 1 ni el 1: 1,2,3 ni el 2: 1,2,4,3,6,7 ni el 3: 1,2,4,8,9,10,11                   c) ¿será apropiada la búsqueda bidireccional para este problema? Si Comenzaría la búsqueda en profundidad por un lado y por el otro la que empieza de arriba hacia abajo iría: 1 2 3 4 5 8 9 10 11; mientras que la que va de abajo hacia arriba iría de: 11 5 2 1                           d) ¿Qué es el factor de ramificación en cada dirección de la búsqueda bidireccional? Es el número de nodos hijos que genera el algoritmo de búsqueda bidireccional en cada una de sus ramas Son 3 para el que inicia de arriba hacia abajo de igual manera el que va en orden contrario ya que ambos se encuentran en el nivel más bajo del árbol de búsqueda   !  !    e) ¿La respuesta (c) sugiere una nueva formulación del problema que permitiría resolver el problema de salir del estado 1 para conseguir un estado objetivo dado, con casi ninguna búsqueda? Sí sugiere una nueva formulizacion del problema por el camino recorrido desde el nodo inicio al nodo objetivo por concluir un camino mas corto "  3.9 El problema de los misioneros y caníbales en general se forma como sigue. Tres misioneros y tres caníbales están en un lado de un rio, con un barco que puede sostener a una o dos personas. Encuentre un modo de conseguir que todos estén en el otro lado, sin dejar algún vez a un grupo de misioneros en un lugar excedido en numero por los caníbales. Este problema es famoso en IA por que fue el tema del primer trabajo que aproximo una formulación de problema de un punto de vita analítico (Amarel,19 68). a) formule el problema de forma precisa, haciendo solo las distinciones necesarias para asegurar una solución válida. Dibujar un diagrama del espacio de estados completo. Orilla 0 Orilla 1 mmm ccc mmm ccc nodo inicial (3c, 3m, 1) nodo objetivo (0c, 0m, 0) Simbología: c=caníbal, m=misionero, 0=no hay bote, 1=bote Estado inicial: (3c,3m,1/0c,0m,0) /representa el otro lado del rio Estado final: (0c,0m,0/3c,3m,1) b) Implemente y resuelva el problema de manera optima utilizando un algoritmo apropiado de búsqueda. ¿Es una buena idea comprobar los estados repetidos? No es una buena idea comprobar los espacios repetidos por que se extenderá el problema En la búsqueda preferente por profundidad siempre se expande uno de los nodos que se encuentre en los más profundo de árbol por lo tanto los nodos sucesores estarán a profundidades cada vez mayores #  $  #  Simbología: c=caníbal, m=misionero, 0=no hay bote, 1=bote Estado inicial: (3c,3m,1/0c,0m,0) /representa el otro lado del rio Estado final: (0c,0m,0/3c,3m,1) BÚSQUEDA EN PROFUNDIDAD (3c,3m,1/0c,0m,0) 1 5 (1c,3m,0/2c,0m,1) (2c,2m,0/1c,1m,1) 9 (2c,3m,1/1c,0m,0) 1 (0c,3m,0/3c,0m,1) 5 (2c,3m,0/1c,1m,1) 9 6 (1c,3m,1/2c,0m0) (2c,3m,1,/ 1c,0m,0) 2 (1c,1m,0/2c,2m,1) 8 7 (2c,2m,1/1c,1m,0) (1c,3m,1/2c,0m,0) 2 (2c,0m,0/1c,3m,1) (1c,1m,0/2c,2m,1) 3 6 (3c,0m,1/0c,3m,0) 1 4 (1c,0m,0/2c,3m,1) 9 (2c,0m,0/1c,3m,1) 10 (2c,0m,1/1c,3m,0) 1 (1c,1m,1/2c,2m,0) 3 (0c,0m,0/3c,3m,1) (0c,0m,0/3c,3m,1) 1. un misionero lleva un caníbal y se devuelve. 2. se envían 2 caníbales y uno de ellos regresa. 3. se van dos misioneros y regresa uno con un caníbal 4. se van los dos misioneros y se devuelve un caníbal 5. se van dos caníbales y vuelve uno 6. se van los dos caníbales. y y y y y y y y y y y y M:3 C:3 \___/ ~~~~~~~~ M:0 C:0 M:2 C:2 ~~~~~~~~ \___/ M:1 C:1 M:3 C:2 \___/ ~~~~~~~~ M:0 C:1 M:3 C:0 ~~~~~~~~ \___/ M:0 C:3 M:3 C:1 \___/ ~~~~~~~~ M:0 C: 2 M:1 C:1 ~~~~~~~~ \___/ M:2 C: 2 M:2 C:2 \___/ ~~~~~~~~ M:1 C:1 M:0 C:2 ~~~~~~~~ \___/ M:3 C:1 M:0 C:3 \___/ ~~~~~~~~ M:3 C:0 M:0 C:1 ~~~~~~~~ \___/ M:3 C: 2 M:1 C:1 \___/ ~~~~~~~~ M:2 C: 2 M:0 C:0 ~~~~~~~~ \___/ M:3 C:3 y y y Estado inicial: 3M y 3C en la izquierda, 0M y 0C en la derecha, y la canoa en la izquierda. Aquí es donde empezamos. Estado final: 0M y 0C en la izquierda, 3M y 3C en la derecha, y la canoa en la derecha. Aquí es a donde queremos llegar. Viajes: 1M y 0C, 0M y 1C, 1M y 1C, 2M y 0C, 0M y 2C. Son las posibilidades de personal que puede ir en la canoa. Como no busco todas las soluciones, el resultado dependerá del orden en el que se prueben estas posibilidades. c) ¿Por qué cree que la gente utiliza mucho tiempo para resolver este puzle, dado que el espacio de estados es tan simple? Nos cuesta resolver el puzle a la primera porque no somos capaces de pensar diferente si no que pensamos de una forma más ambigua 3.12 Demuestre que la búsqueda de costo uniforme y la búsqueda primero en anchura con costos constantes son óptimas cuando se utiliza con el algoritmo de Búsqueda-Grafos. Muestre un espacio de estados con costos constantes en el cual la Búsqueda-Grafos, utilizando profundidad iterativa, encuentren una solución suboptima 3.13 Describa un espacio de estados en el cual la búsqueda de profundidad iterativa funciones mucho peor que la búsqueda primero en profundidad (por Ejemplo, O(n2) con otra O(n) 3.14 Escriba un programa que tome como entrada dos URLs de páginas web y encuentre un camino de links de una a la otra. ¿Cuál es una estrategia apropiada de búsqueda? ¿La búsqueda bidireccional es una idea buena? ¿Podría usarse un motor de búsqueda para implementar una función predecesor? 4.1 trace como opera la búsqueda A* aplicada la problema de alcanzar Bucarest desde luego utilizando la heurística distancia en línea recta. Es decir, muestre la secuencia de nodos que considerar el algoritmo y los valores f,g,h para casa nodo. 4.3 Demuestre cada una de las declaraciones siguientes: a) La búsqueda primero en anchura es un caso especial de la búsqueda de coste uniforme. b) La búsqueda primero en anchura, búsqueda primero en profundidad, y la búsqueda de conté uniforme es un caso especial de la búsqueda primero el mejor. c) La búsqueda de coste uniforme es un saco especial de búsqueda A*. 4.8 El problema del viajante de comercio (PVC) puede resolverse con la heurística del árbol mismo (AM). Utilizado para estimar el coste de completar un viaje, dado que ya se ha construido un viaje parcial. El coste de AM del Conjunto de ciudades es la suma mas pequeña de los costos de los arcos de cualquier árbol que une todas las ciudades. a) Muestre como puede obtenerse esta heurística a partir de una versión relajada del P VC. b) Muestre que la heurística AM domina la distancia en línea recta. c) Escriba un generador de problemas para ejemplos de PVC donde las ciudades están representadas por puntos aleatorios en el cuadrado unidad. d) Encuentra un algoritmo eficiente en la literatura para construir el A M, y Úselo con un algoritmo de búsqueda admisible para resolver los ejemplos del P VC. 4.11 De el nombre del algoritmo que resulta de casa uno de los casos siguientes: a) Busqueda de haz local con K=1. c) Temple simulado con T=0 en cualquier momento. d) Algoritmo genético con tamaño de la población N=1. 4.15 En este ejercicio, exploremos el uso de los métodos de búsqueda local para resolver los pvcs del tipo definido en el Ejercicio 4. 8. a) Idee una aproximación de la ascensión de colinas para resolver los P VSs. Compare los resultados con solucunes optimas obtenidas con el algoritmo A* Con la Heuristica A M (Ejemrcicio 4.8). b) idee una aproximación del algoritmo genético al problema del viajante de comercio. Campare los resultados a las otras aproximaciones. Puede consultar Larrañaga et al (1999) para algunas sugerencias sobre las representaciones. 4.17 En este ejercicio, examinaremos la ascensión de colinas en el contexto de navegación de un robot, Usando el entorno de la figura 3. 22 como un ejemplo. a) Repita el Ejercito 3.16 Utilizando la ascensión de colinas. ¿Cae alguna vea su agente en un mínimo local? ¿Es posible con obstáculos Convexos? c) Modifique el algoritmo de ascensión de colinas de modo que, en vez de hacer una búsqueda a profundidad 1 para decidir donde ir, haga una búsqueda a probre el camino, y luego repetir el proceso. d) ¿Hay algún k para el cual este garantizado que el nuevo algoritmo se escape de mínimos locales?