I ricercatori dell'ETH sviluppano l'algoritmo di flusso più veloce possibile

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. Per essere precisi, 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 minimizzando i costi di trasporto?".

Immaginate di utilizzare la rete di trasporto 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 qualsiasi tipo di rete, sia essa ferroviaria, stradale, idrica o internet. Il suo algoritmo calcola così rapidamente da presentare la soluzione nel momento stesso in cui un computer ha letto i dati che descrivono la rete.

Calcola tanto velocemente quanto una rete è grande

Nessuno prima di Rasmus Kyng è riuscito a farlo. Anche se questo problema viene studiato 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.

Non è questo 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 era riuscito a calcolare più velocemente di m^1,5,dove m indica il numero di connessioni in una rete che il computer deve calcolare, e la sola lettura dei dati di rete richiede una sola volta m tempo. Dal 2004 in poi, il tempo di calcolo necessario per risolvere i problemi è stato ridotto a m^1,33 per ridurre i limiti di capacità. Con l'algoritmo di Kyng, il tempo di calcolo "aggiuntivo" necessario per ottenere una soluzione dopo la lettura dei dati della rete è ora semplicemente trascurabile.

Come una Porsche contro le carrozze a cavalli

I ricercatori dell'ETH 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 innovativo. In gergo tecnico, i nuovi algoritmi, quasi ottimamente veloci, sono noti anche come "algoritmi lineari veloci". La comunità dell'informatica teorica 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 supera le carrozze a cavalli. Il suo lavoro è stato premiato come miglior documento 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 i migliori del settore. lato esternoLe dieci più grandi scoperte del 2022 nell'informatica.

Da allora, i ricercatori dell'ETH 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, per esempio, o le amicizie umane.

Algoritmi fulminei 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 dell'ETH hanno sviluppato un ulteriore algoritmo che tiene conto anche della rimozione delle connessioni.

Questi algoritmi determinano i percorsi più brevi in reti in cui vengono aggiunti o rimossi collegamenti. 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 il percorso ottimale anche 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 reindirizzamento o una nuova costruzione - è di nuovo trascurabile.

Cosa rende esattamente il metodo di calcolo di Kyng così 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 team di Rasmus Kyng sta ora prendendo i rispettivi vantaggi di entrambi gli approcci e li combina in un approccio radicalmente nuovo. "Il nostro approccio si basa su molte piccole fasi di calcolo, efficienti e poco costose, che sono complessivamente molto più veloci di poche grandi", afferma Maximilian Probst Gutenberg, docente e collaboratore del gruppo di Kyng, che ha dato un contributo significativo allo sviluppo degli algoritmi a tempo quasi lineare.

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 di costo minimo globale. 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 '70, 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, dalla rotaia al flusso

Solo nel 2004 i matematici e informatici Daniel Spielman e Shang-Hua Teng, e più tardi Samuel Daitch, sono riusciti a scrivere algoritmi di questo tipo, che risolvono anche il problema del flusso a costo minimo in modo rapido ed efficiente. Furono anche loro a orientarsi sul flusso elettrico nella rete elettrica. Il loro cambio di prospettiva dalla ferrovia all'elettricità portò a una significativa differenza matematica: 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 verso una nuova connessione.

Questo reinstradamento parziale ha permesso a Spielman e ai suoi colleghi di calcolare tali 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". Questo calcolo parziale del percorso per iterazione ha contribuito notevolmente a velocizzare il calcolo complessivo del flusso.

Al punto di svolta delle basi teoriche

L'aspetto decisivo dei progressi compiuti dai ricercatori dell'ETH è che non si limitano allo sviluppo di nuovi algoritmi. Piuttosto, utilizzano e progettano anche 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.

Gli algoritmi di flusso significativamente più veloci non solo gettano le basi per la soluzione di problemi molto grandi che in precedenza erano impossibili da calcolare in modo efficiente, ma cambiano anche il modo in cui i computer calcolano i compiti complessi in primo luogo. "Negli ultimi dieci anni si è assistito a una rivoluzione nelle basi teoriche degli algoritmi provabilmente veloci per i problemi fondamentali dell'informatica teorica", lato esternoscrive un gruppo internazionale da ricercatori dell'Università di Berkeley, tra cui Rasmus Kyng e Deeksha Adil, ricercatore dell'Istituto di studi teorici dell'ETH di Zurigo.