Problema con un algoritmo en JAVA (backtracking).

Thread View: es.comp.os.linux.programacion

4 messages

[T] Back to Threads [V] Tree View [G] Group Articles

4 total messages Started by Manuel Wed, 09 Nov 2005 12:56

#1461

Author: Manuel
Date: Wed, 09 Nov 2005 12:56

45 lines
2608 bytes

Hola.

Resulta que estoy haciendo una practica de una asignatura, pero no controlo 
muy bien JAVA, y por encima nos piden resolver el juego del sudoku usando un 
algoritmo backtracking.

Lo que quiero saber es lo siguiente:
Tengo una funcion llamada compleciones que retorna un objeto Stack, que es 
la encargada de generar los hijos de un nodo (tambien llamado ensayo) del 
arbol de busqueda, esto hijos (objetos) se guardan en una pila (el objeto 
Stack del paquete java.util).

    private static void backtracking(Censayo e)
    {
        if (e.valido())
        {
            e.solucion();
        }
        else
        {
            pila = e.compleciones();
            while (!pila.empty())
            {
               Censayo hijo = (Censayo)pila.pop();
                if (hijo.poda())
                {
                       backtracking((Censayo)hijo.clone());
                }
            }
        }
    }

Mi pregunta es la siguiente : �como debo de declarar el objeto pila para que 
no me borre los "ensayo hijos" cada vez que se llama a la funcion 
backtracking?,  porque cada vez que se ejecuta el metodo compleciones, se 
generan una serie de hijos que se cargan en una pila, pero luego yo lo que 
quiero es que esa pila mantenga los valores anteriores que tenia.

He probado con static Stack pila  = new Stack(); pero creo que no funciona, 
o es algo que no comprendo sobre java al intentar pasar un problema en C a 
Java....algo me falta para que funcione.

GRACIAS.

Saludos.

Re: Problema con un algoritmo en JAVA (backtracking).

#1462

Author: Manuel
Date: Wed, 09 Nov 2005 13:13

36 lines
1879 bytes

 �Esto funcionaria como yo quiero?

      static Stack pila = new Stack();

>    private static void backtracking(Censayo e)
>    {
          Stack pilaCompleciones = new Stack();

>        if (e.valido())
>        {
>            e.solucion();
>        }
>        else
>        {
              pilaCompleciones  = e.compleciones();
              Censayo hijoAux = (Censayo)pilaCompleciones.pop();
              pila.push((Censayo)hijoAux.clone());

>            while (!pila.empty())
>            {
>               Censayo hijo = (Censayo)pila.pop();
>                if (hijo.poda())
>                {
>                       backtracking((Censayo)hijo.clone());
>                }
>            }
>        }
>    }







pilaAux.push((Censayo)hijoAux.clone());

Re: Problema con un algoritmo en JAVA (backtracking).

#1465

Author: Alberto Cabello Sanchez
Date: Fri, 11 Nov 2005 09:00

8 lines
1531 bytes

Manuel wrote:
> Hola.
> 
> Resulta que estoy haciendo una practica de una asignatura, pero no controlo 
> muy bien JAVA, y por encima nos piden resolver el juego del sudoku usando un 
> algoritmo backtracking.

Mejor pregunta en comp.lang.java o en es.comp.lenguajes.java

Re: Problema con un algoritmo en JAVA (backtracking).

#1466

Author: Claudio
Date: Fri, 11 Nov 2005 10:26

45 lines
2685 bytes

On 2005-11-09, Manuel <no@no.com> wrote:
> Hola.
>
> Resulta que estoy haciendo una practica de una asignatura, pero no controlo 
> muy bien JAVA, y por encima nos piden resolver el juego del sudoku usando un 
> algoritmo backtracking.
>
> Lo que quiero saber es lo siguiente:
> Tengo una funcion llamada compleciones que retorna un objeto Stack, que es 
> la encargada de generar los hijos de un nodo (tambien llamado ensayo) del 
> arbol de busqueda, esto hijos (objetos) se guardan en una pila (el objeto 
> Stack del paquete java.util).
>
>     private static void backtracking(Censayo e)
>     {
>         if (e.valido())
>         {
>             e.solucion();
>         }
>         else
>         {
>             pila = e.compleciones();
>             while (!pila.empty())
>             {
>                Censayo hijo = (Censayo)pila.pop();
>                 if (hijo.poda())
>                 {
>                        backtracking((Censayo)hijo.clone());
>                 }
>             }
>         }
>     }
>
> Mi pregunta es la siguiente : �como debo de declarar el objeto pila para que 
> no me borre los "ensayo hijos" cada vez que se llama a la funcion 
> backtracking?

Me parece entender que en la pila pones todos los posibles ensayos hijos
de un determinado estado y despu�s pasas al siguiente nivel con
backtracking((Censayo)hijo.clone()), el cual mete nuevos ensayos hijos
en la misma pila. Pero � que criterio usas para distinguir los metidos
por el padre de los metidos por el hijo ?

Un saludo.
--claudio--

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads