Trincado con JAVA
 

Mis conocimientos sobre Java son bastante escasos así que no me queda más remedio que buscar ayuda por donde sea.

Debo implementar un método que forma parte de un programa mayor y que halle los sucesores de un tablero.

Hasta ahora he hecho lo siguiente:

[CODE] * Método para conocer cuáles son los nodos sucesores al tablero actual.
* @return Un contenedor con los nodos sucesores al nodo actual.
* @throws CloneNotSupportedException Si el nodo actual no se puede clonar.
*/
public ArrayList<Nodo> sucesores() throws CloneNotSupportedException
{

ArrayList<Nodo> sucesores = new ArrayList<Nodo>();
Nodo nodo = new Nodo();
Iterator it = islas.iterator();



while (it.hasNext())
{

Isla islaActual=(Isla)it.next();

if ((islaActual.esPosiblePuenteEnDirección(1))&( numPuentesColocados<numPuentesNecesarios))
{
islaActual.colocarPuente(1);

islaActual.setPosiblePuenteEnDirección(1,false);
numPuentesColocados++;
calcularVecinos();
};

nodo= (Nodo) clone();
sucesores.add(nodo);


if ((islaActual.esPosiblePuenteEnDirección(2))&( numPuentesColocados<numPuentesNecesarios))
{
islaActual.colocarPuente(2);
islaActual.setPosiblePuenteEnDirección(2,false);
numPuentesColocados++;
calcularVecinos();
};

nodo= (Nodo) clone();
sucesores.add(nodo);



};

return sucesores;
} [/CODE]

Cuando hago la traza del método clone() veo que efectivamente trabaja con los datos del nodo actual y luego devuelve el nodo clonado. Sin embargo, cuando llamo a sucesores.add(nodo) en la sentencia siguiente para guardar la copia en el arraylist, me guarda un nodo vacío y no el devuelto por clone().

Si alguien me orienta sobre el tema le estaré muy agradecido.

Salúos.
PD: No sé si con el CODE fue peor el remedio que la enfermedad. :D

La verdad es que hace mas de 10 años que no hago nada con Java y estoy oxidado.
Pero te recomiendo que la próxima vez que postees código en vez de utilizar el tag [B]QUOTE[/B] uses el [B]CODE[/B], ya que el primero se come los espacios haciendo ilegible el programa y el segundo los mantiene.
Por ejemplo he puesto lo mismo en ambos y sin embargo se ven diferentes
[quote]
if (condicion)
{
.....
}
[/quote]
[code]
if (condicion)
{
.....
}
[/code]

Gracias, Kezu.

Hace un momento acabo de salir del atolladero con ésto

[CODE] nodo= (Nodo) clone();
sucesores.add(nodo);[/CODE]


Ahora si que me carga todo en el arraylist haciendo una copia profunda de todos los objetos contenidos dentro del objeto nodo.

Pero salgo de uno para meterme en otro. Ya tengo los sucesores del tablero pero ahora me da un overflow o desbordamiento de pila en una parte de la clase principal. Sigo en la lucha.:D:D

El que la persigue la consigue.

Salúos.

eso es que hay demasiadas llamadas anidades.
si por ejemplo se trata del tablero de un juego de mesa, el ajedrez mismo, el número de jugadas crece de forma exponencial por lo que la pila de llamadas se sobrepasa, de alguna manera tienes que valorar cada opción y desechar las que a priori parezca que no aportan nada.

Efectivamente, el esquema es un backtracking y genera un mogollón de llamadas recursivas. Tengo que desechar por algún lado.

ya me lo estaba intuyendo, eres un libro abierto para mi :D :D :D

La recursividad es un recurso muy potente, pero que consumen cantidades tremendas de memoria, tanto en la pila de llamadas como en la replicación de todas las variables locales, y por tanto no siempre es la opción mas eficiente.

Como ejemplo de una mala aplicación de la recursividad tenemos la función factorial, es mucho mas rápido, eficiente y apenas consume memoria de la segunda forma
[code]
long Fact(int n)
{
long result;
if (n=1) {
result=1;
} else {
result=n*Fact(n-1);
}
return result;
}

long Fact(int n)
{
long result;
int i;
result=1;
for (i=2; i<=n; i++) {
result*=i;
}
return result;
}
[/code]

Bueno, yo creo que el coste asintótico del algoritmo de las dos funciones viene a ser el mismo, al menos en teoría, pues depende del tamaño del problema, en este caso "n".
Quizás la única ventaja es que la versión iterativa se hace más legible pues la recursividad es algo más engorrosa de entender

Para calcular el factorial de n sólo es necesario multiplicar Fact(n-1)*n. Evidentemente, no conocemos Fact(n-1) pero sabemos que el factorial de (n-1) es igual a Fact(n-2)*(n-1) y así sucesivamente hasta llegar al caso trivial n=1 cuyo factorial se calcula directamente.

Los algoritmos de exploración de grafos (con sus correspondientes nodos) parecen más de naturaleza recursiva que iterativa por eso, en este caso concreto, estoy condenado a la recursividad y al riesgo de desbordar la pila.

Seguimos en ello. :D

Salúos.

no, el coste no es ni parecido (a no ser que n sea menor que 10) el coste de encadenar llamadas es basante elevado, hay que poner en la pila de llamadas la dirección de retorno y esta pila no suele ser muy grande ya que no se suelen encadenar muchas llamadas, y ademas por cada llamada hay que crear de nuevo las variables locales para guardar el estado actual, pro tanto si n=1000 habrán 1000 variables locales y 1000 direcciones de retorno (aunque siendo relaistas el valor del factorial de 1000 no cabe ni de lejos en un entero largo ;))
Y he oido muchas veces que la recursividad es difícil de leer, para mi es todo lo contrario, lo veo mas fácil y lógico, pero es que yo digo mucha veces que mi cerebro piensa como un ordenador y por eso los entiendo tan bien que muchas veces solo con ver como se comporta ya se donde está el problema.

por cierto, seguro que en Google encuentras multitud de algoritmos para lo que buscas.
Recuerdo que ya hace una década buscaba algoritmos optimizados para el problema del viajante de comercio (TSP en inglés), que no se conoce una solución y no queda mas remedio que calcular todas las posibilidades y encontré bastante (muchas de ellas en inglés) y en las mismas páginas (generalmente de departamentos de matemáticas o de investigación operativa de universidades) habían enlaces a otros algoritmos comunes.

PD: No sabía yo de tu aficición por la programación y por lo que antes se llamaba Inteligencia Artificial, igual aún tengo por algún lado el libro con el que dí esa asignatura en el último curso de la facultad de informática, pero de eso hace 25 años (apenas se hablaba entonces de las redes neuronales) y era muy básico, pero si que tenía algoritmos para optimizar este tipo de busquedas en grafos.

Creo que los dos llevamos razón en cuanto al coste.

La cuestión es que creo que tú lo está viendo desde el punto de vista de los recursos del sistema (del que como bien demuestras gana el iterativo por goleada) y yo parto de unos recursos iguales para cada uno de los algoritmos y lo que contemplo es la variable tiempo. Entonces el coste en referencia a la eficiencia temporal de las dos funciones es parecida.

Salúos.