Prácticas de Programación III. Curso 2001-2002

Hola, esto es mi trabajo escrito para las prácticas de Programación III, tras las sesiones presenciales de los días 14 y 15 de Diciembre en Las Rozas, Madrid. El código en modula2 lo he implementado, probado y compilado con el compilador XDS versión 2.45, que me bajé de prueba de la red.

El programa consta de estos módulos (comprimidos junto con el ejecutable juego.exe):

Ensayo .def .mod

EntrSal .def .mod

ExploraGrafos.def .mod

PilaEnsa .def .mod

PilaEnla .def .mod

Juego.mod

Funciona como viene especificado en el enunciado de las prácticas, dándole un fichero como argumento en la línea de comando de DOS.

El código de estos módulos está al final de este documento. Por favor, si necesitas algo más no dudes en escribirme por correo electrónico. Gracias.

Diseño del algoritmo

¿Existe alguna regla o criterio que nos permita, en cada momento del juego, saber cuál es el movimiento óptimo que nos garantice la resolución del juego (si es posible)? Utiliza tu respuesta para decidir razonadamente si el esquema voraz es apropiado para resolver el problema.

No, una jugada será buena si conduce a la solución, pero eso sólo lo sabes cuando efectivamente la alcanzas, varias jugadas después. Así que nada nos puede ayudar a decidir entre jugadas alternativas “a priori”. Por otro lado, una jugada mala deberá ser deshecha para terminar el juego, si es que hay solución. Por estas dos razones, una aproximación “voraz” a la resolución del problema no es posible: no podemos por lo general decidir qué movimiento es más prometedor y puede ser necesario deshacer decisiones ya tomadas.

Supón que dividimos el tablero inicial en dos partes, y encontramos la forma de resolver cada parte individualmente. Las dos soluciones a los subtableros, ¿nos sirven para resolver el tablero completo?¿Qué otras formas hay de reducir el problema a subproblemas idénticos?¿Alguna nos permite utilizar el esquema divide y vencerás? Razona tus respuestas.

No es posible solucionar dos subtableros de forma independiente, porque estaríamos ignorando las adyacencias de las casillas que tocan al subtablero vecino. Por esta razón no tiene sentido dividir el tablero en trozos más pequeños y por eso no es posible aplicar el esquema algorítmico “divide y vencerás” aquí.

Este juego tiene un grafo implícito asociado, en el que los nodos son las situaciones posibles en el tablero, y las aristas indican transiciones entre tableros mediante jugadas válidas. Tomando como nodo inicial el tablero de partida en el ejemplo anterior, representa los dos primeros niveles del grafo asociado.

O	O	X	+	X
O	+	+	X	+
O	*	*	O	X
O	O	*	X	X

	X	+	X
	+	X	+
+	*	O	X
*	*	X	X

O			+	X
O	O		X	+
O	+	X	O	X
O	O	+	X	X

O	O	X
O	+	+	+
O	*	*	X	X
O	O	*	O	+
O			+	X
O	O	X	X	+
O	*	*	O	X
O	O	*	X	X

Responde a las siguientes preguntas sobre los grafos asociados a este juego: ¿Se trata de un grafo finito o infinito?¿Cuál es la profundidad máxima?¿Y el grado de ramificación máximo?¿Tiene ciclos?¿Se puede llegar al mismo nodo por dos caminos diferentes?¿Se trata de un árbol?

Es un grafo finito, puesto que el número de jugadas que pueden aplicarse sobre un tablero es siempre finito, y por lo tanto el número de tableros que pueden ser generados es finito. En cuanto a la profundidad máxima, en el caso peor un tablero de dimensiones F"C tendrá F"C/2 posibles regiones de adyacencia, así que la profundidad máxima del árbol generado a partir de él será de F"C/2. Y por el mismo criterio establecemos el mismo número como el mayor grado de ramificación posible. No contendrá ciclos, puesto que las ramas generadas a partir de un tablero dado se obtienen por eliminación de celdas, por lo que nunca un tablero podrá generar tableros hijos con el mismo número de celdas, y por tanto nunca podrá haber ciclos en nuestro problema. Sin embargo, sí será posible en ocasiones llegar al mismo tablero desde diferentes ramas del grafo. Por esta razón a este grafo no lo podemos llamar estrictamente un árbol.

Considera la posibilidad de resolver el problema mediante una exploración ciega en el grafo implícito asociado. Comenta qué importancia tiene cada una de las características del grafo (que has descrito en la pregunta anterior) a la hora de realizar la búsqueda.

En primer lugar, al tratarse de un grafo finito, tenemos la certeza de que el algoritmo que usemos para explorarlo terminará la tarea en un tiempo asimismo finito. Además, al no haber ciclos no tenemos que preocuparnos por callejones son salida en nuestro algoritmo.

Si se utiliza un esquema de exploración de grafos ¿cuál es el más adecuado?

En principio la solución para este problema sería una “búsqueda en profundidad” con vuelta atrás. Este esquema general sería:

Fun vuelta-atrás (ensayo)

Si válido (ensayo) dev ensayo

Si no

para hijo " compleciones (ensayo)

si condiciones-de-poda (hijo) hacer vuelta-atrás (hijo)

fsi

fsi

Ffun

Si sólo nos interesa encontrar una solución, modificaríamos el esquema general para detener la exploración tras encontrar la primera solución. De esta forma ganaríamos en eficiencia. Como explico en la pregunta 9, si lo que buscamos es la solución óptima, yo usaría un esquema de “búsqueda en anchura”, para asegurarnos encontrar en primer lugar la menos profunda en el grafo.

En un esquema de exploración de grafos, la estructura de datos “Ensayo” será cada situación de juego. Para resolver el problema necesitamos dos operaciones sobre Ensayos: por un lado, identificar las regiones que se pueden seleccionar para ser eliminadas; por otro lado, dado un Ensayo y una región concreta, necesitamos una operación que elimine todas las casillas que pertenecen a esa región. De acuerdo con estas necesidades, discutir cuál es la implementación del tipo de datos “Ensayo” más adecuada (en cuanto a sencillez de manipulación y eficiencia). Considera al menos dos implementaciones distintas.

La estructura de datos “Ensayo” que he diseñado

TYPE Celda = RECORD (* celdas del tablero de un Ensayo *)

valor : CHAR;

yavista : BOOLEAN;

yaelim : BOOLEAN;

END;

TYPE Ensayo = RECORD

matriz : ARRAY[1..maxlado] OF ARRAY [1..maxlado] OF Celda;

pilaAdya : Tipo_pila;

...

END;

consta, entre otros elementos, de un tablero de estructuras de tipo “Celda” y una pila que contiene las coordenadas de las celdas que conforman una región adyacente, que habrán de ser eliminadas. Cada celda contiene su valor y dos etiquetas booleanas que nos permiten saber si ha sido ya visitada en una búsqueda y si ha sido definitivamente eliminada. Así, al avanzar el juego, el número de celdas eliminadas en los tableros hijos generados irá en aumento, pero el espacio físico ocupado en memoria por cada uno será exactamente el mismo. Esto se debe a que he elegido como estructura de datos para el tablero una matriz bidimensional de celdas, estática, con un tamaño fijo en tiempo de compilación. Esta desventaja la compenso con la facilidad de recorrer una matriz, con un coste constante, pudiendo acceder directamente a una celda con un par de coordenadas (fila y columna). De esta manera, localizar las celdas adyacentes a una dada es tan sencillo como sumar o restar 1 a las filas o las columnas. Y eliminar una celda sería sólo marcar su campo celda.yaelim como verdadero. Esta implementación podría haber sido todavía mejor si, como en C++, fuera posible crear matrices de acceso aleatorio con tamaño definido en tiempo de ejecución. En tal caso, cada tablero ocuparía solamente el espacio de la matriz FxC que abarcase todas las celdas. Pero esto no es posible, al menos con la biblioteca de módulos del compilador XDS, en Modula-2, así que la alternativa a esta estructura “Ensayo” que he tenido en cuenta fue una en donde el tablero estaría implementado como una lista de listas enlazadas de celdas (lista primaria de listas secundarias).

En este caso, cada tablero usaría el espacio mínimo necesario, minimizándose el gasto de memoria, puesto que las celdas eliminadas no ocuparían nada, no existirían. Sin embargo, el acceso a las celdas de la matriz se complica mucho respecto a una matriz estática. Ya no es suficiente manejar un índice de columnas y otro de filas; ahora haría falta una función que recorriese la lista primaria y que bajase por la lista secundaria deseada hasta la posición deseada, con un coste lineal. Además, para buscar adyacencias habría que visitar dos celdas consecutivamente y si fueran iguales, para eliminarlas, habría que utilizar punteros auxiliares para liberar el espacio de memoria liberado y enlazar los trozos de lista anterior y posterior. Por comodidad y por el coste de acceso constante a las celdas, me quedé con la primera opción.

Utilizando toda la información que ya has analizado, proporciona una solución completa en pseudocódigo para el problema de encontrar una solución cualquiera al juego, incluyendo las estructuras de datos necesarias. La especificación debe permitir cambiar la implementación del tipo de datos ensayo de forma modular.

Esquema general de solución

stop ! FALSE

IniciaPila ( pilaSolución );

CreaPrimerEnsayo ( Ensayo , fichero_entrada );

vuelta_atrás ( Ensayo , stop , pilaSolución );

/* llamada a procedimiento recursivo */

si stop entonces hacer

ImprimeEnsayo ( Ensayo );

ImprimeSolución ( pilaSolución );

si no

Escribir ("No hay solución");

fsi

Vuelta atrás en detalle

proc vuelta_atrás ( Ensayo, stop, pilaSolución )

si EnsayoVacío( Ensayo ) entonces hacer stop ! TRUE

si no

siguebuscando ! TRUE

mientras siguebuscando " no stop hacer

BuscaAdyacencia ( Ensayo )

si no Pila_vacía( Ensayo.pila ) entonces hacer

Ensayo_hijo ! EliminaAdyacencia( Ensayo )

si Condiciones_de_poda( Ensayo_hijo ) entonces hacer

vuelta_atrás( Ensayo_hijo , stop , pilaSolución )

si ( EnsayoVacío( Ensayo_hijo ) "

no PilaVacía( pilaSolución ) ) entonces hacer

MeterPila( pilaSolución , Ensayo_hijo )

fsi

fsi

fsi

siguebuscando ! PreparaSiguiente( Ensayo )

fmientras

fsi

fproc

Si se requiere hallar la solución en el menor número de movimientos ¿Hay algún cambio en la elección del esquema anterior? Detalla en su caso completamente el nuevo algoritmo en pseudocódigo y justifícalo.

Como ya adelanté en la pregunta 6, en este caso yo eligiría una búsqueda en anchura, porque de esa manera te aseguras de que la primera solución encontrada es la que menos movimientos requiere. Esto se debe a que se exploran todas las hojas del mismo nivel antes de pasar al siguiente. El inconveniente de este método es que gasta cada vez más espacio en memoria almacenando todas las hojas de un nivel: a medida que bajas en profundidad los requerimientos de espacio son mayores. A diferencia de la exploración en profundidad, que sugiere naturalmente una búsqueda recursiva, la búsqueda en anchura es iterativa. Aquí propongo una posible implementación en pseudocódigo:

Exploración en anchura en detalle

proc anchura ( Ensayo Ensayo, stop, pilaSolución )

cola ! "

Encolar( Ensayo, cola )

mientras no Vacía( cola ) hacer

nodo ! Desencolar( cola )

MeterPila( pilaSolución, nodo )

si EnsayoVacío( nodo ) entonces hacer

stop ! TRUE

si no

siguebuscando ! TRUE

mientras siguebuscando " no stop hacer

BuscaAdyacencia ( Ensayo )

si no Pila_vacía( Ensayo.pila ) entonces hacer

Ensayo_hijo ! EliminaAdyacencia( Ensayo )

si Condiciones_de_poda( Ensayo_hijo ) entonces

Encolar( Ensayo_hijo, cola )

fsi

fsi

siguebuscando ! PreparaSiguiente( Ensayo )

fmientras

fsi

fmientras

fproc

Otra diferencia respecto de la búsqueda en profundidad es que ahora debes mantener en una pila todos los nodos explorados para luego reconstruir la solución completa, si la hay, desde la raíz. Para eso habría que cambiar la estructura Ensayo, añadiendo un campo para guardar la dirección del nodo padre.

A veces,aunque queden regiones en el tablero que pueden ser eliminadas, se puede anticipar que ya no es posible encontrar una solución. Intenta encontrar condiciones de poda que mejoren la eficiencia del algoritmo. En general, discute posibles mejoras de la eficiencia y, en la medida de lo posible, ténlas en cuenta al realizar la implementación definitiva.

Ya he discutido posibles mejoras en la pregunta 7, al diseñar la estructura de datos “Ensayo”, así que ahora quedarían por discutir mejoras en el algoritmo de búsqueda. Al tratarse de una exploración en profundidad, la única posibilidad de mejorar es considerar condiciones de poda. La única que se me ocurre es la evidente: una rama nunca tendrá final feliz si alguno de los símbolos presentes en el tablero está sólo, nunca podrá formar parte de una región adyacente que puede ser eliminada. Así que he diseñado una función que comprueba exactamente eso. Se llama EnsayoConFuturo( Ensayo ): booleana y está en el módulo Ensayo.

Estudio del coste

El coste de ejecución de este algoritmo depende del tamaño del grafo del juego y de la composición del tablero inicial de juego. Si describimos el tablero inicial por medio de F (número de filas) y C (columnas), en el caso peor (un tablero formado por F"C/2 parejas diferentes de símbolos), la profundidad máxima y el grado máximo de ramificación serán r = p = F"C/2. Como no sabemos a priori si un juego tendrá solución o no, habrá que explorar todo el grafo para comprobarlo. Esto nos da, seguimos en el caso peor, una complejidad de rp. Este sería el coste asintótico sin aplicar condiciones de poda y explorando todo el tablero. Si usamos el algoritmo que he codificado en modula2, que se para al encontrar la primera solución, el coste puede ser menor, en función del número de ramas que sean exploradas antes de terminar. Y lo mismo podría decirse de la exploración en anchura.

Y si además usamos la condición de poda EnsayoConFuturo(), entonces el coste será potencialmente menor, pero como antes, también dependerá de la composición inicial del tablero de juego. El efecto de la condición de poda equivaldrá a reducir el grado de ramificación, por lo que la base de la potencia será más pequeña.

Código en modula2

Juego.mod es el módulo principal. Es muy corto y aquí lo único que hago es leer el nombre del fichero tablero, iniciar el juego e imprimer los resultados cuando termina.

EntrSal.def es el módulo que contiene las funciones para abrir y cerrar el fichero tablero.

En Ensayo.def está definida la estructura de datos Ensayo y están los prototipos para las funciones que manipulan este tipo de datos:

CreaPrimerEnsayo ( VAR tablero : Ensayo ; VAR fichero : ChanId );

(* función para generar el primer tablero de juego *)

BuscaAdyacencia ( VAR tablero : Ensayo; F,C : CARDINAL );

(* función recursiva que busca celdas adyacentes a F,C y las acumula en pilaAdya *)

EliminaAdyacencia ( VAR tablero : Ensayo ) : Ensayo;

(* función que genera un nuevo tablero hijo tras eliminar las celdas de pilaAdya en el tablero padre; vacía la pila del tablero padre *)

PreparaSiguiente ( VAR tablero : Ensayo; prF,antC : CARDINAL; opc : CHAR ):BOOLEAN;

(* función que busca,tras una búsqueda de adyacencias, la próxima celda donde buscar*)

EnsayoVacio ( VAR tablero : Ensayo ) : BOOLEAN;

(* comprueba si un ensayo tiene celdas sin eliminar *)

EnsayoConFuturo ( VAR tablero : Ensayo ) : BOOLEAN;

(* Es la única condición de poda que he codificado. Comprueba si en un tablero hay algún signo sólo, que nunca podrá formar parte de una región de adyacencia. En tal caso devuelve FALSE *)

ImprimeEnsayo ( VAR tablero : Ensayo );

Y dos funciones auxiliares que son llamadas desde las otras

testAdya ( VAR tablero : Ensayo ; F,C,adF,adC : CARDINAL ):BOOLEAN;

(* función que comprueba una adyacencia dentro de BuscaAdyacencia *)

ProximaCeldaValida ( VAR tablero : Ensayo; prF,prC : CARDINAL ):BOOLEAN;

(* función que busca la próxima celda válida empezando en prF,prC *)

En ExploraGrafos.def implemento el algoritmo de exploración de un grafo en profundidad con vuelta atrás. Sólo contiene 2 funciones:

vuelta_atrás ( VAR tablero : Ensayo; VAR stop : BOOLEAN ; VAR solucion : PilaEnsayo );

(* módulo para aplicar una exploración en profundidad del grafo juego con vuelta atrás y que se para al encontrar la primera solución, si la hay *)

ImprimeSolución ( VAR solucion : PilaEnsayo );

(* módulo que imprime la solucion, la sucesión de tableros desde el inicial al vacío *)

Quedan sólo dos módulos, PilaEnsa.def y PilaEnla.def, donde implemento dos tipos de datos “pila”, uno para guardar Ensayos y otro para guardar pares de cardinales como celdas adyacentes de un tablero.