Questa scoperta suona quasi come Lucky Luke, l’uomo che spara più veloce della sua ombra. Rasmus Kyng e il suo team hanno sviluppato un algoritmo superveloce che probabilmente cambierà un intero campo di ricerca. Infatti, il team di Kyng ha scritto un cosiddetto algoritmo di flusso di rete che risponde alla domanda: "Come si può ottenere il massimo flusso di traffico in una rete riducendo al minimo i costi di trasporto?".
Immaginate di utilizzare la rete di trasporti europea e di voler trovare il modo più veloce ed economico per trasportare il maggior numero possibile di merci da Copenaghen a Milano. In questi casi, l’algoritmo di Kyng calcola il flusso di traffico ottimale e più conveniente per ogni tipo di rete, sia essa ferroviaria, stradale, idrica o Internet. Il suo algoritmo calcola così rapidamente che presenta la soluzione nel momento stesso in cui un computer ha letto i dati che descrivono la rete.
Calcola tanto velocemente quanto è grande una rete
Nessuno prima di Rasmus Kyng era riuscito a fare questo. Anche se la ricerca su questo problema va avanti da circa 90 anni. Finora, il calcolo del flusso di traffico ottimale ha sempre richiesto molto più tempo dell’elaborazione dei dati di rete. Infatti, con l’aumentare delle dimensioni e della complessità di una rete, il tempo di calcolo richiesto è cresciuto molto più della dimensione effettiva del problema. Per questo motivo, esistono anche problemi di flusso nelle reti che sono troppo grandi per essere calcolati da un computer.Questo non è il caso di Rasmus Kyng: nel suo algoritmo, il tempo di calcolo aumenta allo stesso ritmo dell’aumento delle dimensioni della rete - è come quando si parte per un’escursione in montagna e la velocità di camminata non rallenta per un minuto, anche se il sentiero diventa sempre più ripido! Questo risultato si riflette nelle nude cifre: Fino all’inizio del nuovo millennio, nessun algoritmo riusciva a calcolare più velocemente di m1,5, dove m sta per il numero di connessioni in una rete che il computer deve calcolare - e la sola lettura dei dati di rete richiede m tempo. Dal 2004 è stato possibile ridurre il tempo di calcolo necessario per risolvere il problema a m1,33. Con l’algoritmo di Kyng, il tempo di calcolo "aggiuntivo" necessario per ottenere una soluzione dopo la lettura dei dati di rete è ora semplicemente trascurabile.
Come una Porsche contro le carrozze a cavalli
I ricercatori hanno così sviluppato l’algoritmo di flusso di rete teoricamente più veloce possibile. Rasmus Kyng e il suo team ne hanno fornito la prova matematica due anni fa in un documento rivoluzionario. In gergo tecnico, i nuovi algoritmi, quasi ottimalmente veloci, sono noti anche come "algoritmi lineari veloci". La comunità degli informatici teorici ha reagito in modo positivo ed entusiasta alla scoperta di Kyng.Il supervisore del dottorato di Kyng, Daniel A. Spielman, professore di matematica e informatica a Yale e lui stesso pioniere e decano in questo campo, ha paragonato l’algoritmo "assurdamente veloce" a una Porsche che sorpassa le carrozze trainate da cavalli. Il loro lavoro è stato premiato come miglior articolo all’"Annual IEEE Symposium on Foundations of Computer Science" nel 2022 e riconosciuto come un punto di forza dalla rivista di informatica "Communications of the ACM", mentre la rivista di divulgazione scientifica "Quanta Magazine" ha inserito l’algoritmo di Kyng tra le dieci più grandi scoperte dell’informatica nel 2022.
Da allora, i ricercatori hanno perfezionato il loro approccio e sviluppato altri algoritmi quasi lineari. Ad esempio, il primo algoritmo si riferiva ancora a reti statiche e immutabili le cui connessioni sono direzionali, cioè funzionano come le strade a senso unico delle reti stradali urbane. Gli algoritmi pubblicati quest’anno possono ora calcolare i flussi ottimali anche per reti che cambiano gradualmente nel tempo. La rapidità di calcolo è un passo importante, soprattutto per le reti molto complesse e ricche di dati che cambiano dinamicamente e molto rapidamente, come le molecole o il cervello in biologia, ad esempio, o le amicizie umane.
Algoritmi veloci per reti mutevoli
Giovedì Simon Meierhans, del team di Kyng, ha presentato un nuovo algoritmo veloce e a tempo lineare all’Annual ACM Symposium on Theory of Computing (STOC) di Vancouver. Questo risolve il problema del minimo costo-massimo flusso per reti che cambiano gradualmente con l’aggiunta di nuove connessioni. In un secondo lavoro, accettato dall’"IEEE Symposium on Foundations of Computer Science (FOCS)" il prossimo ottobre, i ricercatori hanno sviluppato un altro algoritmo che tiene conto della rimozione delle connessioni.Questi algoritmi determinano i percorsi più brevi, in particolare nelle reti in cui i collegamenti vengono aggiunti o rimossi. Nelle reti di trasporto reali, tali cambiamenti si verificano, ad esempio, quando la galleria di base del Gottardo viene chiusa prima completamente e poi parzialmente, come accade dall’estate del 2023, o quando una frana distrugge attualmente parte della strada nazionale A13, che è il più importante percorso alternativo alla galleria stradale del Gottardo.
Come fa un computer, un servizio di mappe online o un pianificatore di itinerari stradali a calcolare il collegamento più veloce ed economico tra Milano e Copenaghen in questi casi? I nuovi algoritmi di Kyng calcolano anche il percorso ottimale per queste reti che cambiano gradualmente in un tempo quasi lineare, cioè così rapidamente che il tempo di calcolo per ogni nuovo collegamento aggiunto - attraverso un nuovo percorso o una nuova costruzione - è di nuovo trascurabile.
Cosa rende il metodo di calcolo di Kyng molto più veloce di tutti gli altri algoritmi di flusso di rete? In linea di principio, tutti gli approcci di calcolo affrontano la sfida di dover calcolare la rete in diverse iterazioni per trovare il flusso ottimale e il percorso più favorevole. Nel farlo, calcolano le diverse varianti di quali connessioni sono aperte, bloccate o congestionate quando hanno raggiunto il loro limite di capacità.
Calcolare cosa? L’insieme o le sue parti?
Prima di Rasmus Kyng, esistevano due principali strategie di soluzione: una si basava sulla rete ferroviaria e calcolava un’intera sezione con un flusso di traffico modificato per ogni iterazione. L’altra si ispirava al flusso elettrico della rete elettrica. Calcolava l’intera rete per ogni iterazione, ma utilizzava valori medi statistici per il flusso modificato di una sezione al fine di calcolare più velocemente."Il nostro approccio si basa su molte piccole fasi di calcolo, efficienti ed economiche, che nel complesso sono molto più veloci di poche grandi fasi".
Il team di Rasmus Kyng sta ora prendendo in considerazione i rispettivi vantaggi di entrambi gli approcci e li combina in un approccio radicalmente nuovo. "Il nostro approccio si basa su molti piccoli passaggi di calcolo, efficienti e poco costosi, che nel complesso sono molto più veloci di pochi passaggi di grandi dimensioni", afferma Maximilian Probst Gutenberg, docente e membro del gruppo di Kyng, che ha dato un contributo significativo allo sviluppo degli algoritmi quasi lineari.
Uno sguardo alla storia della disciplina rivela ulteriori dimensioni del significato della scoperta di Rasmus Kyng: dopo tutto, i problemi di flusso nelle reti sono stati tra i primi a essere risolti sistematicamente con l’aiuto di algoritmi negli anni ’50, e gli algoritmi di flusso hanno svolto un ruolo importante nell’affermare l’informatica teorica come campo di ricerca a sé stante. Risale a questo periodo il noto algoritmo dei matematici Lester R. Ford Jr. e Delbert R. Fulkerson, che risolve in modo efficiente il problema del flusso massimo, ovvero come trasportare il maggior numero possibile di merci attraverso una rete senza superare i limiti di capacità dei singoli percorsi.
Non solo veloce, ma anche completo
Da allora è noto che gli importanti problemi di flusso di rete, come il problema del flusso massimo, il problema del costo minimo (il cosiddetto problema del trasbordo o del trasporto) e altri, sono in linea di principio casi speciali del problema del flusso completo a costo minimo. Prima di Rasmus Kyng, la maggior parte degli algoritmi riusciva a risolvere in modo efficiente solo uno di questi sottoproblemi. Tuttavia, non erano né particolarmente veloci né potevano essere estesi al più completo problema del flusso a costo minimo. Questo vale anche per i pionieristici algoritmi di flusso degli anni Settanta, per i quali gli informatici teorici John Edward Hopcroft, Richard Manning Karp e Robert Endre Tarjan hanno vinto il Premio Turing nel 1985 e nel 1986, che è considerato il premio Nobel dell’informatica.Cambio di prospettiva dalle rotaie all’elettricità
Solo nel 2004 i matematici e informatici Daniel Spielman e Shang-Hua Teng, e successivamente Samuel Daitch, sono riusciti a scrivere algoritmi che risolvessero in modo rapido ed efficiente anche il problema del flusso a costo minimo. Furono anche loro a orientarsi sul flusso elettrico nella rete elettrica. Il loro cambio di prospettiva dalla ferrovia all’elettricità ha portato a una differenza matematica significativa: se un treno viene deviato nella rete ferroviaria perché un percorso viene cancellato, può accadere che il successivo percorso migliore sia già occupato da un altro treno secondo l’orario. Nella rete elettrica, invece, è possibile che gli elettroni che formano il flusso di corrente vengano parzialmente deviati verso una connessione di rete attraverso la quale sta già scorrendo altra corrente. A differenza dei treni, la corrente può quindi essere matematicamente "parzialmente" spostata su un nuovo collegamento."Abbiamo scartato l’approccio di progettare gli algoritmi più potenti possibili per l’intera rete".
Questo reinstradamento parziale ha permesso a Spielman e ai suoi colleghi di calcolare questi cambiamenti di percorso molto più velocemente e allo stesso tempo di calcolare l’intera rete per ogni cambiamento. "Abbiamo rifiutato l’approccio di Spielman di progettare gli algoritmi più potenti possibili per l’intera rete", dice Rasmus Kyng, "invece abbiamo trasferito la sua idea di calcolo parziale del percorso agli approcci precedenti di Hopcroft e Karp". Il calcolo parziale del percorso per ogni iterazione ha accelerato notevolmente il calcolo del flusso complessivo.
Il punto di svolta delle basi teoriche
L’aspetto decisivo per i progressi dei ricercatori è che non si limitano allo sviluppo di nuovi algoritmi. Piuttosto, stanno anche utilizzando e progettando nuovi strumenti matematici che accelerano ulteriormente i loro algoritmi. In particolare, hanno sviluppato una nuova struttura di dati che organizza i dati di rete in modo tale che ogni modifica a una connessione nella rete possa essere trovata con estrema rapidità, contribuendo così alla soluzione algoritmica superveloce. Poiché esistono molte applicazioni per gli algoritmi quasi lineari e per strumenti come la nuova struttura di dati, è probabile che la spirale dell’innovazione giri molto più velocemente di prima.In ogni caso, gli algoritmi di flusso significativamente più veloci non solo gettano le basi per la risoluzione di problemi molto grandi che in precedenza non potevano essere calcolati in modo efficiente, ma cambiano anche il modo in cui i computer calcolano compiti complessi in generale. "Negli ultimi dieci anni c’è stata una rivoluzione nelle basi teoriche degli algoritmi provabilmente veloci per i problemi fondamentali dell’informatica teorica", scrive un gruppo internazionale di ricercatori dell’Università di Berkeley, tra cui Rasmus Kyng e Deeksha Adil, ricercatore presso l’Istituto di Studi Teorici del Politecnico di Zurigo.
Riferimenti
van den Brand, J, Chen, L, Kyng, R, Liu, YP, Meierhans, S, Probst Gutenberg, M, Sachdeva, S. Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality. 65° Simposio IEEE sui fondamenti dell’informatica (FOCS) 2024. https://focs.computer.org/2024/accepted-papers-for-focs-2024/Chen, L, Kyng, R, Liu, YP, Meierhans, S, Probst Gutenberg, M. Algoritmi a tempo quasi lineare per grafi incrementali: Cycle Detection, SCCs, s-t Shortest Path e Minimum-Cost Flow. Atti del 56° Simposio annuale ACM sulla teoria dell’informatica, giugno 2024 (STOC 2024). doi: https://doi.org/10.1145/3618260.3649745 .
Chen, L, Kyng, R, Liu, YP, Peng, R, Probst Gutenberg, M, Sachdeva, S, Kyng, R. Flusso massimo e flusso a costo minimo in tempo quasi lineare. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), Denver, CO, USA, 2022. doi: 10.1109/FOCS54457.2022.00064 .
