L'algoritmo semplice ed elegante che fa funzionare Google Maps

Quella degli algoritmi è una scienza che si basa sull'intelligenza: come naturale manifestazione di ragionamento logico—di induzione matematica, nello specifico—un buon algoritmo è come la fugace istantanea dell'essenza di un problema, dove proprietà e relazioni diventano semplici rapporti di reiterazione, che producono caos e complessità illimitati. E per penetrare una profonda complessità c'è bisogno di intelligenza.

Il pioniere della programmazione Edsger W. Dijkstra ha compreso a fondo questa cosa, e il suo omonimo algoritmo rimane uno degli elementi più ingegnosi delle scienze informatiche. Inflessibile difensore della semplicità e dell'eleganza nel mondo della matematica, pensava che ogni problema complicato avesse una base accessibile, e che in un certo era proprio la matematica era lo strumento per scoprirlo e servirsene.

Nel 1956, Dijkstra stava lavorando su ARMAC, un sistema per la computazione parallela presso il Centro di Matematica di Amsterdam. Era un successore di ARRA e ARRA II, che erano essenzialmente i primi computer mai costruiti nel paese. Il suo lavoro era di programmare il macchinario, e una volta che ARMAC fu pronto per essere presentato al pubblico, dopo due anni di duro lavoro, Dijkstra aveva bisogno di un problema da fargli risolvere.

"Perché una dimostrazione sia comprensibile anche per persone che non sono del settore c'è bisogno di un problema semplice," ha affermato Dijkstra in un'intervista rilasciata poco prima della sua morte nel 2002. "Quindi ho elaborato un programma che trova la strada più corta tra due città dell'Olanda, usando una mappa ridotta del paese sulla quale ho selezionato 64 città."

"Qual è il percorso più breve per andare da Rotterdam a Groningen?," si è chiesto Dijkstra. "Si tratta dell'algoritmo per la strada più breve, che ho elaborato in circa 20 minuti."

Ora c'è Google Maps a svolgere per noi questo compito, e raramente pensiamo a quanto sia complesso. Il problema del percorso più breve, fondamentale della teoria dei grafi e con applicazioni piuttosto ovvie nel mondo reale, va molto a fondo. Il suo risultato è conosciuto (informalmente) come "esplosione combinatoria", che è il punto in cui il numero delle diverse combinazioni esplorate in un dato problema cresce esponenzialmente.

Il risultato di questa esplosione è che i problemi, come i problemi del percorso più breve, crescono così velocemente da diventare praticamente incomputabili, richiedendo una quantità praticamente infinita di tempo per trovare una soluzione. C'è bisogno di alcuni nodi di una data mappa o di un grafo per calcolare il numero di possibili combinazioni, il che richiede un'enorme e irragionevole quantità di tempo.

Il modo più semplice per spiegare l'algoritmo di Dijkstra è probabilmente un esempio. Prendete il grafo qui sotto, dove i numeri rappresentano i pesi di ogni connessione. (Un peso può essere una semplice distanza o ogni costo relativo associato all'attraversamento di una particolare connessione che vogliamo minimizzare.) Per iniziare, poniamo s come la nostra posizione iniziale, con il valore di 0. Ci vogliono 0 km per arrivarci perché è appunto la posizione iniziale.

Nella prima iterazione guardiamo il nodo più vicino, che è a solo a 1 unità di distanza. Assegnamo un'etichetta al nodo con questo valore a, e guardiamo i nodi successivi e le loro rispettive distanze. b si trova a una distanza di 1 unità (2 dal punto d'inizio), c a una distanza di 2 unità (3 dal punto d'inizio) e abbiamo anche d, che si trova a una distanza di 2 unità dall'inizio. Dal momento che stiamo cercando il percorso più breve dall'inizio, dobbiamo muoverci da d a s (2 unità) e assegniamo il valore di 2 a d. Nell'iterazione successiva dell'algoritmo, da d passiamo poi a c, che si trova a una distanza di 10 unità (12 da s), ma consideriamo anche di partire da a, da cui possiamo arrivare a c in 2 unità (3 dal punto di inizio) e a b in 1 unità (2 dal punto di inizio). Stabiliamo il nostro prossimo avamposto in b e gli assegniamo valore 2 (2 mosse dal punto di inizio).

Il nostro esploratore immaginario piazzato in b non avrà successo. L'unico movimento possibile verso t è a distanza di 10 unità (12 dal punto di inizio). E sono più delle 2 unità da a a c (3 dall'inizio) e lo stesso valore di un viaggio da s a c attraverso d, una possibilità che ora possiamo scartare. Ora siamo a c e il prossimo passo è meno complesso di quanto sembra. Stiamo facendo semplicemente passi cauti e provvisori da un nodo all'altro, mentre siamo sempre obbligati dall'algoritmo di considerare sempre il percorso più breve dall'inizio.

Infine, guardiamo di nuovo da b a t, e notiamo che il percorso totale è di 12 unità. Allo stesso tempo, il salto finale da c costa 1, per una distanza complessivamente più corta di 4. E a questo punto, un problema incredibilmente complesso—quasi in maniera esplosiva—può essere risolto elegantemente, semplicemente e persino intuitivamente.

Altri esempi:

Dijkstra mi ha detto di aver avuto l'idea mentre sorseggiava un caffè su una terrazza. "Di fatto, l'algoritmo è stato pubblicato nel 1959, ben tre anni dopo. Una delle ragioni della sua eleganza è il fatto che l'ho pensato non avendo a disposizione carta e penna e sono stato praticamente obbligato a evitare fronzoli. Improvvisamente quell'algoritmo è diventato, con mia grande sorpresa, una delle pietre miliari della mia fama internazionale."

Questo è il meccanismo alla base di Google Maps. Il prodotto della mente di Dijkstra è proprio ciò che ci permette di trovare le strade così facilmente: quel tanto di intelligenza che basta a vedere un po' di luce in mezzo al buio.