«

»

mag 23

Il problema delle 8 regine parte 2, un approccio iterativo

6952100115_de8c56ecd8_h

Questo post è comparso inizialmente nel blog di Fabrizio Mondo qualche anno fa.

In seguito Fabrizio ha deciso di rendere il blog tematico e il post è rimasto disperso nel cyberspazio come“Un fiocco di neve che non cade in nessun posto.”(cit.).

Adesso ho deciso di correggere qualcosa e ri-pubblicarlo.

Il problema delle 8 regine parte 2, un approccio iterativo

In questo articolo ci proponiamo di riscrivere l’algoritmo descritto nel precedente in modo da renderlo completamente iterativo, questo problema è un caso particolare di un problema ricorrente nell’ottimizzazione del software, si tratta di rendere iterativo un algoritmo “intrinsecamente” ricorsivo.

Quando un problema è definibile per induzione risulta molto più semplice progettare il suo algoritmo per ricorsione e l’equivalente iterativo risulta meno leggibile.

I programmi ricorsivi risultano più chiari, più semplici, più brevi e più facili da capire delle corrispondenti versioni iterative perchè l’implementazione riflette fedelmente la strategia di soluzione del problema.

La versione iterativa però è sempre più veloce e meno pesante perchè usa una quantità costante di memoria (con la possibile eccezione delle ricorsioni tail nei linguaggi ottimizzati per la ricorsione…ma come vedremo tra poco quella è una ricorsione “semplificabile”).

Infatti ogni volta che una funzione ricorsiva chiama se stessa vengono riallocate le variabili locali e vengono aggiunti record alla memoria di stack per poi ritornare alla funzione chiamante, questo implica sia un maggiore utilizzo di memoria (pesantezza) sia un maggiore tempo di esecuzione visto che un accesso alla memoria è infinitamente più lento di un accesso a un dato che si trova in un registro.

Piccola digressione:Ricorsione TAIL e ricorsione non-TAIL

Una ricorsione si definisce tail quando la chiamata ricorsiva viene eseguita come ultima operazione, una ricorsione tail è sempre direttamente convertibile in un iterazione, vediamo un esempio banale: stampare tutti gli elementi di una lista.

stampaLista(lista){
        if(not lista.empty){
                print lista.pop;
                stampaLista(lista);
        }
}

noterete che questa ricorsione è facilmente e direttamente sostituibile con un un ciclo while.

while(not lista.empty){
    print lista.pop;
    stampaLista(Lista);
}

Alcuni linguaggi di programmazione sono pensati per basarsi sulla ricorsione più che sull’iterazione, in questi linguaggi tipicamente l’interprete comprende che si tratta di ricorsione tail e la trasforma in iterazione a runtime. Questo è l’unico caso in cui l’uso della ricorsione tail è ragionevole.

Questo è il modo di procedere tipico del Lisp ( almeno nelle sue declinazioni accademiche):

(defun stampaLista (l)
    (if (null l) ()
        (progn
            (print (car l))
            (stampalista (cdr l)))))

Dico accademico perché il ciclo while esiste in molti dialetti di Lisp. E se non esiste è possibile definirlo. Alcuni dialetti del Lisp possono essere usati in modo totalmente imperativo e procedurale:

(defun stampaLista (list)
  (while list
    (print (car list))
    (setq list (cdr list))))

(Sul Lisp e sulla Tail Call optimization ci sarebbe molto altro da dire, mi ripropongo di farlo in seguito)

Viceversa una ricorsione è non-tail se la chiamata ricorsiva non viene eseguita per ultima. Una ricorsione non-Tail non è direttamente convertibile in un iterazione.

L’esempio canonico di ricorsione non-Tail è la sequenza di Fibonacci.
Com’è noto la sequenza di Fibonacci è definita nel caso generico come: Fib(n) = Fib(n-1) + Fib(n-2)

Il calcolo richiede quindi due chiamate ricorsive.

Vediamone l’implementazione in Lisp

(defun fib (n) 
(cond
 ((eq n 1) 0)
 ((eq n 2) 1)
 (T (+ 
 (fib (- n 1)) 
 (fib (- n 2))))))

Vediamone anche un implementazione in Java

int fib(n){
        if(n==1) return 0;
        if(n==2) return 1;
        return fib(n-1)+fib(n-2);
}

Spesso si cerca di convertire una ricorsione non-tail in una tail aggiungendo una funzione ausiliaria o delle variabili che passano valori alle chiamate successive.

In questo modo sarà possibile convertirla poi in iterazione ( o se si sta lavorando su linguaggio con la Tail Call Optimization si otterrà una ricorsione più veloce).

Cerchiamo di convertire il codice precedente

(defun _fib (n i j)
 (if (zerop n) i
 (_fib (1- n) j (+ i j))))
 
(defun fib (n) 
 (_fib n 0 1))

Ci siamo serviti di una funzione interna che funziona attraverso due variabili ausiliarie.
Questa implementazione ci permette di utilizzare una sola chiamata ricorsiva tail.
Convertiamo ancora una volta in Java

int _fib(int n, int i, int j){
        if(n==0)return i;
        return _fib(--n,j,i+j)
}

int fib(int n){
        return _fib(n,0,1);
}

Fine della digressione, torniamo a noi.

Torniamo al nostro caso adesso

Nel nostro caso le cose sono abbastanza complicate, infatti non solo non è una ricorsione tail, ma non è nemmeno un’approccio puramente ricorsivo. Infatti le colonne vengono percorse per iterazione mentre singole pedine piazzate per ricorsione.

public void generate(){
    int h=0;
    do{
        if(check(n, h)){
            iterazioni++;
            piazza(n,h);
            n++;
            if(n<8){
                generate();
            }
            else
                System.out.println(dump(scacchiera));
            n--;
            rimuovi(n,h);
        }
        h++;
    }while(h<8);
}

E quindi: come si affronta il problema nel caso di ricorsione non-Tail? o peggio ancora di ibridi ricorsione/iterazione?

In questo caso serve astrazione, non si può convertire il listato, si deve guardare al funzionamento dell’algoritmo e riformalizzarlo in modo iterativo. Dobbiamo proprio ripartire da come ci si muove sulla scacchiera e riscrivere l’algoritmo.

Possiamo riscrivere l’algoritmo in questo modo:

  1. Si parte da una configurazione vuota , la riga corrente è la prima, la colonna corrente è la prima.
  2. Dalla riga corrente e dalla colonna corrente si piazza una pedina nella prima posizione disponibile successiva alla colonna corrente, se è possibile, la colonna corrente è adesso la posizione dove si è piazzato.
  3. Se la 2 ha avuto successo e ci sono 8 piedine piazzate l’algoritmo ha trovato una configurazione valida, la si stampa.
  4. Se la 2 ha avuto successo si passa alla riga successiva, la colonna corrente sarà la prima e si ripete il punto 2.
  5. Se la 2 non ha avuto successo e ci si trova sulla prima riga l’algoritmo è concluso.
  6. si toglie una pedina, la riga corrente è la precedente, la colonna corrente è la colonna successiva a quella in cui si trovava la pedina si ripete il punto 2.

Notate che questa implementazione ci permette anche di separare in due l’algoritmo e di ottenere una configurazione per volta, infatti il punto 1 è il setup iniziale e I successivi l’algoritmo vero e proprio. Trattandosi di un algoritmo con backtrack inoltre ci servirà una qualche struttura a stack che nell’implementazione ricorsiva era implementata intrinsecamente dalla ricorsione mentre qui dovrà essere esplicita. Una volta riformulato in maniera iterativa l’implementazione in Java è diretta:

public void generate_iterative()  {
        boolean libero;
        int k,p;
        c = 0;
        n = 0;
        iterazioni=0;
        while (true) {
                libero = false;
                for (k = c; k < 8 && !libero; k++)libero = check(n,k);
                k--;
                if(libero){
                        iterazioni++;
                        push(n,k);
                        n++;
                        c=0;
                        if(n>=8)System.out.println(dump(scacchiera));
                }else{
                        if(n<1)return;//algoritmo concluso
                        p=pop();//rimuovo pedina;
                        c = 1 + p % 8;// parto a cercare dalla colonna dopo
                        n--;
                }
        }
}

Contando le iterazioni allo stesso modo del precedente otteniamo anche qui esattamente 1951 iterazioni per generare la 91 disposizione. Esattamente come doveva essere.

Le funzioni che abbiamo usato per gestire lo stack sono push() e pop() che sono definite in questo modo:

void push(int riga, int colonna) {
        piazza(riga, colonna);
        pedine.add(p(riga, colonna));
    }

    int pop() {
        int p = pedine.pop();
        rimuovi(p / 8, p % 8);
        return p;
    }

dove pedine è uno Stack.

Share Button

Lascia un Commento

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

Puoi usare i seguenti tag ed attributi HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>