- Iscritto dal:
- 27 Ottobre 2018
- Messaggi
- 449
Algoritmi Greedy
Un paradigma in cui l'lgoritmo generico compie ad ogni passo la scelta più "golosa", ovvero la migliore possibile tra quelle disponibili in un determinato momento.
Usiamo knapsack (problema dello zaino), un esempio molto classico, immaginando di voler riempire il più possibile il nostro zaino di KG di oro.
Abbiamo a disposizione un peso massimo di 10 KG, e disponiamo di:
- Un lingotto da 7 KG
- Un lingotto da 5 KG
- Un lingotto da 4 KG
- Un lingotto da 3 KG
Il nostro algoritmo farà la scelta più golosa ad ogni passo, ovvero:
1. Scelgo il lingotto da 7 KG.
2. Mi avanzano 3 KG. Scarto quelli da 5 e da 4 KG perché non ci stanno, scelgo quello da 3 KG
3. Non ho più spazio, mi fermo.
Successo! Abbiamo riempito il nostro zaino al meglio possibile: abbiamo risolto un problema NP-Completo come knapsack.
Sull'onda dell'entusiasmo, permettetemi di effettuare una leggera modifica all'esempio precedente.
Peso massimo di 10 KG, materiale disponibile:
- Un lingotto da 8 KG
- Un lingotto da 5 KG
- Un lingotto da 4 KG
- Un lingotto da 3 KG
In questo caso, il mio algoritmo greedy effettuerà i seguenti passi:
- Scelgo il lingotto da 8 KG, in quanto il migliore disponibile.
- Mi restano 2 KG disponibili: ci sono altri lingotti adatti per riempire questo spazio? No
- Non ho più spazio per i lingotti disponibili, allora mi fermo.
Si tratta della soluzione migliore del nostro problema? NO.
Difatti, potevamo riempire in modo migliore il nostro zaino, scegliendo prima il lingotto da 5 KG e poi quello da 4 KG.
Ora, finché dovete riempire lo zaino immaginario delle fatine, potete sorridere e dire che questi problemi dell'informatica teorica sono tutti crucci mentali di qualche matematico che vuole incasinare il mondo. Immaginate però una grande compagnia di logistica, che fornisce un servizio di trasporto con navi cargo.
Provate ad usare la stessa logica greedy su knapsack in questa realtà: se il vostro algoritmo, che si occupa di disporre al meglio il carico nelle navi cargo, vi farà partire 120 navi al posto di 100, l'azienda avrà una netta riduzione del guadagno e massimizzazione del profitto.
Potete comprendere allora quanto la questione possa essere importante per tirare avanti la baracca.
Vi chiederete ora: come diamine faccio a sapere se allora possiamo risolvere un determinato problema con un algoritmo greedy?
Nell'informatica teorica, entra in gioco il concetto di matroide e il teorema di Rado; per i più curiosi e coraggiosi (purtroppo si entra in concetti matematici non comprensibili a chiunque in un lampo), lascio a voi l'approfondimento
Una piccola tips riguardo a knapsack: se al posto dei lingotti avessimo avuto una roba simile
- 8 KG di sabbia di oro
- 5 KG di sabbia di silicio (?)
- 4 KG di sabbia di polvere di stelle
- 3 KG di sabbia di sostanza sconosciuta
e il vostro obiettivo sia riempire sempre lo zaino, sapendo però che potete frazionare gli elementi dati (di quei 5 KG posso prenderne solo 2KG, essendo sabbia), allora l'approccio greedy funziona!
Nota curiosa: il noto algoritmo di Prim è un algoritmo greedy.
Ricorsione
L'idea è la seguente: si prende un problema, e scomporlo in sottoproblemi più semplici.
Un esempio è la sequenza di Fibonacci
Codice:
funzione fibonacci(int n){
if (n <= 1){
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}Come notate, questa funzione richiama sé stessa.
Come in un while, bisogna stare attenti a porre le giuste condizioni per le chiamate ricorsive e per la terminazione (nel codice, in questo caso è if n <= 1), altrimenti creeremo una computazione non terminabile.
La ricorsione è una tecnica molto usata, perché talvolta risolve problemi apparentemente complessi con poche righe di codice, in modo elegante e pulito.
Ad esempio, per effettuare un ordinamento basato sui confronti di un semplice array, un algoritmo molto efficiente è il mergesort, il quale sfrutta la ricorsione e impiega un tempo O(nlogn).
Gli svantaggi?
Immaginiamo che, generalmente, ogni chiamata ricorsiva vada allocata in memoria, e dunque occupi spazio.
Quando queste chiamate, per un motivo o per l'altro, si presentano più e più volte, stiamo iniziando a occupare spazio inutilmente e dilatando i tempi di computazione.
Se non hai capito, tranquillo: passa pure alla spiegazione della programmazione dinamica, la quale risolve questo problema.
Programmazione Dinamica
Non lasciatevi ingannare: non si tratta di un linguaggio di programmazione o altro, ma sempre di un paradigma di algoritmo.
Nello specifico, immaginate la programmazione dinamica come una sorta di "ricorsione con cicli for e while, in cui la complessità viene scaricata sulla memoria a favore della velocità di computazione".
Riprendiamo il nostro esempio sulla sequenza di Fibonacci
Codice:
funzione fibonacci(int n){
if (n <= 1){
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}Ora, potete implementare questa funzione in qualsiasi linguaggio di programmazione, e vedere che basta andare verso un numero "tranquillo" come il 20 che il vostro PC inizierà ad esplodere.
Qual è il problema?
Notate dal disegno che. il nostro programma, effettua un ricalcolo esagerato di valori già computati in precedenza
Contate quante volte rieseguiamo f(2) (fibonacci(2) sostanzialmente): come sarebbe comodo, invece, calcolare una sola volta tutti questi valori, memorizzarli e, all'occorrenza, tirare fuori il valore finale già calcolato - che è anche quello che farebbe una persona normale se dovesse fare i conti a mano, o sbaglio?
Ecco qui il codice di Fibonacci con la programmazione dinamica
Codice:
funzione fibonacciProgDinam(int n){
int f[] = new int[n+2];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++){
f[i] = f[i-1] + f[i-2];
}
return f[n];
}L'approccio teorico per passare da un algoritmo ricorsivo al paradigma della programmazione dinamica è molto più complicato di quanto si pensi: bisogna iniziare a pensare in termini di sottoproblemi, astraendo ciò che sta sotto a quel sottoproblema e arrivando infine alla soluzione poi del problema originale.
Oltretutto, certi problemi non è possibile risolverli così come sono posti, ma è necessario introdurre dei problemi ausiliari.
Non che sia nulla di spaventoso: in un corso universitario di algoritmi 2 o simili è un argomento ampiamente affrontato, in particolare con i grafi, ma spiegare ciò su un forum a chiunque passi mi viene un tantino difficile.
Euristiche
Abbiamo citato i problemi NP e NP-Completi, ma non li spiegheremo in questa sede.
In sostanza, vi basti sapere che generalmente, sono problemi a cui si pensa che non vi sia una soluzione ragionevole, ovvero che se cliccate col tasto sinistro il bottone RUN per eseguire l'algoritmo che risolve quel problema, il vostro PC inizierà a computare e vi darà la soluzione solo quando sarete morti.
Allora entrano in gioco due elementi: il primo di questi sono le euristiche.
Un euristica è, sostanzialmente, un algoritmo che è stato pensato per risolvere un problema specifico (knapsack, TSP, ecc...) in modo non esatto, ovvero che non mira a trovare a tutti i costi la soluzione migliore al problema, ma per ottenere almeno una buona soluzione, e soprattutto ottenerla in un tempo ragionevole.
Ribadisco che miriamo a trovare una "buona soluzione", e non "la soluzione" - ovvero il valore migliore che risolve quel problema.
Questo compromesso non esclude comunque che, con un algoritmo euristico, si possa comunque trovare la soluzione al problema; semplicemente, non c'è garanzia.
Metaeuristiche
Le metaeuristiche, a differenza delle euristiche, definisco delle tecniche di carattere generico, e che quindi non dipendono strettamente da un certo problema (delle black-box).
Detto in altri termini: "un algoritmo euristico è pensato per risolvere un problema specifico; una metaeuristica è una tecnica che usi per risolvere qualsiasi problema".
Serviamoci di un'immagine per fare uno step in più, con un'immagine presa totalmente a caso da internet
Immaginiamo che la nostra soluzione sia il pallino più alto, quindi verso il 29.
Segnatevi questa frase: "un euristica mi permette di trovare un ottimo locale".
Un po' di pazienza, con l'esempio capirete meglio
Immaginiamo di partire da 24, la nostra euristiche ci dice di fare uno step avanti se c'è qualcosa di meglio, altrimenti mi fermo e dico che quello è il migliore.
- Partiamo da 24, è il primo numero quindi è il migliore.
- Vado avanti, trovo il 25. Meglio del 24? Certo, quindi è lui il nuovo best, e lo memorizzo.
- Vado avanti, trovo il 26. Meglio di cosa avevo nel 25? Ceeerto, allora dimentico il precedente e memorizzo lui come nuova soluzione migliore.
- Vado avanti, trovo il 27. Meglio di cosa avevo nel 26? No, mi fermo.
La soluzione trovata migliore è il valore che c'è dove ho il 26.
Ecco, questa è l'essenza di cosa significhi trovare un ottimo locale: in base a dove parto, continuo a cercare di meglio; mi fermo quando trovo qualcosa di peggio.
Il problema di questo approccio è che, non accettando mosse peggiori, non posso "sfuggire" da quella prima montagnetta, per andare alla vetta più alta.
Resto intrappolato in un ottimo locale.
Le metaeuristiche mirano proprio a questo: le euristiche fanno il lavoro sporco a livello locale, mentre loro definiscono dei modi per sfuggire a questi ottimi locali, che si sa mai che l'ottimo globale sia da qualche altra parte - accettando anche mosse di peggioramento.
E come sono queste tecniche? Ci sono varie metaeuristiche, e devo dire che alcune sono davvero geniali e originali.
Una metaeuristica davvero interessante è il SA (simulated annealing), che trae spunto dal mondo metallurgico: essenzialmente, quando un certo metallo non è "perfetto", esso viene ricotto parzialmente e lavorato nuovamente, lasciandolo poi raffreddare; questa ricottura o rifusione viene eseguita altrettante volte, lasciando sempre raffreddare di più il metallo, fino a che non si ottiene il solido perfetto (o quasi).
E ciò viene applicato nel mondo degli algoritmi: la vostra temperatura è un semplice numero, che più è grande e più alza la probabilità (lasciamo perdere la formula) di accettare una soluzione peggiore; accettando così soluzioni peggiori e continuando a muovervi, posso trovare soluzioni migliori, e nel frattempo che miglioro diminuire lentamente la temperatura (= probabilità di accettare soluzioni peggiori); in questo modo mi avvicino sempre di più all'ottimo globale.
In particolare, è stato dimostrato che il Simulated Anealling converge all'ottimo globale - converge, non lo raggiunge per forza (diciamo che ci andiamo vicini).
Non è la sola metaeuristiche, ce ne sono tante altre (algoritmi genetici su tutti), e potete notare quanto l'uomo non abbia preso strade bizzarre e astratte, ma abbia tratto spunto dalla realtà che lo circonda.
Ora, per chiudere un attimo le fila, dato un problema (NP o NP-Hard) di nome Pippo e trovare una buona soluzione, voi prendete:
- Un algoritmo euristico di nome Paperino, che è stato progettato apposta per risolvere il problema Pippo
- Una metaeuristica di nome Paperina, che non è stata progettata appositamente per Pippo, ma è generale.
E il funzionamento avviene nel modo seguente:
1. Fate partire l'algoritmo da un punto di partenza (aka un valore di input specifico)
2. Paperino inizierà ad ottimizzare localmente, poi quando ha finito consegna la soluzione migliore trovata a Paperina
3. Paperina controllerà la bontà della soluzione trovata, e in base a certi altri parametri, dirà a Paperino di fermarsi qui, oppure di partire da un nuovo punto perché c'è ancora
margine di miglioramento.
4. Paperino sa che la soluzione da cui partire è peggiore di quella che ha trovato. SGRUNT! Ma sta zitto e ricomincia a ottimizzare localmente.
5. Si ritorna al punto 3, finché Paperina, la nostra metauristica, deciderà di fermare il tutto.
Piccola tips: in verità, in base al tipo di problema, ci potrebbero essere metauristiche migliore di altre.
Non perché alcune sono state progettate, come le euristiche, su appositi problemi, ma perché si può dedurre all'incirca come sarà lo spazio delle soluzioni di tale problema.
Cosa vuol dire?
Che se rappresento le mie soluzioni con un grafico, e in questo ci appaiono pochi ottimi locali e un bel ottimo globale, allora gli AG (algoritmi genetici) possono essere una soluzione migliore.
Al contrario, se questo grafico invece presenta tantissimi ottimi locali, il simulated annealling potrebbe essere una soluzione migliore.
Metaeuristiche
La discussione può essere allargata tranquillamente rispondendo a questo thread
Fonti ausiliarie: ringrazio Wikipedia <3
Ultima modifica: