ejercicios

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 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. 2 Explique por qué la formulación del problema debe seguir a la formulación del objetivo. ¿No?. test objetivo. Test bjeti o: Se comprueba si las regiones cercanas a él tienen el mismo color que el que tiene listo para pintar.) 3. función sucesor. también es el número de sucesores que posee un nodo.Por eje o. Escoja una formulación que sea suficiente precisa para ser implementada. 3. Función suceso : Después de pintar. Función costo: Es 1 (Se mueve de uno en uno).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? ¿Puede ser más preciso sobre qué tipos de espacios de estados siempre conducen a arboles de búsqueda finitos? (adaptados de Vender. 3. Cantidad de ramas que tiene un nodo en particular. la func n sucesor sería ir a ciudad. s un agente está en una c udad y va a otra. Función suceso : Si está a su alcance lo corta y se lo come. y función costo para cada uno de los siguientes casos. 1996. estar en ciudad. de tal modo que dos regiones adyacentes no tengan el mismo color. Es el número máximo de sucesores. se comprueba si están a su alcance. Test bjeti o: Comprobar si hay plátanos. a partir del estado inicial. Estado Inicial: El mono está en cualquier lugar del cuarto. a) Colore un mapa plano utilizando solo cuatro colores. busca las cajas ©   ¨  § ¥¦ ¥ Facto d amificación: ¤£ £ £ ¢¡  . ¿Si?. b) Un mono de tres pies de alto está en una habitación en donde algunos plátanos están suspendidos del techo de ocho pies de alto.7 Defina el estado inicial. se mueve a la siguiente región cambiando al siguiente color listo para pintar. que se realizarán antes de llegar al objetivo. esto depende del tiempo que tarde el grifo en llenar los jarrones y cuántas veces sea necesario hacer esto.10. así como el tiempo que se tarde en llegar hasta los demás jarrones y vaciarlos o traspasar el agua.3.4.10. búsqueda primero en profundidad con limite tres.6.apilables. y la búsqueda de profundidad iterativa.9.2.11.2. c) Tiene tres jarros.11          .2. Estado Inicial: Los 3 jarros están vacíos. y un grifo de agua.2. Test bjeti o: Comprobar si tiene 1 galón en los 3 jarros.9.5.11.9.5. Función suceso : si no hay 1 galón en ninguno de ellos.7 ni el 3: 1.11 ni el 0: 1 ni el 1: 1. vaciarlos o compartir el contenido.4. Función costo: Depende de dónde dejó las cajas o si las acarrea y la distancia que haya de un plátano a otro.8.3.2.7. los numero 2n y 2n +1.8.8.4.5. corta y come el plátano (Va hacia el siguiente plátano).2. Primero en profundidad: 1. 3. con capacidades 12 galones.10. P imero en anchura: 1. b) Supongamos que el estado objetivo es el 11 Enumere el orden en el que serán visitados los nodos por las búsquedas primero en anchura. las monta. llenarlos.6.3 ni el 2: 1.10. Profundidad Iterati a: 1.4.4. a) Dibuje el trozo del espacio de estados para los estados del 1 al 15.8. y tres galones.9. Usted puede llenar los jarros o vaciarlos de uno a otro o en el suelo. Tiene que obtener exactamente un galón. Función costo: Depende del tiempo.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. ocho galones. 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. 3m. 0m.0m. 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. 1) Orilla 1 mmm ccc nodo objetivo (0c. a) formule el problema de forma precisa.1/0c.0/3c.9 El problema de los misioneros y caníbales en general se forma como sigue.0) /representa el otro lado del rio Estado final: (0c. Encuentre un modo de conseguir que todos estén en el otro lado.3m.3m. 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. 0=no hay bote. Orilla 0 mmm ccc nodo inicial (3c. m=misionero. 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. 0) Simbología: c=caníbal.1968). 1=bote Estado inicial: (3c.1) "  !            !  . con un barco que puede sostener a una o dos personas.0m. Tres misioneros y tres caníbales están en un lado de un rio. sin dejar algún vez a un grupo de misioneros en un lugar excedido en numero por los caníbales. haciendo solo las distinciones necesarias para asegurar una solución válida. Dibujar un diagrama del espacio de estados completo. / 1c.3m.0m.0m0) (2c.0/1c.3m.1m.3m.1) 5 (2c.0) /representa el otro lado del rio Estado final: (0c.0m.1/2c.1/1c.3m.1m.1/1c. 0=no hay bote.0/1c. 2.3m. 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 $ # # .1) (2c.0m.b) Implemente y resuelva el problema de manera optima utilizando un algoritmo apropiado de búsqueda.1m. ¿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. se van los dos caníbales.2m.0m. 3.0/3c.3m. se van los dos misioneros y se devuelve un caníbal 5.0m.0/1c.1) (1c.0) 1 9 5 (1c.0m.3m.1/0c.1/0c. m=misionero.1/1c.1) 9 (2c. se envían 2 caníbales y uno de ellos regresa.1m.0/2c.1) 1.2m.1) 3 (0c.0/3c.1) 8 (2c.0m.3m.2m.0m.0) 9 6 2 (1c.0/3c.3m.1m.0/2c.3m.0) 10 (1c.1. un misionero lleva un caníbal y se devuelve.0m.3m.1m.0) 1 (0c.1) 3 (1c.2m.0m.1) BÚSQUEDA EN PROFUNDIDAD (3c.1/2c. 1=bote Estado inicial: (3c.3m.0m.0m.0/2c.0) 1 (1c.1) (2c.0) 7 (1c. se van dos misioneros y regresa uno con un caníbal 4.3m.0m.3m.0) 1 (0c.1) 4 (2c. se van dos caníbales y vuelve uno 6.0/3c.1) 6 (3c.3m.1/0c.3m.0/1c.0m.2m.0) 2 (2c.0/2c.3m.1/2c.0m. 2M y 0C.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. Aquí es donde empezamos.y y y Estado inicial: 3M y 3C en la izquierda. 0M y 0C en la derecha. 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. Son las posibilidades de personal que puede ir en la canoa. Estado final: 0M y 0C en la izquierda. 1M y 1C. utilizando profundidad iterativa. Muestre un espacio de estados con costos constantes en el cual la Búsqueda-Grafos. y la canoa en la izquierda. el resultado dependerá del orden en el que se prueben estas posibilidades. ¿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? . y la canoa en la derecha. 0M y 2C. encuentren una solución suboptima 3. O(n2) con otra O(n) 3. Como no busco todas las soluciones.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. Aquí es a donde queremos llegar.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. Viajes: 1M y 0C. 3M y 3C en la derecha. c) ¿Por qué cree que la gente utiliza mucho tiempo para resolver este puzle. 0M y 1C. 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. 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. Utilizado para estimar el coste de completar un viaje. 4. c) Temple simulado con T=0 en cualquier momento. .15 En este ejercicio. muestre la secuencia de nodos que considerar el algoritmo y los valores f. b) Muestre que la heurística AM domina la distancia en línea recta. exploremos el uso de los métodos de búsqueda local para resolver los pvcs del tipo definido en el Ejercicio 4. 4.h para casa nodo. Compare los resultados con solucunes optimas obtenidas con el algoritmo A* Con la Heuristica AM (Ejemrcicio 4. b) La búsqueda primero en anchura. c) Escriba un generador de problemas para ejemplos de PVC donde las ciudades están representadas por puntos aleatorios en el cuadrado unidad.11 De el nombre del algoritmo que resulta de casa uno de los casos siguientes: a) Busqueda de haz local con K=1. 4. Es decir. c) La búsqueda de coste uniforme es un saco especial de búsqueda A*. y la búsqueda de conté uniforme es un caso especial de la búsqueda primero el mejor. y Úselo con un algoritmo de búsqueda admisible para resolver los ejemplos del PVC. a) Muestre como puede obtenerse esta heurística a partir de una versión relajada del PVC.8).4. d) Algoritmo genético con tamaño de la población N=1. 4. búsqueda primero en profundidad.8.g. dado que ya se ha construido un viaje parcial.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.8 El problema del viajante de comercio (PVC) puede resolverse con la heurística del árbol mismo (AM). a) Idee una aproximación de la ascensión de colinas para resolver los PVSs. d) Encuentra un algoritmo eficiente en la literatura para construir el AM. a) Repita el Ejercito 3.16 Utilizando la ascensión de colinas. 4. en vez de hacer una búsqueda a profundidad 1 para decidir donde ir. haga una búsqueda a prob el re camino. Usando el entorno de la figura 3. ¿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. d) ¿Hay algún k para el cual este garantizado que el nuevo algoritmo se escape de mínimos locales? . Puede consultar Larrañaga et al (1999) para algunas sugerencias sobre las representaciones.17 En este ejercicio. examinaremos la ascensión de colinas en el contexto d navegación de e un robot.22 como un ejemplo. Campare los resultados a las otras aproximaciones. y luego repetir el proceso.b) idee una aproximación del algoritmo genético al problema del viajante de comercio.