In questa lezione vedremo alcune delle principali tecniche di progettazione di algoritmi. Queste tecniche hanno l’obiettivo di affrontare problemi di natura computazionale in cui sono presenti delle strutture dati complesse (ad esempio matrici, liste, alberi, grafi) ed occorre trovare un algoritmo di complessità sufficientemente ridotta da poter essere codificato ed eseguito in tempi ragionevoli.

Alcune di queste vengono già utilizzate intuitivamente nella risoluzione di esercizi quando si impara un linguaggio di programmazione. Diventa però molto utile generalizzarle per individuare categorie di problemi comuni e quindi fare tesoro di problematiche simili in problemi nuovi.

Molte di queste tecniche fanno uso della ricorsione, che rivediamo rapidamente.

Ricorsione

Le funzioni ricorsive sono una classe di funzioni che prevedono nella loro definizione la chiamata a se stesse.  L’obiettivo di queste funzioni è quello di semplificare o suddividere il set di dati ricevuti come parametro e richiamare se stesse con un set di dati semplificato/ridotto, fino ad arrivare ad un caso base.

La struttura di una funzione ricorsiva è determinata da una condizione: 

1) caso base: se il parametro di input rispetta determinati requisiti, allora la funzione svolge il suo compito e restituisce quando previsto un risultato;

2) caso generale: se non rispetta i suddetti requisiti, la funzione chiama se stessa con parametri opportunamente modificati.

Nel diagramma sottostante uno schema di funzionamento generale di una funzione che chiama se stessa più volte fino ad arrivare ad un caso base.

Divide et impera

La tecnica del divide et impera consiste nel risolvere un problema computazionale tramite la sua scomposizione in sottoproblemi indipendenti più semplici e poi la sua ricomposizione in una soluzione unica. Per sua natura è una tecnica ricorsiva: ovvero si applica lo stesso algoritmo di suddivisione molte volte fino ad una dimensione minima dove si trova una soluzione per ciascun sottoinsieme, e poi si ricompongono le soluzioni a ritroso fino a trovare la soluzione generale.

Ipotizziamo ad esempio di voler trovare il massimo di un array di n elementi, per esempio:

[35, 21, 4, 16, 18, 71, 24, 36]

Col divide et impera dividiamo l’array in due parti:

[35, 21, 4, 16]
[18, 71, 24, 36]

e poi ancora:

[35, 21]
[4, 16]
[18, 71]
[24, 36]

fino ad array di un solo elemento:

[35]
[21]
[4]
[16]
[18]
[71]
[24]
[36]

A questo punto ricombiniamo gli array mettendo come primo elemento il più grande:

[35, 21]
[16, 4]
[71, 18]
[26, 24]

e procedo a ritroso:

[35, 16, 21, 4]
[71, 26, 18, 24]

ed infine:

[71, 35, 16, 21, 4, 26, 18, 24]

Questo sistema ha quindi un vantaggio di efficienza rispetto a quello di scorrere tutti gli elementi (scansione lineare), ovvero è O(log n) rispetto a O(n). Infatti se con 8 elementi si fanno 6 cicli (contro 7 di una ricerca lineare), già con 100 elementi i cicli sono 14 contro 99, con 1000 elementi sono 22 cicli contro 9999 e così via (scansione logaritmica).

Divide et impera è utilizzato anche nella ricerca binaria, in quicksort, mergesort ed in ogni altro algoritmo di calcolo dove è possibile suddividere un problema in sottoproblemi indipendenti.

Programmazione dinamica

La programmazione dinamica è simile al divide et impera: è quindi anche questa una tecnica di programmazione dove si divide un problema in sottoproblemi e poi si ricompone la soluzione. In questo caso però i sottoproblemi non sono indipendenti, ovvero tornando indietro si riutilizzano più volte le stesse sottosoluzioni.

Prendiamo ad esempio di avere uno zaino che può contenere fino a 10 kg e una serie di oggetti, ognuno con un peso e un valore specifici. 

• Oggetto A: peso 5 kg, valore 10€
• Oggetto B: peso 3 kg, valore 7€
• Oggetto C: peso 4 kg, valore 8€

L’obiettivo è massimizzare il valore totale degli oggetti nello zaino senza superare i 10 kg.

Applicando la programmazione dinamica, si crea una tabella dei sottoproblemi che memorizza in ogni riga una diversa combinazione di oggetti possibile che si può mettere nello zaino ed il valore complessivo, e poi si sceglie quella di maggior valore. Quindi:

1. [] -> 0
2. [A] -> 10
3. [A, B] -> 17
4. [A, B, C] -> 25 NON AMMESSA
5. [A, C] -> 18
6. [B, C] -> 7
7. [B] -> 10
8. [B, A] -> [A, B] (già calcolata)
9. [C] -> 8
10. [C, A] -> [A, C] (già calcolata)

Osservare come l’algoritmo aggiunge un oggetto alla volta, verifica se non è già stata utilizzata la combinazione (quindi vengono scartate [B,A] e [C, A]) ed indica che valore ha o se non è ammessa. Alla fine trova la soluzione ottimale.

Fondamentale in questi algoritmi la memorizzazione di tutte le sotto soluzioni per ricordarsi il valore della sottosoluzione senza ricalcolare di nuovo tutta quella porzione di albero. Di fatto quindi la programmazione dinamica produce un grafo di soluzioni: ovvero a differenza della programmazione dinamica, i cammini convergono a soluzioni già visitate.

Un altro noto esempio è il calcolo dei numeri di Fibonacci, che sebbene possa essere svolto anche con divide et impera, ha prestazioni ottimali con la programmazione dinamica.

La programmazione dinamica è una tecnica molto diffusa e si usa per molti algoritmi di calcolo, come per esempio l’individuazione del cammino minimo in un grafo o nel calcolo matriciale e differenziale.

Algoritmi Greedy

Gli algoritmi Greedy (traduzione letterale “algoritmi ingordi”) sono un altro tipo di algoritmi che cercando di trovare una soluzione ad un problema di ottimizzazione, ovvero di individuazione di una struttura dati ottimale a partire da un insieme di dati di input.

Si basa sempre sulla ricorsione, dove però la strategia utilizzata non è quella di cercare tutte le combinazioni possibili e scegliere quella migliore, ma di scegliere ad ogni passo la soluzione locale migliore e procedere ricorsivamente con il sottoproblema.

In altre parole l’algoritmo Greedy non “esplora” tutto il grafo, ma ad ogni passo sceglie la soluzione migliore per quel passo. Poi passa al passo successivo, e svolge la stessa scelta, fino al termine dell’algoritmo.

Poniamo di dover dare una certa somma usando banconote e monete, ad esempio 77 euro, cercando di utilizzare il minor numero di pezzi. Come noto i tagli disponibili sono 50, 20, 10, 5, 2 e 1 euro. L’algoritmo greedy sceglie ad ogni passaggio il pezzo più grande del totale restante e lo sottrae alla somma rimanente e poi procede ricorsivamente. Quindi:

1. 77 -> scelgo 50
2. 27 -> scelgo 20
3. 7 -> scelgo 5
4. 2 -> scelgo 2
5. 0 -> fine

In pratica il principio che guida l’algoritmo greedy è che presuppone che ad ogni passaggio esiste una sola soluzione ottimale sia per quel passaggio (ovvero localmente) che per il problema in generale.

Come fare a capire se un problema è risolvibile con un algoritmo Greedy? Per capirlo devono essere soddisfatti questi requisiti:

• deve essere definito un criterio di selezione rigido ad ogni passaggio della soluzione migliore (es. “il taglio più grande”);
• deve essere definita una funzione che verifica quali opzioni sono ammissibili (“sono esclusi i tagli maggiori del resto da dare”)
• deve essere definita una funzione di ottimizzazione (“il minore numero di monete/banconote”);
• devono essere presenti, ad ogni passo, più opzioni disponibili (es. i tagli di moneta) ordinate per valore;
• la scelta locale non deve “rovinare” le scelte successive. Una regola pratica è che il valore di ogni opzione deve essere almeno il doppio di quella successiva (potrebbero però esserci problemi Greedy che non la rispettano).

Come si può vedere, non è sempre applicabile: ad esempio nel problema dello zaino non è possibile scegliere la soluzione localmente, perché la scelta localmente migliore non è la scelta globalmente migliore. Ad esempio con questo zaino:

• Oggetto A: peso 8 kg, valore 10€
• Oggetto B: peso 3 kg, valore 7€
• Oggetto C: peso 4 kg, valore 8€

In questo caso Greedy ci farebbe scegliere l’oggetto A. Peccato che dopo non potremmo mettere nessun altro oggetto, mentre se avessimo scelto B o C, che sebbene siano soluzioni localmente meno valide, lo sono globalmente, in quanto ogni opzione disponibile non è ottenibile con una combinazione delle altre.

I problemi “greedy” sono quindi classi di problemi dove è garantito che la soluzione locale è sempre la migliore anche globalmente, cioè in tutte quelle strutture dati che non solo sono composte da sottostrutture indipendenti (come nel divide et impera) ma ogni soluzione di una sottostruttura deve essere valida anche per le altre sottostrutture (quindi l’esempio che abbiamo visto per il divide et impera non è greedy).

Gli algoritmi greedy hanno quindi una applicazione limitata, solo quando è dimostrabile questa proprietà, altrimenti occorre utilizzare la programmazione dinamica o il divide et impera.

Backtracking

L’algoritmo di backtracking si basa sul concetto di “esplorazione”. Dato un problema di calcolo, l’algoritmo cerca di trovare una soluzione tramite tentativi: se il tentativo ha successo, va avanti, se arriva ad una soluzione errata, “torna indietro” e cerca un’altra soluzione.

Un esempio è il problema del calcolo dei percorsi (Trovare i cammini in un grafo) o la risoluzione di un labirinto. Immaginiamo di voler andare dal punto A al punto D usando questa rete di strade:

• Da A posso andare a B o a C.
• Da B posso andare a C o a D (Arrivo).
• Da C posso andare a B o a D (Arrivo).

Se l’algoritmo non tenesse traccia degli stati già visitati, rimarrebbe intrappolato in un ciclo infinito tra B e C (A→B→C→B→C…).

Il backtracking invece ricorda il cammino percorso, e non riprende una strada già esplorata.

E’ usato nella rete Internet: si calcolano tutti i percorsi possibili tra due nodi del grafo, escludendo e scartando le soluzioni non valide o già visitate come non valide.

Programmazione euristica

La programmazione euristica si basa nel cercare di trovare una soluzione ad un problema molto complesso, tramite tentativi. Questi algoritmi si basano sull’individuare una soluzione buona non tramite esplorazione di tutto il grafo (impossibile perché troppo complesso) e senza avere la certezza che la soluzione locale sia globalmente ottima. Quindi la soluzione individuata non è necessariamente ottimale, ma si limita ad essere buona, cioè all’interno di un range di soluzioni considerate accettabili.

Deve essere presente una funzione, detta funzione obiettivo, che ad ogni passaggio minimizza la distanza dalla soluzione globale. Ad ogni tentativo viene calcolata l’efficacia del risultato e se migliora si fa un nuovo tentativo con una soluzione che si basa sulla precedente. In altri termini, l’algoritmo cerca di convergere localmente ad una soluzione globale, provando un insieme di opzioni disponibili e cercando quella che localmente sembra avvicinarsi di più a quella globale.

Un esempio di questi algoritmi sono gli algoritmi genetici, che prendono spunto dall’evoluzione.

La soluzione, chiamata cromosoma, viene costruita nel seguente modo:

1. Viene generato un insieme di cromosomi iniziali casuali
2. Ogni cromosoma viene valutato tramite la funzione obiettivo, il cui valore indica la distanza dalla soluzione ottimale.
3. Vengono scelti i due migliori cromosomi.
4. Questi cromosomi vengono ricombinati (crossover) per ottenerne di nuovi (nuova generazione)
5. Si inserisce una mutazione nei nuovi cromosomi per ottenere variabilità delle soluzioni.
6. Si ripete il punto 2.

Si prosegue di generazione in generazione fino a quando il miglioramento ottenuto dai cromosomi ad ogni nuova generazione è sotto una certa soglia, e quindi la soluzione è ottimale.

Ad esempio vogliamo risolvere il problema del commesso viaggiatore, ovvero individuare il cammino più breve tra un insieme di città. La soluzione a forza bruta consiste nell’esplorare tutte le soluzioni fino a trovare quella ottima ma come abbiamo detto è computazionalmente troppo complessa. Col sistema genetico:

1. Si crea una prima generazione di n percorsi casuali
2. Si calcolano i due percorsi minimi secondo la funzione obiettivo.
3. Se nessun percorso è sotto la soglia definita ottimale, si ricombinano (ad esempio prendendo metà di un percorso e metà di un altro) costruendone due nuovi.
4. Si introduce una mutazione che genera n nuovi percorsi
5. Si torna al punto 2

Gli algoritmi genetici, che sono un esempio di programmazione euristica, sono in generale più efficienti di una soluzione a forza bruta, ma necessitano di una funzione obiettivo (cioè un indicatore della bontà del tentativo in corso) e rischiano di trovare una soluzione che magari non è quella globalmente ottimale ma valida solo per un sottoinsieme dell’input dato rispetto a soluzioni “vicine”, detta “ottimo locale”. Il problema è legato al fatto che le mutazioni sono troppo piccole e quindi non si riesce ad esplorare tutto lo spazio delle soluzioni possibili.

Pertanto richiedono una buona conoscenza del problema e quindi una ottimizzazione dei parametri che gestiscono i tentativi (in particolare la mutazione e la funzione obiettivo).

Sono alla base di molti algoritmi di calcolo nelle reti, nell’analisi dati e nel machine learning.

Forza Bruta

Gli algoritmi basati sulla “forza bruta” sono utilizzati quando nessun altro sistema è possibile quando cioè non è possibile suddividere un problema in sottoproblemi, non c’è alcun backtracking da scartare, non ci sono funzioni obiettivo che ci dicono se ci stiamo avvicinando ad una soluzione ottima.

Un esempio è un algoritmo che cerca di individuare una password. Infatti:

• anche se indoviniamo un carattere della password non siamo in grado di testarlo localmente, quindi non è possibile fare divide et impera o programmazione dinamica e tantomeno greedy;
• non c’è modo di sapere se possiamo scartare uno o più caratteri, quindi non c’è backtracking;
• nessun tentativo ci aiuta ad avvicinarci alla soluzione.

In questo caso bisogna tentare tutte le strade possibili e solo una ci da la soluzione.

Questo tipo di problemi sono detti NP-completi, perché non solo si risolvono con un algoritmo con complessità esponenziale (come in tutti gli altri problemi che abbiamo visto sopra) ma questo è l’unico possibile.

Conclusioni

Le tecniche di programmazione sono strumenti che aiutano la progettazione di algoritmi la cui soluzione non è riconducibile ad un problema computazionalmente semplice da risolvere. Sono problemi che coinvolgono di solito strutture di dati complesse, come liste, alberi o grafi.

Possiamo schematizzarne l’uso in questi scenari:

• Divide et impera è efficace quando si può scomporre in sottoproblemi indipendenti;
• Programmazione dinamica sfrutta la sovrapposizione dei sottoproblemi, evitando il ricalcolo;
• Greedy è efficace quando la soluzione locale è valida anche globalmente
• Backtracking esplora tutte le soluzioni, ma scarta percorsi non validi
• Gli algoritmi euristici non garantiscono l’ottimalità ma se ben progettati danno una soluzione in tempi ragionevoli
• La forza bruta è sempre l’ultima risorsa, quando un problema non rientra negli altri casi.