Búsqueda en escalada

En la búsqueda en escalada se supone que los estados están mediante una función, la heurística, que es una estimación de su coste para llegar a un estado final.

Definir la función

tal que (buscaEscalada s o e) es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e, obtenidas buscando en escalada.

Nota: La búsqueda en escalada se aplica en el problema de las monedas.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

El problema del 8 puzzle

Para el 8-puzzle se usa un cajón cuadrado en el que hay situados bloques cuadrados. El cuadrado restante está sin rellenar. Cada bloque tiene un número. Un bloque adyacente al hueco puede deslizarse hacia él. El juego consiste en transformar la posición inicial en la posición final mediante el deslizamiento de los bloques. En particular, consideramos el estado inicial y final siguientes:

Para solucionar el problema se definen los siguientes tipos:

  • Tablero es una matriz de número enteros (que representan las piezas en
    cada posición y el 0 representa el hueco):

  • Estado es una listas de tableros [t_n,…,t_1] tal que t_i es un
    sucesor de t_(i-1).

Usando el procedimiento de búsqueda por primero el mejor, definir la función

tal que (solucion_8puzzle t) es la solución del problema del problema del 8 puzzle a partir del tablero t. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Búsqueda por primero el mejor

En la búsqueda por primero el mejor se supone que los estados están ordenados mediante una función, la heurística, que es una estimación de su coste para llegar a un estado final.

Definir la función

tal que buscaPM s o e es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e, obtenidas buscando por primero el mejor.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

El tipo abstracto de datos de las colas de prioridad

1. El tipo abstracto de datos de las colas de prioridad

Una cola de prioridad es una cola en la que cada elemento tiene asociada una prioridad. La operación de extracción siempre elige el elemento de menor prioridad.

Las operaciones que definen a tipo abstracto de datos (TAD) de las colas de prioridad (cuyos elementos son del tipo a) son las siguientes:

tales que

  • vacia es la cola de prioridad vacía.
  • (inserta x c) añade el elemento x a la cola de prioridad c.
  • (primero c) es el primer elemento de la cola de prioridad c.
  • (resto c) es el resto de la cola de prioridad c.
  • (esVacia c) se verifica si la cola de prioridad c es vacía.

Las operaciones tienen que verificar las siguientes propiedades:

  • inserta x (inserta y c) == inserta y (inserta x c)
  • primero (inserta x vacia) == x
  • Si x <= y, entonces primero (inserta y (inserta x c)) == primero (inserta x c)
  • resto (inserta x vacia) == vacia
  • Si x <= y, entonces resto (inserta y (inserta x c)) == inserta y (resto (inserta x c))
  • esVacia vacia
  • not (esVacia (inserta x c))

2. Las colas de prioridad en Haskell

2.1. El tipo abstracto de datos de las colas de prioridad en Haskell

El TAD de las colas de prioridadd se encuentra en el módulo ColaDePrioridad.hs cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio,
solo considearemos una que usa las listas.

2.2. Implementación de las colas de prioridad mediante listas

La implementación se encuentra en el módulo ColaDePrioridadConListas.hs cuyo contenido es el siguiente:

3. Las colas de prioridad en Python

3.1. El tipo abstracto de las colas de prioridad en Python

La implementación se encuentra en el módulo ColaDePrioridad.py cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos solo una que usa las listas.

3.2. Implementación de las colas de prioridad mediante listas

La implementación se encuentra en el módulo ColaDePrioridadConListas.py en el que se define la clase CPrioridad con los siguientes métodos:

  • inserta(x) añade x a la cola.
  • primero() es el primero de la cola.
  • resto() elimina el primero de la cola.
  • esVacia() se verifica si la cola es vacía.

Por ejemplo,

Además se definen las correspondientes funciones. Por ejemplo,

Finalmente, se define un generador aleatorio de colas de prioridad y se comprueba que las colas de prioridad cumplen las propiedades de su especificación.

El problema de la mochila (mediante espacio de estados)

Se tiene una mochila de capacidad de peso p y una lista de n para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en la mochila sin sobrepasar la capacidad de la mochila colocando el máximo valor posible.

Para solucionar el problema se definen los siguientes tipos:

  • Una solución del problema de la mochila es una lista de objetos.

  • Los objetos son pares formado por un peso y un valor

  • Los pesos son número enteros

  • Los valores son números reales.

  • Los estados del problema de la mochila son 5-tupla de la (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el peso de los objetos colocados, l es el límite de la capacidad de la mochila, o es la lista de los objetos colocados (ordenados de forma creciente según sus pesos) y s es la solución parcial.

Usando el procedimiento de búsqueda en profundidad, definir la función

tal que mochila os l es la solución del problema de la mochila para la lista de objetos os y el límite de capacidad l. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python