Tecniche di Programmazione : Backtracking

In questo post ho cercato di scrivere quello che avevo capito di una delle tecniche di programmazione più usate, il backtracking, basandomi sugli appunti presi a lezione, informazioni sul web e alcuni libri di testo. Scusatemi per la formattazione, ma ho copiato e incollato da un documento di testo che avevo scritto e sono troppo pigro per riformattarlo a regola d'arte. Per qualsiasi suggerimento o altro lasciate un commento o contattateci!

Principio:

La tecnica del backtracking è, per certi versi, un’ottimizzazione della ricerca esaustiva (o brute force) che prova tutte le possibili soluzioni “sensate” di un problema. Proprio il termine “sensate” fa la differenza con la tecnica di brute force: il backtracking pone dei vincoli in ogni suo passo, così da far diminuire i tempi della brute force. Dunque il backtracking elimina le strade che nel loro stato presentano già una scorrettezza, mentre la brute force esamina ogni combinazione possibile e verifica la sua esattezza solo dopo aver generato la pseudo-soluzione. Questa tecnica intraprende una strada che sembra corretta, non appena si rende conto che la soluzione diventa scorretta, l'algoritmo smette di andare avanti e torna in uno stato precedente, quando la soluzione era ancora giusta. Per capire bene il funzionamento del backtracking si ci può riferire a un albero, visitato in profondità per arrivare alla soluzione, dove a ogni livello corrispondono X nodi interni che rappresentano i valori delle sotto soluzioni: se si arriva ad una foglia significa che si è trovata la soluzione; se, nell'andare avanti nei nodi, i vincoli imposti risultano violati o non si può più procedere, si ritorna al nodo padre per poter scegliere un altro figlio e quindi intraprendere una nuova strada. Il processo si blocca se si trova una soluzione o si provano tutte le strade disponibili senza arrivare alla soluzione.

Per poter applicare il backtracking si devono verificare delle condizioni:

• Lo spazio delle soluzioni dev’essere finito
• La soluzione può essere rappresentata mediante soluzioni parziali
• La dimensione della soluzione finale S è nota
• Il valore di ogni sotto soluzione dev’essere finito

Introduciamo lo pseudo-codice per il backtracking (versione ricorsiva)

E' utile definire un tipo enumerativo per elencare i valori delle sotto-soluzioni:

enum valori { MIN_VAL, MED_VAL, […] , MAX_VAL}

Lista che salva le sotto-soluzioni che assieme daranno la soluzione finale:

lista sottoSoluzioni { }

bool solve ( lista sottoSoluzioni )

x ß minVal

while (x <= MAX_VAL) {

      if (canAdd (x,sottoSoluzioni) ) {

           add (x,sottoSoluzioni) )

           if ( isComplete (sottoSoluzioni) )

               return true

           else

               if ( solve(sottoSoluzioni) )

                   return true

           remove(x,sottoSoluzioni)

           x = next(x)
      }

else

    x = next(x)
}

return false

La funzione solve rappresenta il backtracking: parte con il primo valore del nostro insieme che aggiunge alla lista di sotto-soluzioni se è conforme ai nostri vincoli (dettati dalla funzione canAdd). La funzione add ha il compito di aggiungere il nostro x alla lista delle sotto-soluzioni. isComplete ci informa se la lista di sotto-soluzioni è completa, dunque se abbiamo raggiunto la soluzione finale, se ciò non dovesse accadere viene richiamata la funzione solve ricorsivamente con la nuova lista di sotto-soluzioni aggiornata al valore x appena aggiunto. Se ci accorgessimo che nessun valore di x è in grado di soddisfare i vincoli e che quindi non possiamo più continuare con questa strada, ritorniamo false che fa fallire la condizione if (solve) e che dunque provvederà a rimuovere la x prima inserita, dato che i suoi nodi figli non permettono di continuare verso la soluzione (passo di backtrack, torniamo indietro modificando l'ultimo valore inserito). Il ciclo si ripete fin quando non abbiamo provato tutti i valori possibili di x e le varie strade senza trovare una soluzione (quindi restituendo false) o trovando una strada che ci conduce alla risoluzione del problema(quindi restituendo true in un qualsiasi punto del programma in cui tutte le chiamate ricorsive su solve restituiranno true o sarà soddisfatta la chiamata a isComplete).

Esempio: Problema delle otto regine

Animazione presa da Wikipedia

Il problema ci chiede di sistemare otto regine in una scacchiera 8x8. La posizione delle otto regine dev'essere tale da non permettere a nessuna regina di "attaccarne" un'altra.

Si può notare che possiamo risolvere il problema provando tutte le combinazioni possibili delle regine, ma si può ottimizzare usando il backtracking, posizionando, cioè, le regine in modo "intelligente" e non in tutti i modi possibili. Qualora una posizione non dovesse andare più bene si torna indietro e si modifica la regina precedente.

Usiamo un array di interi per rappresentare la soluzione, che avrà esattamente 8 indici di colonna (assumiamo che gli indici di riga siano uguali al numero della regina: regina 1 -> riga 1 ecc, dato che le regine sulla stessa riga possono attaccarsi).

Le nostre sotto soluzioni varieranno da 1 a 8 (indici di colonna).

Utilizziamo un indice (ultimaPosValida) facente parte dell' array di sotto-soluzioni che ci tiene traccia dell'ultima regina posizionata correttamente.

Applichimo lo pseudo-codice del backtracking:

bool isComplete ( sottoSoluzioni )

return sottoSoluzioni.ultimaPosValida == numeroRegine;

int next ( x )

return x+1;

void remove ( x, sottoSoluzioni)

sottoSoluzioni.ultimaPosValida --;

void add (x, sottoSoluzioni)

sol.ultimaPosValida ++;

sol.valori[sol.ultimaPosValida] = x;

bool canAdd (x,sol)

int currRig = sol.ultimaPosValida +1;

int currCol = x;

for ( int precRig = 1; precRig < currRig; precRig ++)

int precCol = sol.valori[precRig];

if ( currCol == precCol OR currRig - precRig == abs ( currCol - precCol) ) return false

return true

La funzione canAdd memorizza su currRig la riga della regina che si vuole posizionare, che sarà uguale alla riga della regina precedente già posizionata più uno (essendo le righe uguali al numero delle regine come detto sopra). currCol invece memorizzerà l'indice della colonna che dobbiamo "verificare". Il for cicla tutte le righe precedenti all'attuale e memorizza di volta in volta le colonne ad esse associate (in sostanza ad ogni ciclo abbiamo riga e colonna della regina memorizzata nel nostro array di sotto-soluzioni). Con il controllo if che segue, verifichiamo che la regina che stiamo inserendo non sia sulla stessa colonna o su una diagonale della regina precedente in esame ( precRig e precCol -> posizione regina precedente). La formula currRig - precRig == abs (currCol - precCol) indica proprio il controllo atto a verificare se le regine R1(precRig,precCol) ed R2(currRig,currCol) si possono attaccare diagonalmente. La funzione abs restituisce il valore assoluto: essa è applicata in currCol - precCol perché non sappiamo quale delle due colonne sia la maggiore, cosa che non si verifica per precRig e currRig dato che sappiamo che la regina Ri avrà numero di riga maggiore ad Ri-1 per convenzione.