« Búsquedas Informadas… « || Inicio || » Búsquedas Locales »

Ejercicios de Búsqueda Informada

Última modificación: 30 de Septiembre de 2016, y ha tenido 823 vistas

Etiquetas utilizadas: || || ||

These icons link to social bookmarking sites where readers can share and discover new web pages.
  • BarraPunto
  • Del.icio.us
  • Digg
  • email
  • Facebook
  • Google
  • LinkedIn
  • PDF
  • Reddit
  • Slashdot
  • Twitter

Realiza los mismos ejercicios que se propusieron para búsquedas ciegas pero aplicando el algoritmo A* visto en clase. Intenta utilizar diferentes funciones de heurística para cada ejercicio, de forma que puedas realizar comparativas de qué heurística funciona mejor.

Además, se proponen los siguientes ejercicios:

  1. Realiza en NetLogo un modelo para resolver de la forma más general que se te ocurra (haciendo uso de agentes) problemas de búsqueda por medio del algoritmo voraz.
  2. Pon ejemplos de búsquedas en las que al aplicar el algoritmo voraz no encontremos una solución óptima. 
  3. Dados cuatro números naturales \(n\), \(m\), \(r\) y \(T\), encontrar una secuencia mínima de operaciones aritméticas básicas (suma, resta, multiplicación y división) que usando \(n\) y \(m\) únicamente y partiendo de \(0\), obtenga como resultado \(T\), con la restricción adicional de que ni \(n\) ni \(m\) se pueden usar más de \(r\) veces. Por ejemplo, si \(n = 2\), \(m = 3\), \(r = 3\) y \(T = 28\), una posible solución (no necesariamente mínima) es \(((((((0 + 3) × 3) × 2) − 3) × 2) − 2)\), ya que el resultado es \(28\) y ni \(2\) ni \(3\) se han usado más de tres veces cada uno.
  4. Cruce del puente: Un grupo de \(5\) personas quiere cruzar un viejo y estrecho puente. Es una noche cerrada y se necesita llevar una linterna para cruzar. El grupo sólo dispone de una linterna, a la que le quedan \(5\) minutos de batería.Cada persona tarda en cruzar \(10\), \(30\), \(60\), \(80\) y \(120\) segundos, respectivamente. El puente sólo resiste un máximo de \(2\) personas cruzando a la vez, y cuando cruzan dos personas juntas caminan a la velocidad del más lento. No se puede lanzar la linterna de un extremo a otro del puente, así que cada vez que crucen dos personas, alguien tiene que volver a cruzar hacia atrás con la linterna a buscar a los compañeros que falten, y así hasta que hayan cruzado todos.
  5. Problema de las bolsas: Se pretende encontrar una manera de distribuir un conjunto de objetos, \(O=\{o_1,\dots,o_n\}\), en bolsas, usando el menor númer posible de bolsas. Cada objeto tiene un peso asociado, \(Peso(o_i)=p_i\), y las bolsas tienen un límite de peso soportado, \(B\). Exprésalo como un problema de búsqueda en un espacio de estados adecuado, y adapta el modelo A* visto en clase para resolver instancias concretas del problema de una forma efectiva.
  6. Caminos en grafos: Considerando un grafo geométrico, diseña diversas estrategias para calcular el camino más corto entre dos nodos del grafo por medio del algoritmo A*.
  7. Dado un conjunto de enteros \(I=\{i_1,\dots,i_n\}\), el problema que queermos resolver es el de encontrar un subconjunto \(S\subseteq I\) que sume \(0\). Para ello: a) Formula el problema como una búsqueda en un espacio de estados, que tendrás que explicitar. b) Adapta el modelo visto en clase para resolver instancias concretas de este problema de forma efectiva.
  8. El juego de las Ranas: Tenemos 3 ranas negras y 3 verdes situadas encima de 7 nenúfares tal y como muestra el diagrama: N N N V V V O, donde O es el nenufar vacío. El objetivo consiste en llegar a la configuración final V V V O N N N. Para ello, los movimientos permitidos son los siguientes: a) Una rana puede moverse a un nenúfar adyacente vací, con coste 1. b) Una rana puede desplazarse a un nenúfar vacío saltando a una rana como máximo, con un coste igual a 2. Expresa este problema como un problema de búsqueda adecuado y resuélvelo de forma efectiva a partir del modelo A* visto en clase.
  9. Juego de las Cifras (Cifras y Letras): Dados \(6\) números, y un objetivo \(O\), encontrar la combinación aritmética entre ellos que se aproxima lo más posible a \(O\). Expresa este problema como un problema de búsqueda en una espacio de estados explicitado, e impleméntalo en el modelo A* que s eha visto en clase.
  10. Resuelve el siguiente juego por medio de un algoritmo A*: Trabajaremos con números de 3 cifras (de \(100\) a \(999\)). Inicialmente, tenemos dos números prefijados, que denotaremos por \(S\) (Start) y \(G\) (Goal), y un conjunto de números que denotaremos por \(P\) (de Prohibidos). En cada turno, podemos transformar un número en otro añadiendo/sustrayendo 1 a uno de sus dígitos (por ejemplo, pasando de \(678\) a \(679\), o de \(234\) a \(134\)). El coste de cada movimiento es 1. Adicionalmente, tenemos estas restricciones:
    1. No se permite añadir \(1\) a \(9\), ni sustraer \(1\) a \(0\).
    2. No se permite convertir un número en un elemento de \(P\) (por eso son prohibidos).
    3. No se puede cambiar un mismo dígito 2 veces seguidas.
    El objetivo es transformar \(S\) en \(G\) en el menor número de movimientos posibles.
    a) Formula el problema como un espacio de estados en el que se pueda aplicar el algoritmo A*.
    b) Define una heurística admisible para ser usada en la aplicación del algoritmo A*.
    c) Usa la heurística del apartado anterior para resolver el caso \(S = 567\), \(G = 777\) y \(P = \{666, 667\}\).

« Búsquedas Informadas… « || Inicio || » Búsquedas Locales »