 |
| Algo cuco para no dejar el árbol en los huesos |
Comienzos de Diciembre de 2012, me surgió un apañillo.
Un estudiante de ingenería informática en la UNED se vió sorprendido por una de sus asignaturas – en concreto la asignatura más avanzada de programación como tal – “Programación III”, obligada para Ingenierías técnicas informáticas – sistemas y gestión –, como para la Ingeniería superior informática.
Me pidió, le echara una mano.
Me pidió, le echara una mano.
Contexto sobre la asignatura “Programación III”
Lo que a continuación detallo es tan real como venenoso. Sufrido en carnes, incluso.
Al tratarse de algo muy español y muy propio de nuestro sistema y país, no lo voy a traducir --Dejo a visitantes foranos la opción de traducción por "DIY"--.
Es más, para no desvirtualizar el contenido de la entrada en sí, voy a empezar a usar botones de expandir.
Al tratarse de algo muy español y muy propio de nuestro sistema y país, no lo voy a traducir --Dejo a visitantes foranos la opción de traducción por "DIY"--.
Es más, para no desvirtualizar el contenido de la entrada en sí, voy a empezar a usar botones de expandir.
La práctica 2012/2013:
.jar para KNIGHT's TOUR o el problema del caballo, básicamente.
Aquí está la práctica a realizar:
Como se ve en el pdf , de forma
resumida, piden un jar (Archivo java ejecutable) que se pueda
invocar basándose en 4 propiedades distintas:
- Lado del tablero
- Posición inicial de salida del caballo
- El programa se ejecuta hasta alcanzar una solución o hasta hallar todas las existentes para la posición de partida
- Dame la traza de cada movimiento
Queremos pués que, un caballo de ajedrez haga caminos hamiltonianos (pase una y sólo una vez por cada casilla) en un tablero cuadrado y siempre que, su lado sea mayor o igual que 5.
 |
| Noria, carrusel y ahora tablero. No podían elegir al cocodrilo, no. |
El
programa admitirá que demos longitud al lado del tablero.
También
permitirá que establezcamos una posicion incial (x,y) para el
caballo. Obligada la casilla inferior izquierda como 0,0.
Permitirá la opción de detenerse cuando encuentre un camino o de mostrar todos los posibles.
Permitirá la opción de detenerse cuando encuentre un camino o de mostrar todos los posibles.
Permitirá
la opción de mostrar la traza a cada “intento de moviento“ o no.
Por
defecto, si no añadimos ningún parámetro el programa entiende que:
-El
tablero es 8*8
-
La posición inicial de caballo es la casilla situada en el vertice
inferior izquierdo (en un tablero visual). La llameremos casilla 1 y
la podríamos etiquetar como a un par ordenado (x,y) correspondiente
(0,0).
-
El programa se detendrá al encontrar un camino y lo mostrará.
-
No hay traza.
Observaciones al enunciado de la práctica
 |
| Google: Odiseo Troya |
Efectivamente, observaciones y objeciones.
Quien haya leído el enunciado y guía exigida del pdf , teniendo algo de sentido común, habrá observado dos condiciónes que, por absurdas, dañan la vista.
Quien
sepa construir programas en Java, quizás piense como yo, 3.
Digo 3 por cómo exigen invocar el jar. "A gusto se quedo, la madre que los parió". (En los comentarios podemos discutir esto).
Digo 3 por cómo exigen invocar el jar. "A gusto se quedo, la madre que los parió". (En los comentarios podemos discutir esto).
Así que, antes de que se nos desboque nuestro Rocinante o nos amargue la fiesta Odiseo, con el fin de no extenderme demasiado, voy aprecisar:
Se acabó tanta chachara. Empezamos la chicha.
ANÁLISIS: elección de algoritmo y costes.
No
hay criterio de selección de candidatos dentro de las n2
casillas y una ruta sin solución hará que "algoritmo vóraz" finalice. Ergo,
planteamiento bajo la directriz de algoritmos voraces descartado.
En
esta primera versión , debido a premuras de tiempo, no tomaremos los
estudios matemáticos formales ya realizados sobre este problema
desde hace unos siglos. Luego, no iremos por la linea de algoritmos
"divide y vencerás". Línea que sí podríamos seguir en otras
versiones posteriores.
Hablamos
de un caballo que parte de una posicion en el tablero (“estado”)
y puede
--en caso mejor – saltar a 8 casillas (“nuevos estados”).
Parece pues que se ajusta bastante bien a la idea de grafo y árbol.
El grado de ramificación en hijos es de 8.
Hablamos,
pues, de un algoritmo de exploración de grafos que vaya
generando tableros y que nos permita la vuelta atrás
si no agotamos los n2 nodos pero si las casillas posibles
para un nuevo tablero desde una posición.
Estudio de costes:
DISEÑO
He
diseñado el módulo en 4 clases: 'saltocaballo', 'Tablero',
'Secretario' y 'Exploradora'.
No
sé hasta que punto es conveniente mostrar el esquema de cada clase,
puesto que aquí ya hay detalles que pertencen al campo de la
implementación. Pero, por si a alguien le sirve para tomar confianza,
aquí van.
La
clase 'Secretario' se encarga de pasar los tableros a ficheros.
Podría, inicialmente, considerarse innecesaria como clase y
suplirla por un método dentro de la clase Exploradora. Podría. Sin
embargo, me ha parecido más claro establecerla como clase e
instanciarla en una 'topisto' (elegante telefonista) por si, para
futuras versiones, se le requirieran más cosas.
La clase 'saltocaballo' es la clase que lleva el main y gestiona la parametrización de la invocación y computa el problema pidendo, se guarden los resultados de la prueba en un fichero indentificable de acceso secuencial.
La
clase 'Exploradora' es la más compleja.
Hace instancias de
'Tablero' y genera saltos de caballo.
A la hora de explorar el método
trabajará con tipo de datos dinámico, 3.
Uno lo uso para almacenar
las soluciones que vaya encontrando en la invocación. Otro me sirve
de rastro o huella y el tercero lo uso para comprobar si he llegado a
la solución y si no generar hijo factible. Al generar hijo factible
el padre pasa a la “pila” de rastro de mi exploración. Si no
llego a solución cada vez que no hay paso factible el método toma
la cima de rastro y busca el siguiente salto en la cronología.
 |
| Una clase de exploradora |
 |
| Tablero por defecto |
Pongo un par, por ejemplo, de la clase exploradora y otra de la clase tablero y nos vamos a la implementación que es donde de verdad se destapa toda la chicha y hay que leer y comentar detenidamente. ;-)
IMPLEMENTACIÓN
Voy con los fuentes de menor a mayor complejidad:
Sí, implemento la clase tablero como "serializable". El motivo es que la hora de "explorar" un tablero dado en busca de la solución voy creando clones y modificándolos respecto al tablero que examino.
La clase 'saltocaballo' la paso a odt y os la pego en dos fotos :
El último fuente es la clase "Exploradora" que instancio en salto caballo como 'dora'.
Expongo el archivo .java en él, como veis, bastantes métodos son auxiliares:
PROBAR EN ECLIPSE Y HACER EL .JAR
Ese que, creo yo y no como dice la guía, debería de invocarse como:
$> java jar saltocaballo.jar
Y, si se quiere, darle parámetros de entrada.
Entregar el programa y ...
!A probar las camisetas! ;-)
No quiero alagar a entrada mucho más. De por sí es técnica y larga.
Os subiré un enlace para que os descarguéis el .jar y hagáis vuestras probatinas.
Recordad el coste temporal. Da igual que tengáis un "pepino" de equipo con tropecientos "quad cores". Como le pongáis lados de tablero por encima de 20, lo mismo disminuye el paro en España del 25 % y aún no tenéis solución... !Nah!
Sí que os agradecería si me haceis llegar los costes de los ficheros con busqueda exhaustiva que por probatinas genereís. Así me daré cuenta de cuanto de desfasado tengo el hardware de mi equipo. (lo ideal sería me mandeis el nombre del fichero generado , procesador de vuestro equipo , memoria ram, sistema operativo y tiempo que ha tardado en generarse el fichero una vez invocado el .jar ;-) Respecto a algunas dudas que ya me han ido llegado por correo, daré mi opinión o cómo lo hice en comentarios.
!En cuánto tenga algo de tiempo!
Mientras ya sabéis, salida 3,2,1...
SED BUENOS!
