Un algoritmo è comunemente definito come un procedimento che risolve un determinato problema tramite un numero finito di passi elementari. Analizziamo come funziona questo concetto fondamentale nell’informatica, cardine della fase di programmazione dello sviluppo del software e punto di partenza per le nuove tecnologie del futuro, dalla blockchain all’Intelligenza artificiale.
Prima di esaminare le possibili declinazioni di un algoritmo, è utile soffermarsi sulla natura del problema da risolvere. Dal punto di vista formale, un problema viene definito da una coppia input/output, dove l’input specifica la struttura dell’istanza del problema da risolvere e l’output una soluzione che soddisfa delle specifiche proprietà.
Algoritmo, il problema del commesso viaggiatore
Si consideri, ad esempio, il problema del commesso viaggiatore, in cui, dati un insieme di città, le strade che le connettono e i tempi di percorrenza media tra ogni coppia di città, si vuole trovare il tragitto con il minimo tempo di percorrenza che un commesso viaggiatore deve seguire per visitare tutte le città una ed una sola volta. In questo caso, l’input di una istanza del problema è costituito da un insieme di città, le strade di connessione e dai tempi di percorrenza tra queste, mentre l’output è costituito da ogni tragitto che tra tutti quelli che attraversano ogni città una e una sola volta ha il tempo di percorrenza minimo.
Un problema può presentarsi in alcune varianti, ognuna delle quali può richiedere soluzioni algoritmiche diverse. Si riportano alcune tra le varianti più significative.
Algoritmo: prima variante del problema
Nella prima variante, ogni elemento dell’istanza del problema è perfettamente noto. Ad esempio, nel caso del problema del commesso viaggiatore, questo vuol dire che sono note tutte le città, come sono connesse e i tempi di percorrenza.
Quando l’istanza di un problema è perfettamente nota, si hanno tre principali classi di algoritmi. La prima classe è costituita da algoritmi esatti, cioè algoritmi che restituiscono soluzioni ottime per il problema dato. Un algoritmo esatto viene utilizzato ogni qual volta il suo tempo di esecuzione è compatibile con l’applicazione. In particolare, si distinguono algoritmi che richiedono tempo polinomiale nella dimensione dell’istanza del problema da quelli che richiedono tempo esponenziale.
Nell’esempio del commesso viaggiatore, la dimensione dell’istanza è il numero di città ed è noto che è improbabile l’esistenza di un algoritmo esatto che richieda tempo polinomiale nel numero di città.
Algoritmi di approssimazione e stocastici
Problemi che non ammettono algoritmi esatti polinomiali sono detti difficili e, non potendo essere risolti in modo esatto entro un tempo compatibile con l’applicazione se non per piccole istanze, è necessario ricorrere ad algoritmi di approssimazione. Questi ultimi richiedono tempo polinomiale nella dimensione dell’istanza del problema e forniscono una garanzia teorica alla qualità della soluzione approssimata restituita. Nel caso del commesso viaggiatore, un algoritmo approssimato garantisce che la distanza di percorrenza totale della soluzione approssimata non è superiore, ad esempio, a due volte la distanza di percorrenza ottima. Qualora un algoritmo approssimato non fornisca alcuna garanzia teorica sulla qualità della soluzione è detto euristico. In molti problemi particolarmente difficili, è comune il fatto che non sia possibile costruire un algoritmo di approssimazione in tempo polinomiale con delle garanzie teoriche e quindi l’uso di tecniche euristiche risulta necessario.
Algoritmi esatti, di approssimazione ed euristici possono essere deterministici o stocastici. Un algoritmo esatto/di approssimazione deterministico restituisce una soluzione esatta/approssimata con probabilità 1. Invece, un algoritmo esatto/di approssimazione stocastico restituisce una soluzione esatta/approssimata con una certa probabilità inferiore ad 1. Solitamente gli algoritmi stocastici sono versioni ripetute di algoritmi deterministici parametrizzati in cui, ad ogni ripetizione (potenzialmente eseguita parallelamente alle altre), si usano parametri generati in modo casuale. Spesso capita infatti che diverse parametrizzazioni dello stesso algoritmo possono dare prestazioni radicalmente differenti su istanze diverse del problema e provando varie parametrizzazioni si può avere alta probabilità di trovare una buona parametrizzazione.
Un esempio è l’algoritmo Quicksort, il quale ordina gli elementi di un insieme in tempo quadratico nel numero di elementi, ma, se reso stocastico, in alta probabilità completa l’ordinamento in tempo quasi lineare.
Algoritmo: seconda variante del problema
La seconda variante del problema è quando alcuni elementi dell’istanza del problema non sono noti e non è possibile apprendere quell’informazione. Ad esempio, nel problema del commesso viaggiatore, la rete di strade che connette le città potrebbe non essere nota. In questo caso, l’algoritmo scopre le connessioni stradali accessibili da una città ogni volta che la città viene raggiunta e sulla base di questa informazione prende la decisione sul prossimo spostamento. Un tale algoritmo è detto online. Gli algoritmi online sono detti competitivi se forniscono garanzie teoriche rispetto al caso in cui l’informazione sia perfettamente nota. In altre parole, si vuole garantire che la mancanza di informazione non impedisca all’algoritmo di trovare una soluzione di qualità troppo peggiore rispetto a quella ottima.
Algoritmo: terza variante del problema
La terza variante del problema è quando alcuni elementi dell’istanza non sono noti ed è possibile apprendere quell’informazione. Ad esempio, nel problema del commesso viaggiatore, è necessario apprendere i tempi di percorrenza media tra ogni coppia di città. In questa variante, il problema viene dunque esteso rispetto alle prime due varianti, includendo sia l’apprendimento dell’informazione che la risoluzione del problema originale.
Possiamo distinguere tre casi. Nel primo caso, l’apprendimento è totalmente offline e un algoritmo userà una collezione di dati precedentemente raccolta per stimare l’informazione mancante.
L’algoritmo può poi essere model-based se include un modello matematico specifico il cui sono presenti dei parametri i cui valori sono da apprendere, oppure può essere model-free se usa tecniche black-box, ad esempio reti neurali.
La fase dell’apprendimento
Nell’esempio del problema del commesso viaggiatore, si ha apprendimento offline quando sono disponibili i dati di molti viaggi fatti nel passato. Nel secondo caso, l’apprendimento è online ed è possibile spendere un certo intervallo di tempo per apprendere ripetendo la soluzione del problema e successivamente usare le stime ottenute. Questo caso è detto di pure exploration.
Tipicamente, nella fase di apprendimento, l’obiettivo è generare il miglior insieme di dati per poter apprendere al meglio i parametri. Ad esempio, se il commesso viaggiatore è sicuro del tempo di percorrenza tra due città, si concentrerà nella fase di apprendimento a provare altre strade per migliorare le sue stime sui tempi di percorrenza tra queste.
L’aspetto caratterizzante è che, durante la fase di apprendimento, non c’è alcun interesse nell’usare soluzioni buone, ma solo nell’apprendere, mentre, una volta chiusa la fase di apprendimento, l’obiettivo è di usare la migliore soluzione possibile. Le garanzie fornite dagli algoritmi riguardano l’accuratezza delle stime, assicurando che in alta probabilità l’errore di accuratezza è inferiore a un certo margine.
Nel terzo e ultimo caso, l’apprendimento è online e non è possibile spendere tempo per apprendere prima di usare la soluzione, ma l’apprendimento è contestuale all’uso della soluzione. Questo caso è detto di exploration/exploitation e richiede di trovare il miglior compromesso tra l’esplorazione di nuovi dati e la scelta della miglior soluzione in accordo con i dati osservati precedentemente. Le garanzie fornite dagli algoritmi sono dirette a limitare la perdita di qualità delle soluzioni usate nel tempo dovuta al costo di apprendere l’informazione mancante.
