Un nuovo algoritmo rende più veloce la ricerca dei percorsi più brevi

La versione originale di questa storia è apparsa su Quanta Magazine .

Se si vuole risolvere un problema complesso, spesso è utile organizzarsi. Ad esempio, si potrebbe suddividere il problema in più parti e affrontare prima quelle più semplici. Ma questo tipo di suddivisione ha un costo. Si rischia di perdere troppo tempo a mettere in ordine i pezzi.

Questo dilemma è particolarmente rilevante per uno dei problemi più iconici dell'informatica: trovare il percorso più breve da uno specifico punto di partenza in una rete a tutti gli altri punti. È come una versione potenziata di un problema che devi risolvere ogni volta che ti trasferisci: imparare il percorso migliore dalla tua nuova casa al lavoro, alla palestra e al supermercato.

"Quello dei percorsi più brevi è un problema affascinante con cui chiunque nel mondo può relazionarsi", ha affermato Mikkel Thorup , informatico dell'Università di Copenaghen.

Intuitivamente, dovrebbe essere più semplice trovare il percorso più breve per destinazioni vicine. Quindi, se si desidera progettare l'algoritmo più veloce possibile per il problema dei percorsi più brevi, sembra ragionevole iniziare trovando il punto più vicino, poi il successivo più vicino e così via. Ma per farlo, è necessario determinare ripetutamente qual è il punto più vicino. Si ordineranno i punti in base alla distanza man mano che si procede. Esiste un limite di velocità fondamentale per qualsiasi algoritmo che segua questo approccio: non si può procedere più velocemente del tempo necessario per l'ordinamento.

Quarant'anni fa, i ricercatori che progettavano algoritmi per il calcolo dei cammini più brevi si sono scontrati con questa "barriera di ordinamento". Ora, un team di ricercatori ha ideato un nuovo algoritmo che la infrange . Non ordina, ed è più veloce di qualsiasi algoritmo che lo faccia.

"Gli autori sono stati audaci nel pensare di poter superare questa barriera", ha affermato Robert Tarjan , informatico della Princeton University. "È un risultato sorprendente".

Per analizzare matematicamente il problema dei cammini più brevi, i ricercatori utilizzano il linguaggio dei grafi, reti di punti, o nodi, collegati da linee. Ogni collegamento tra i nodi è etichettato con un numero chiamato peso, che può rappresentare la lunghezza di quel segmento o il tempo necessario per attraversarlo. Di solito ci sono molti percorsi tra due nodi qualsiasi, e il più breve è quello i cui pesi sommati danno il numero più piccolo. Dato un grafo e uno specifico nodo "sorgente", l'obiettivo di un algoritmo è trovare il percorso più breve per ogni altro nodo.

Il più famoso algoritmo per i cammini più brevi , ideato dal pioniere dell'informatica Edsger Dijkstra nel 1956, parte dalla sorgente e procede passo dopo passo verso l'esterno. È un approccio efficace, perché conoscere il percorso più breve per i nodi vicini può aiutare a trovare i percorsi più brevi per quelli più distanti. Tuttavia, poiché il risultato finale è un elenco ordinato di cammini più brevi, la barriera di ordinamento pone un limite fondamentale alla velocità di esecuzione dell'algoritmo.

Illustrazione: Mark Belan, Samuel Velasco/Quanta Magazine

Nel 1984, Tarjan e un altro ricercatore migliorarono l'algoritmo originale di Dijkstra in modo che raggiungesse questo limite di velocità. Qualsiasi ulteriore miglioramento avrebbe dovuto derivare da un algoritmo che evitasse l'ordinamento.

Tra la fine degli anni '90 e l'inizio degli anni 2000, Thorup e altri ricercatori idearono algoritmi che superarono la barriera dell'ordinamento, ma avevano bisogno di fare alcune ipotesi sui pesi. Nessuno sapeva come estendere le loro tecniche a pesi arbitrari. Sembrava che fossero arrivati ​​al capolinea.

"La ricerca si è fermata per molto tempo", ha affermatoRan Duan , informatico presso l'Università Tsinghua di Pechino. "Molte persone credevano che non ci fosse un modo migliore".

Duan non era uno di loro. Aveva sognato a lungo di costruire un algoritmo di percorsi minimi in grado di superare la barriera dell'ordinamento su tutti i grafi. Lo scorso autunno, ci è finalmente riuscito.

L'interesse di Duan per la barriera di smistamento risale a quasi 20 anni fa, quando frequentava la scuola di specializzazione presso l'Università del Michigan, dove il suo relatore era uno dei ricercatori che avevano elaborato il modo di infrangere la barriera in casi specifici. Ma è stato solo nel 2021 che Duan ha ideato un approccio più promettente.

La chiave era concentrarsi su dove l'algoritmo andasse a finire a ogni passo. L'algoritmo di Dijkstra prende la regione che ha già esplorato nei passi precedenti. Decide dove andare successivamente scansionando la "frontiera" di questa regione, ovvero tutti i nodi connessi al suo confine. All'inizio, questo non richiede molto tempo, ma diventa più lento man mano che l'algoritmo procede.

Edsger Dijkstra ha ideato un algoritmo classico che trova il percorso più breve da un punto specifico di una rete a tutti gli altri punti.

Fotografia: Hamilton Richards

Duan immaginò invece di raggruppare i nodi adiacenti sulla frontiera in cluster. Avrebbe quindi considerato un solo nodo per ogni cluster. Con meno nodi da esaminare, la ricerca sarebbe potuta essere più veloce a ogni passaggio. L'algoritmo avrebbe anche potuto finire per andare in un punto diverso dal nodo più vicino, quindi la barriera di ordinamento non si sarebbe applicata. Ma garantire che questo approccio basato sul clustering rendesse effettivamente l'algoritmo più veloce anziché più lento sarebbe stata una sfida.

Duan sviluppò quest'idea di base nel corso dell'anno successivo e, nell'autunno del 2022, era ottimista di poter superare gli ostacoli tecnici. Coinvolse tre studenti laureati per aiutarli a elaborare i dettagli e, pochi mesi dopo, giunsero a una soluzione parziale : un algoritmo che superava la barriera dell'ordinamento per qualsiasi peso, ma solo sui cosiddetti grafi non orientati.

Nei grafi non orientati, ogni collegamento può essere attraversato in entrambe le direzioni. Gli informatici sono solitamente più interessati alla classe più ampia di grafi che presentano percorsi unidirezionali, ma questi grafi "orientati" sono spesso più difficili da navigare.

"Potrebbe verificarsi il caso in cui A possa raggiungere B molto facilmente, ma B non possa raggiungere A altrettanto facilmente", ha affermato Xiao Mao , uno studente laureato in informatica alla Stanford University. "Questo creerebbe un sacco di problemi".

Nell'estate del 2023, Mao ascoltò Duan parlare dell'algoritmo dei grafi non orientati a una conferenza in California. Intavolò una conversazione con Duan, il cui lavoro ammirava da tempo.

"L'ho incontrato per la prima volta nella vita reale", ha ricordato Mao. "È stato molto emozionante."

Dopo la conferenza, Mao iniziò a riflettere sul problema nel tempo libero. Nel frattempo, Duan e i suoi colleghi stavano esplorando nuovi approcci che potessero funzionare sui grafi orientati. Si ispirarono a un altro venerabile algoritmo per il problema dei cammini minimi, chiamato algoritmo di Bellman-Ford, che non produce una lista ordinata. A prima vista, sembrò una strategia poco saggia, poiché l'algoritmo di Bellman-Ford è molto più lento di quello di Dijkstra.

"Ogni volta che si fa ricerca, si cerca di seguire una strada promettente", ha detto Thorup. "Direi quasi che seguire la Bellman-Ford è anti-promettente, perché sembra la cosa più stupida che si possa fare".

Il team di Duan ha evitato la lentezza dell'algoritmo Bellman-Ford eseguendolo solo per pochi passaggi alla volta. Questo uso selettivo di Bellman-Ford ha permesso al loro algoritmo di individuare in anticipo i nodi più preziosi da esplorare nei passaggi successivi. Questi nodi sono come le intersezioni delle principali arterie stradali in una rete stradale.

"Bisogna attraversarli per trovare il percorso più breve verso molte altre cose", ha detto Thorup.

Nel marzo 2024, Mao pensò a un altro approccio promettente. Alcuni passaggi chiave dell'approccio originale del team avevano sfruttato la casualità. Gli algoritmi randomizzati possono risolvere efficacemente molti problemi, ma i ricercatori preferiscono ancora approcci non casuali. Mao ideò un nuovo modo per risolvere il problema dei cammini più brevi senza casualità. Si unì al team e lavorarono insieme nei mesi successivi tramite chat di gruppo e videochiamate per unire le loro idee. Infine, in autunno, Duan si rese conto che potevano adattare una tecnica da un algoritmo che aveva ideato nel 2018 che superava la barriera dell'ordinamento per un diverso problema di grafi. Quella tecnica era l'ultimo tassello di cui avevano bisogno per un algoritmo che funzionasse più velocemente di quello di Dijkstra sia sui grafi orientati che su quelli non orientati.

L'algoritmo finito suddivide il grafo in strati, muovendosi verso l'esterno a partire dalla sorgente come quello di Dijkstra. Ma invece di occuparsi dell'intera frontiera a ogni passo, utilizza l'algoritmo di Bellman-Ford per individuare i nodi influenti, avanza da questi nodi per trovare i percorsi più brevi verso gli altri e in seguito torna agli altri nodi di frontiera. Non sempre trova i nodi all'interno di ogni strato in ordine di distanza crescente, quindi la barriera di ordinamento non si applica. E se si suddivide il grafo nel modo giusto, l'algoritmo funziona leggermente più velocemente della versione migliore dell'algoritmo di Dijkstra. È considerevolmente più complesso, basandosi su molti pezzi che devono incastrarsi perfettamente. Ma curiosamente, nessuno di questi pezzi utilizza calcoli matematici sofisticati.

"Questa cosa avrebbe potuto essere scoperta 50 anni fa, ma non è stato così", ha detto Thorup. "Questo la rende ancora più impressionante."

Duan e il suo team intendono verificare se l'algoritmo possa essere semplificato per renderlo ancora più veloce. Una volta superata la barriera dell'ordinamento, il tempo di esecuzione del nuovo algoritmo non si avvicina a nessuno dei limiti fondamentali noti agli informatici.

"Essendo ottimista, non mi sorprenderei se riuscissi a ridurre ulteriormente il problema", ha detto Tarjan. "Non credo proprio che questo sia l'ultimo passo del processo".

Articolo originale ristampato con l'autorizzazione di Quanta Magazine , una pubblicazione editorialmente indipendente della Simons Foundation, la cui missione è quella di migliorare la comprensione pubblica della scienza, occupandosi degli sviluppi e delle tendenze della ricerca in matematica, scienze fisiche e della vita.