PDF de programación - MEMORIA DE LA PRCTICA DE PROGRAMACIÓN III

MEMORIA DE LA PRÁCTICA DE

PROGRAMACIÓN III

CURSO 2006-2007



DIEGO J. SÁNCHEZ CAAMAÑO.

CENTRO ASOCIADO DE ALBACETE

MEMORIA PRÁCTICA PROGRAMACIÓN III



DIEGO J. SÁNCHEZ CAAMAÑO

Contenido:



ENUNCIADO.

1. RESPUESTAS A LAS CUESTIONES PLANTEADAS EN EL



1.1. Características de la aplicación del esquema al problema planteado
1.2. Descripción del grafo asociado al espacio de soluciones
1.3. Función de coste para la selección del nodo más prometedor
1.4. Cálculo de una cota del valor de las soluciones generadas
1.5. Estructura de datos utilizada para el almacenamiento de los nodos no

explorados

1.6. Pseudocódigo del esquema y de su instanciación al problema
1.7. Coste computacional del programa desarrollado


2. EJEMPLO DE EJECUCIÓN PARA EL CASO DE PRUEBA.

3. ESTUDIO DEL COSTE DEL ALGORITMO.

4. LISTADO DEL CÓDIGO FUENTE COMPLETO.


4.1. Clase Puzzle
4.2. Clase Resuelve
4.3. Clase Nodo
4.4. Clase Arbol
4.5. Clase Traduce

i

MEMORIA PRÁCTICA PROGRAMACIÓN III



DIEGO J. SÁNCHEZ CAAMAÑO

1.- RESPUESTAS A LAS CUESTIONES PLANTEADAS EN EL

ENUNCIADO.


1.1.- Características particulares de la aplicación del esquema al problema

planteado.

1.1.a.- Estructura de datos asociada al puzzle.


Como estructura de datos para almacenar las fichas se ha elegido un array de n2
enteros, dado el carácter fijo del número de fichas de los puzzles, y la facilidad de
cálculo de la posición relativa de las fichas respecto a la posición final requerida.
El uso de un array permite también una identificación rápida de identidad entre
puzzles (con la comparación en secuencia de sus datos) e incluso la ordenación
entre ellos, para facilitar su búsqueda.

1.1.b.- Adaptación del esquema general.


El esquema general de ramificación y poda permite la utilización de varias
estrategias a la hora de generar los nodos. Para la elección del nodo a expandir
podemos seguir un recorrido del grafo de soluciones en anchura o en profundidad.
O bien podemos utilizar un cálculo previo de una función de coste que nos
permita seleccionar el nodo en principio más prometedor, el de menor coste.
Debido al alto número de nodos diferentes posibles obtenidos al modificar el
inicial adoptaremos esta última, para reducir al máximo el número de nodos a
analizar. Para implementar la citada estrategia de minimización de costes, los
nodos generados se almacenarán en una estructura de datos que permita la
selección del nodo de menor coste de manera eficiente, que se describirá en el
punto 1.5.

1.1.c.- Consideraciones en la expansión del grafo de soluciones.


Debemos tener en cuenta la posibilidad de aparición de ciclos en la generación de
los nodos. Si uno de los nodos del grafo de soluciones es igual a uno de sus
ascendientes, generará en una de sus ramas un grafo igual al que se desarrolla a
partir de ese antecesor repetido, lo que multiplicará los nodos a investigar de
manera superflua, ya que este subgrafo, si contiene la solución, siempre tendrá un
camino de mayor longitud que la de aquel del que se deriva. Para evitar la
aparición de los aludidos ciclos, al generar los descendientes de cada nodo se
comprobará:


que ninguno de ellos es igual a su padre, mediante el descarte del movimiento
opuesto al que generó el nodo evaluado, y
que ninguno de ellos ha sido ya evaluado, por medio de la exploración de un
árbol binario de búsqueda (ordenado por el valor de las casillas de cada
puzzle comprobadas en orden ascendente). Se utiliza una estructura diferente
a la de la selección del nodo más prometedor debido al diferente criterio de
búsqueda a utilizar: ordenados por coste en la selección del nodo (varios
nodos diferentes pueden tener el mismo coste) y por el valor de las casillas
(que pretendemos que nunca sea igual).

•

•

1

MEMORIA PRÁCTICA PROGRAMACIÓN III



DIEGO J. SÁNCHEZ CAAMAÑO

1.2.- Descripción del grafo asociado al espacio de soluciones.


Las soluciones se distribuyen en un árbol cuya raíz es el puzzle inicial. A partir de
ella se desarrollan las diferentes ramas, que serán generadas expandiendo cada
uno de los nodos. Los hijos de un nodo se generan al ir moviendo las fichas del
puzzle padre; tomando como referencia el caso de prueba, los movimientos
aparentes del hueco podrán ser:

1

4

5



2

3

• Arriba (norte), intercambio de posición con el 5.
• Abajo (sur), intercambio de posición con el 8.
• Derecha (este), intercambio de posición con el 3.
•

Izquierda (oeste), intercambio de posición con el 4.



8

6

7

De esta manera
tenemos un máximo de cuatro
movimientos a partir de cada nodo. Según hemos visto
en el punto 1.1.c, debemos rechazar siempre al menos
uno de los movimientos posibles del hueco, aquel que deshaga el último realizado.
Esto nos da un máximo de tres hijos para cada nodo distinto del raíz (que no tiene
un movimiento anterior), sin tener en cuenta la posición del nodo, que puede
hacer descartar a su vez los movimientos que lo puedan sacar del tablero.

Por lo tanto, el árbol asociado al espacio de soluciones será un árbol ternario, con
la excepción del primer nivel de descendientes, que podrá ser de cuatro hijos.

1.3.- Función de coste para seleccionar el nodo más prometedor.


Dado que lo que buscamos es la solución con menos movimientos realizados, la
función de coste la estableceremos como la suma de dos factores, los
movimientos realizados hasta llegar al nodo evaluado y una estimación de los
movimientos restantes hasta alcanzar la solución.


fcoste=(movimientos realizados) + fmovimientos estimados


Para el cálculo aproximado de los movimientos restantes se usará la suma de las
distancias “de Manhattan” de cada ficha a su posición final. Ésta se calcula en
nuestro caso contando las filas y columnas que diferencian las posiciones actual y
final de cada ficha. Dará un número de movimientos cercano al real pero no
exacto, ya que no tiene en cuenta que al mover una ficha pueden descolocarse
otras (y acercarse a su posición final o alejarse de la misma).

2

MEMORIA PRÁCTICA PROGRAMACIÓN III



DIEGO J. SÁNCHEZ CAAMAÑO

distancia=Math.abs((pos/numFilas)-(posfinal/numFilas)) +

Math.abs((pos%numFilas)-(posfinal%numFilas));



pos, posfinal: son las posiciones de la ficha dentro del array de
datos del nodo y de la solución, respectivamente. pos/numFilas
da la fila de la casilla; pos%numColumnas da la columna.


Como ejemplo presentamos el caso de prueba, resoluble en cuatro movimientos:



Valores

1
4
7

5

8

2
3
6
0 movs. hechos



distancia = 4

Distancias

0
0
0

1
1
1

0
1
coste = 4

Por tanto, para seleccionar el nodo más prometedor usaremos una estrategia de
mínimo coste (LC), implementada en la ordenación de la estructura de datos en la
que se almacenarán los nodos aún no desarrollados: la extracción del nodo a
analizar en cada iteración debe proporcionar el nodo de menor coste de los
almacenados.

1.4.- Cálculo de una cota del valor de las soluciones que se encontrarán generando

sucesores a un determinado nodo.

Inicialmente tomaremos como cota un número de movimientos que depende de la
magnitud de n; tomaremos 1 para n=1 (trivial), 6 para n=2(1), 31 para n=3(2), 80
para n=4(3) y 1000 para n>4. A esta cota le añadimos un margen de trabajo de 2,
dado que a veces la función de coste sobreestima ligeramente los movimientos
restantes, como acabamos de ver en 1.3.
Una vez encontrada la primera solución, se toma como cota el número de
movimientos de la misma, para desarrollar sólamente nodos con coste menor o
igual que el de la solución encontrada.


1.5.- Estructura de datos utilizada para almacenar en orden de prioridad los

nodos creados y aún no explorados.

Se utiliza un montículo de mínimos,
la clase
PriorityQueue de Java 5.0. La inserción y la extracción de la raíz las realiza en
O(log(n)). La comprobación de estado vacío y del número de nodos contenidos se
obtiene en tiempo constante(4).

Para la implementación de la estrategia LC nos bastará con extraer la raíz como
selección del nodo más prometedor. Tras esa extracción, la clase automáticamente
restaura la condición de montículo de mínimos.

implementado mediante



(1) http://mathworld.wolfram.com/15Puzzle.html
(2) http://www.zib.de/reinefeld/bib/93ijcai.pdf
(3) http://www.ifor.math.ethz.ch/publications/1999_parallelsearchbenchzram.ps
(4) Java 2.0 Platform Standard Edition 5.0 API Specification

3

MEMORIA PRÁCTICA PROGRAMACIÓN III



DIEGO J. SÁNCHEZ CAAMAÑO

1.6.- Pseudocódigo correspondiente al esquema y a su instanciación al problema.


El esquema general es el siguiente:

fun ramificación-y-poda (ensayo) dev ensayo
m montículo-vacío
cota-superior cota-superior-inicial
solución solución-vacía
añadir-elemento (ensayo, m)
mientras ¬vacío (m) hacer



nodo extraer-raíz
si válido(nodo) entonces hacer
si coste (nodo) < cota-superior entonces hacer



fsi
si no


solución nodo
cota-superior coste (nodo)


si cota-inferior (nodo) ≥ cota-superior entonces



fsi

dev solución

entonces añadir-nodo (hijo, m)

si no



fsi

para cada hijo en expandir (nodo) hacer
si condiciones-de-poda(hijo) y cota-inferior(hijo)< cota-superior



fsi
fpara