Tecniche di progettazione di algoritmi

In questa lezione vedremo alcune delle tecniche principali di progettazione di algoritmi e quindi della programmazione indipendentemente dal linguaggio utilizzato. Queste tecniche hanno l’obiettivo di affrontare diversi scenari reali in cui dobbiamo risolvere un problema informatico ovvero computazionale in cui sono presenti delle strutture dati complesse ed è necessario trovare un algoritmo di complessità computazionale sufficientemente ridotta da poter essere codificato ed eseguito in tempi ragionevoli.

Molte 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.

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] e [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). 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] -> 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 ricalcolarla di nuovo. Questa può essere dal basso verso l’alto (come nel caso appena visto) o dall’alto verso il basso, in cui si memorizza ogni soluzione già individuata senza ricalcolarla, come avviene per esempio nel calcolo dei numeri di Fibonacci (il cui algoritmo è lasciato per esercizio).

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 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 parziale in quel momento migliore e procedere ricorsivamente con un sottoproblema.

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 ad ogni passaggio esiste una sola soluzione ottimale sia per quel passaggio (ovvero localmente) che per il problema in generale. Tuttavia non è sempre applicabile: ad esempio nel problema dello zaino non è possibile scegliere la soluzione localmente. 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 sono soluzioni localmente meno valide, avremmo ottenuto una soluzione globale migliore.

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à, ed in genere su utilizza 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.

Vogliamo ad esempio ottenere tutte le permutazioni dell’insieme {1,2,3} ovvero:

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

Dato un insieme di dimensione n, sono possibili n! permutazioni, ottenibili con la forza bruta con n cicli annidati, con un problema quindi di tipo NP.

Una soluzione con backtracking si procede nel seguente modo:

1. Parto da una lista vuota (un array vuoto)
2. Prendo il prossimo numero
3. verifico se è stato usato (uso un array)
4. se non è usato lo aggiungo alla lista e lo marco come usato
5. torno al punto 2

Qui il codice:

#include <iostream>
using namespace std;

#define n 3

void backtrack(int position, int solution[n], bool used[n]) {
	if (position == n) {
		for (int i=0; i<n; i++) {
		cout << solution[i] << " ";
	}
	cout << endl;
	} else {
		for (int i=0; i<n; i++) {
			if (!used[i]) {
				solution[position] = i+1;
				used[i] = true;
				backtrack(position+1, solution, used);
				used[i] = false;
			}
		}
	}
}

int main()
{
    int solution[n];
    bool used[n] = {0};
	backtrack(0, solution, used);

	return 0;
}

Un esempio è usato nella rete Internet, ovvero quello del trovare un percorso più veloce tra due nodi di un grafo: 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, che con la forza bruta richiede un tempo NP, tramite tentativi. Questi algoritmi si basano sull’individuare una soluzione buona, anche se non necessariamente ottimale, mediante tentativi. Ad ogni tentativo viene calcolata l’efficacia del risultato e se migliora faccio un nuovo tentativo con una soluzione che si basa sul precedente.

Un esempio di questi algoritmi sono gli algoritmi genetici, che prendono esempio dalla natura l’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 una funzione obiettivo, il cui valore indica la distanza dalla soluzione ottimale.
3. Vengono scelti i due migliori cromosomi (o anche più di due).
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. Col sistema genetico:

1. Si crea una prima generazione di percorsi casuali
2. Si calcolano i due percorsi minimi.
3. Si ricombinano (ad esempio metà di un percorso e metà di un altro)
4. Si introduce una mutazione
5. Si testano le nuove soluzioni
6. Si procede alla generazione successiva.

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”. 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.