Problema con algoritmo ricorsivo [backtracking] java

Discussione in 'Java' iniziata da Gabriele Saturni, 30 Dicembre 2014.

Tag (etichette):
  1. Gabriele Saturni

    Gabriele Saturni Nuovo Utente

    Registrato:
    30 Dicembre 2014
    Messaggi:
    1
    Mi Piace Ricevuti:
    1
    Punteggio:
    0
    Ciao ragazzi , ho dei problemi con questo algoritmo ricorsivo..spero che qualche anima pia possa aiutarmi.
    Allora il testo dell'esercizio è il seguente:
    Fornire lo pseudocodice di un algoritmo che preso in input un intero n stampi tutte le matrici contenenti le lettere ={a,b,c} nxn tali che le a precedono le b che precedono le c. ad esempio per n=2 l'output deve essere :
    output:
    aa aa aa ab ab bb aa aa ac cc bb bb bc bc ab ab ac
    aa ab bb ab bb bb ac cc ac cc bc cc bc cc bc cc bc

    Vi posto anche il mio codice, è scritto in java ,è semplicemente una funzione statica.
    Codice:
    public class EsercizioNovBT {
        public static void main(String[] args) {
            int n=2 , i , j;
            char[][] m = new char [n][n];
            /* array di booleani che indicano se esiste una b o una c nella riga/colonna i/j ad esempio:
            isBR[i] è true se è stata messa una b nella riga i , isBC[j] è true se è stata messa una b nella colonna j ,stesso    discorso per gli altri array*/
            boolean[] isBR = new boolean [n];
            boolean[] isBC = new boolean [n];
            boolean[] isCR = new boolean [n];
            boolean[] isCC = new boolean [n];
           /* inizializzazione dei vettori e della matrice */
            for(i=0;i<n;i++)
                isBR[i]=false;
            for(i=0;i<n;i++)
                isBC[i]=false;
            for(i=0;i<n;i++)
                isCR[i]=false;
            for(i=0;i<n;i++)
                isCC[i]=false;
            for (i=0 ; i<n ; i++)
                for(j=0 ; j<n ;j++)
                    m[i][j]='d';
            i=0;j=0;
            scriviSuM(m,isBR,isBC,isCR,isCR,i,j,n);
    
    
    
        }
    
    
    
        static void scriviSuM(char[][]M , boolean[] isRB,boolean[] isCB,boolean[] isRC,boolean[] isCC,int i, int j , int n)
        {
            if(i==n)
            {
                for (int r=0 ; r<n ; r++)
                {
                    for(int c=0 ; c<n ;c++)
                    {
                        System.out.print(M[r][c]);
                    }
                    System.out.print("\n");
                }
                System.out.println();
            }
            else
            {
                if(j==n)
                {
                    j=0;
                    scriviSuM(M,isRB,isCB,isRC,isCC,i+1,j,n);
                }
                else
                {
    
                        if (! (isRC[i]) && !(isCC[j])) // se non ci sono delle c
                        {
                            if( ! (isRB[i]) && !(isCB[j]) )  // se non ci sono già delle b e delle c allora puoi prendere a
                            {
                                M[i][j]='a';
                                scriviSuM(M,isRB,isCB,isRC,isCC,i,j+1,n);
                            }
    
                            isRB[i]=isCB[j]=true;
                            M[i][j]='b'; // se non ci sono  c posso comunque prendere delle b
                            scriviSuM(M,isRB,isCB,isRC,isCC,i,j+1,n);
                            isRB[i]=isCB[j]=false;
                        }
                        isRC[i]=isCC[j]=true;
                        M[i][j]='c'; // posso sempre prendere c
                        scriviSuM(M,isRB,isCB,isRC,isCC,i,j+1,n);
    
                }
    
    
            }
        }
    }
    
    ora l'output è:
    aa
    aa

    aa
    ab

    aa
    ac

    aa
    bc

    aa
    cc

    ab
    cc

    ac
    cc

    bc
    cc

    cc
    cc

    Quello che stampa è corretto...ma è solo una parte di quello che dovrebbe stampare...evidentemente taglio troppo lo spazio di ricerca.

    Ora oltre a farmi capire cosa sbaglio in questo esercizio specifico , mi piacerebbe che qualcuno possa darmi delle dritte su come risolvere i problemi con la tecnica del backtracking.
    Grazie in anticipo :):)
     
    A ottofonsuppost piace questo elemento.
  2. narc0x

    narc0x Utente Attivo

    Registrato:
    10 Ottobre 2008
    Messaggi:
    128
    Mi Piace Ricevuti:
    2
    Punteggio:
    18
    Allora per quanto riguarda il codice (tralasciando il forte mal di testa che mi e' venuto leggendo la sintassi :D), hai controllato se restituisce delle eccezioni ?
    E' possibile che hai raggiunto il limite massimo di ricorsioni sullo stack della virtual machine (impostato di default a 400k), puoi provare a forzare il garbage collector ?

    Per la spiegazione sul backtracking.

    Il backtracking e' una tecnica per risolvere dei problemi comuni nella ricerca di determinate condizioni in un albero di dati. Principalmente serve per comparare in maniera ricorsiva tutte le possibili combinazioni di una specifica condizione partendo dalla piu' bassa e andando verso la piu' alta. Per farti un esempio in codice python (ed evitare la nausea da codice Java):

    Codice:
    def prop(x,y):
        return (x and y)
    
    vals = [False, True]
    for x in vals:
        print("x=", x)
        for y in vals:
                print("y=", y)
                if prop(x,y):
                        print("\tSI")
                else:
                        print ("\tNO")
    
    Questo sopra produce come risultato:

    Il codice di sopra ha comparato tutte le possibili combinazioni tra i 2 valori della lista:

    Fonte: http://it.wikipedia.org/wiki/Backtracking
     
    Ultima modifica: 9 Gennaio 2015
    A ottofonsuppost piace questo elemento.
Sto caricando...

Condividi questa Pagina