El problema del calendario mediante búsqueda en espacio de estado

El problema del calendario, para una competición deportiva en la que se enfrentan n participantes, consiste en elaborar un calendario de forma que:

  • el campeonato dure n-1 días,
  • cada participante juegue exactamente un partido diario y
  • cada participante juegue exactamente una vez con cada adversario.

Por ejemplo, con 8 participantes una posible solución es

donde las filas indican los jugadores y las columnas los días; es decir, el elemento (i,j) indica el adversario del jugador i el día j; por ejemplo, el adversario del jugador 2 el 4ª día es el jugador 6.

Para representar el problema se define el tipo Calendario como matrices de enteros,

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

tal que calendario n son las soluciones del problema del calendario, con n participantes, mediante el patrón de búsqueda em profundidad. Por ejemplo,

Soluciones

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


Soluciones en Haskell


Soluciones en Python

El problema de las fichas mediante búsqueda en espacio de estado

Para el problema de las fichas de orden (m,n) se considera un tablero con m+n+1 cuadrados consecutivos.

Inicialmente, en cada uno de los m primeros cuadrados hay una blanca, a continuación un hueco y en cada uno de los n últimos cuadrados hay una ficha verde. El objetivo consiste en tener las fichas verdes al principio y las blancas al final.

Por ejemplo, en el problema de las fichas de orden (3,3) el tablero inicial es

y el final es

Los movimientos permitidos consisten en desplazar una ficha al hueco saltando, como máximo, sobre otras dos.

Para representar el problema se definen los siguientes tipos de datos:

  • Ficha con tres constructores B, V y H que representan las fichas blanca, verde y hueco, respectivamente.

  • Tablero que es una lista de fichas que representa las fichas colocadas en el tablero.

  • Estado representa los estados del espacio de búsqueda, donde un estado es una lista de tableros [t(n), …, t(2), t(1)] tal que t(1) es el tablero inicial y para cada i (2 <= i <= n), t(i) es un sucesor de t(i-1).

  • Busqueda es un procedimiento de búsqueda

Además, se considera la heurística que para cada tablero vale la suma de piezas blancas situadas a la izquierda de cada una de las piezas verdes. Por ejemplo, para el estado

su valor es 1+2+2 = 5. La heurística de un estado es la del primero de sus tableros.

Usando los métodos de búsqueda estudiado en los ejercicios anteriores, definir la función

tal que fichas b m n es la lista de las soluciones del problema de las fichas de orden (m,n) obtenidas mediante el procedimiento de búsqueda b. Por ejemplo,

Soluciones

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


Soluciones en Haskell


Soluciones en Python

El problema del granjero mediante búsqueda en espacio de estado

Un granjero está parado en un lado del río y con él tiene un una cabra y una repollo. En el río hay un barco pequeño. El desea cruzar el río con sus tres posesiones. No hay puentes y en el barco hay solamente sitio para el granjero y un artículo. Si deja la cabra con la repollo sola en un lado del río la cabra comerá la repollo. Si deja el lobo y la cabra en un lado, el lobo se comerá a la cabra. ¿Cómo puede cruzar el granjero el río con los tres artículos, sin que ninguno se coma al otro?

Para representar el problema se definen los siguientes tipos de dato:

  • Orilla con dos constructores (I y D) que representan las orillas izquierda y derecha, respectivamente.
  • Estado que es una tupla que representa en qué orilla se encuentra cada uno de los elementos (granjero, lobo, cabra, repollo). Por ejemplo, (I,D,D,I) representa que el granjero está en la izquierda, que el lobo está en la derecha, que la cabra está en la derecha y el repollo está en la izquierda.

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

tal que granjero son las soluciones del problema del granjero mediante el patrón de búsqueda en espacio de estados. Por ejemplo,

Soluciones

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


Soluciones en Haskell


Soluciones en Python

El algoritmo de Prim del árbol de expansión mínimo por escalada

El algoritmo de Prim calcula un recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Prim funciona de la siguiente manera:

  • Inicializar un árbol con un único vértice, elegido arbitrariamente, del grafo.
  • Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
  • Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)

Usando la búsqueda en escalada el tipo abstracto de datos de los grafos, definir la función

tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim con bñusqueda en escalada. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

entonces

Soluciones

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


Soluciones en Haskell


Soluciones en Python

Problema de las monedas por búsqueda en escalada

El problema del cambio de monedas consiste en determinar conseguir una cantidad usando el menor número de monedas disponibles. Se supone que se posee un número ilimitado de monedas de 1, 2, 5, 10, 20, 50 y 100 euros. Por ejemplo, para conseguir 199 se necesitan como mínimo 7 monedas (129 = 2 + 2 + 5 + 20 + 20 + 50 + 100).

En la representación se usarán los siguientes tipos:

  • Moneda, que es un número entero representado el valor de la moneda
  • Solucion, que es una lista de monedas cuya suma es la cantidad deseada y no nay ninguna lista más corta con la misma suma.

Usando la búsqueda en escalada, definir la función

tal que (cambio n) es la solución del problema de las monedas, para obtener la cantidad n, por búsqueda en escalada. Por ejemplo,

Soluciones

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


Soluciones en Haskell


Soluciones en Python