Práctica de Programación 3 UNED

Memoria de la práctica de Programación III de la UNED

Práctica de la
Asignatura de Programación III
Versión 1.0

Escuela Técnica Superior de
Ingeniería Informática
UNED
Curso 2006-2007

Memoria de la práctica de Programación III de la UNED

Indice
Indice……………………………………………………………………………... 2
Enunciado de la practica…………………………………………………………..3
1. Respuesta a las cuestiones planteadasen este enunciado:
1.1 Cuestión 1…………………………………………………………….....4
1.2 Cuestión 2…………………………………………………………….....8
1.3 Cuestión 3………………………………………………………………12
1.4 Cuestión 4………………………………………………………………13
1.5 Cuestión 5………………………………………………………………14
1.6 Cuestión 6………………………………………………………………15
1.7 Cuestión 7………………………………………………………………18
2. Ejemplo de ejecución para el caso de prueba ………………………………….22
3. Estudio delcoste del algoritmo…………………………………………………25
4. Un listado del código fuente COMPLETO………………………………….....26

Memoria de la práctica de Programación III de la UNED

1.- ENUNCIADO DE LA PRÁCTICA
Se trata del juego del Puzzle (n2-1). En este caso, el objetivo es encontrar la solución a
este juego que conlleve el menor número de movimientos aplicando el esquema de
Ramificación y Poda. El juego partede un tablero de n2 piezas numeradas del 1 al n2-1.
Dada una concreta disposición inicial de las piezas, queda una vacía, el hueco. El
objetivo del juego es transformar, mediante movimientos legales de las piezas, la
disposición inicial en una disposición final tal que en cada casilla [i,j] se encuentre la
pieza numerada (i-1)*n + j, y el hueco esté en la casilla [n,n].
Los movimientos quese consideran legales son aquellos en los que el hueco se puede
mover hacia arriba, abajo, derecha o izquierda, sin salirse del tablero y sólo una
posición cada vez. También es posible interpretar que lo que se mueven son las piezas
adyacentes al hueco, en horizontal o vertical una posición. El siguiente ejemplo muestra
una disposición inicial y cuál sería el resultado para Puzzle-8.
1
4
75

1
4
7

2
5
8

8

2
3
6
3
6

Disposición inicial
(aleatoria)

Resultado

La salida del programa consistirá en la secuencia de tableros que conduce a la
finalización del juego.
2.- REALIZACIÓN DE LA PRÁCTICA
La práctica constará de una memoria y de un programa correctamente escrito y que
resuelva el problema planteado mediante el esquema de Ramificación y Poda.
En lamemoria se detallarán las respuestas a las preguntas planteadas y un listado
comentado del código fuente. Se valorará que el código esté comentado de forma que se
facilite su lectura.

***La práctica se realizará en Java ****

CUESTIONES

Memoria de la práctica de Programación III de la UNED

1. Expón las características particulares de la aplicación del
esquema al problema encuestión.

En el problema del puzzle (n 2-1) como además de encontrar la solución al problema, hay que
encontrar la que tenga el menor número de movimientos, o sea la óptima, queda claro que será
necesario aplicar el esquema de ramificación y poda, cuyo esquema es el siguiente, según el
libro de la asignatura (Esquemas algorítmicos: Enfoque Metodológico y Problemas Resueltos
ed. UNED):

funramificación-y-poda (ensayo)
m ← montículo-vacío
cota-superior ← inicializar-cota-superior
solución ← solución-vacía
añadir-nodo(ensayo,m)
mientras ¬vacío(m) hacer
nodo ← extraer-raiz(m)
si válido(nodo) entonces hacer
si coste(nodo) < cota-superior entonces hacer
solución ← nodo
cota-superior ← coste(nodo)
fin si
si no
si cota-inferior(nodo) ≥ cota-superior entonces
devolver solución
sino
para cada hijo en compleciones(nodo) hacer
si condiciones-de-poda(hijo) y cota-inferior(hijo) < cota-superior
entonces añadir-nodo(hijo,m)
fin si
fin para
fin si
fin si
fin mientras
fin fun

Para la identificación del algoritmo con el problema habrá que definir los nodos que se pasan
como ensayo, cómo se hallan los hijos de un nodo (compleciones), establecer las condiciones de...