Gli algoritmi storici aiutano a sbloccare una svolta nel problema del percorso più breve

Algoritmi storici sbloccano svolta nel percorso più breve

.fav_bar { float:left; border:1px solid #a7b1b5; margin-top:10px; margin-bottom:20px; } .fav_bar span.fav_bar-label { text-align:center; padding:8px 0px 0px 0px; float:left; margin-left:-1px; border-right:1px dotted #a7b1b5; border-left:1px solid #a7b1b5; display:block; width:69px; height:24px; color:#6e7476; font-weight:bold; font-size:12px; text-transform:uppercase; font-family:Arial, Helvetica, sans-serif; } .fav_bar a, #plus-one { float:left; border-right:1px dotted #a7b1b5; display:block; width:36px; height:32px; text-indent:-9999px; } .fav_bar a.fav_de { background: url(../images/icons/de.gif) no-repeat 0 0 #fff } .fav_bar a.fav_de:hover { background: url(../images/icons/de.gif) no-repeat 0 0 #e6e9ea } .fav_bar a.fav_acm_digital { background:url(‘../images/icons/acm_digital_library.gif’) no-repeat 0px 0px #FFF; } .fav_bar a.fav_acm_digital:hover { background:url(‘../images/icons/acm_digital_library.gif’) no-repeat 0px 0px #e6e9ea; } .fav_bar a.fav_pdf { background:url(‘../images/icons/pdf.gif’) no-repeat 0px 0px #FFF; } .fav_bar a.fav_pdf:hover { background:url(‘../images/icons/pdf.gif’) no-repeat 0px 0px #e6e9ea; } .fav_bar a.fav_more .at-icon-wrapper{ height: 33px !important ; width: 35px !important; padding: 0 !important; border-right: none !important; } .a2a_kit { line-height: 24px !important; width: unset !important; height: unset !important; padding: 0 !important; border-right: unset !important; border-left: unset !important; } .fav_bar .a2a_kit a .a2a_svg { margin-left: 7px; margin-top: 4px; padding: unset !important; }

I pionieri dell’informatica Edsger Dijkstra hanno sviluppato algoritmi che costituiscono la base di molte subroutine informatiche, grazie alla loro elegante efficienza. Tuttavia, piccoli cambiamenti nei requisiti possono portare a formulazioni apparentemente semplici che non forniscono una risposta accurata. Gli algoritmi di sostituzione forniscono le risposte corrette ma spesso sono molto più lenti.

Un recente progresso nelle tecniche combinatorie ha dimostrato come questi primi algoritmi possano essere ripristinati.

I problemi del cammino più breve forniscono buoni esempi della sensibilità di un algoritmo alle specifiche dei suoi requisiti. Sono alla base di molte applicazioni, dalla navigazione alla progettazione di chip. Questi problemi presentano una semplice e basilare proposta: trovare il percorso attraverso una rete di percorsi diretti che offre il costo più basso in base ai pesi applicati a ciascun salto. Tale ponderazione può riflettere la distanza o il ritardo, proprietà che sono sempre positive nel mondo fisico.

• Grande lavoro di Scienza Applicata (dei Dati)
• Mappare il potenziale globale dei progetti di riforestazione naturale
• Il New York Times sta valutando di intentare una causa legale contro OpenAI

I problemi iniziano quando si incontra una rete simile in cui i percorsi possono avere pesi negativi. “Quando si affronta una situazione in cui i pesi degli archi corrispondono al costo, i pesi negativi sono naturali”, afferma Aaron Bernstein, professore associato di informatica presso la Rutgers University, New Brunswick, NJ.

Ad esempio, nel campo finanziario potrebbero presentarsi situazioni di negoziazione di valute o opzioni in cui l’acquisto e la vendita in una sequenza è più redditizio rispetto a un percorso diverso, e questi possono essere modellati utilizzando pesi negativi purché l’algoritmo di ricerca sia sufficientemente veloce. Ma quei pesi negativi possono mettere in difficoltà l’algoritmo del cammino più breve di Dijkstra.

Il problema risiede nell’avidità efficiente dell’algoritmo sviluppato a metà degli anni ’50: spesso esclude i percorsi con pesi negativi dalla considerazione. Elabora ogni vertice a turno e non torna indietro, quindi l’algoritmo potrebbe non considerare se un peso elevato combinato con uno che porta un peso negativo potrebbe risultare in un costo inferiore rispetto a un singolo salto con un peso basso.

Un approccio rivisto, spesso noto come algoritmo di Bellman-Ford, gestisce correttamente le connessioni con peso negativo, ma poiché si basa sulla capacità di elaborare i nodi, manca dell’efficienza diretta della tecnica di Dijkstra, che si completa in un tempo basato sulla somma del numero di nodi e connessioni. Bellman-Ford invece richiede molti più passaggi: il totale si basa sul prodotto del numero di nodi e vertici.

Anche se gli informatici hanno cercato di trovare soluzioni più efficienti al problema utilizzando tecniche combinatorie simili a quelle utilizzate in questi algoritmi di lunga data, non sono riusciti a ridurre significativamente il divario computazionale tra di loro. Negli ultimi decenni, sono stati fatti progressi maggiori rappresentando il grafo come coefficienti in una matrice e utilizzando gli strumenti dell’algebra lineare. Tali tecniche si sono dimostrate efficaci per una vasta gamma di problemi legati ai percorsi, non solo per identificare il percorso più breve, ma anche per applicazioni come massimizzare il flusso attraverso una rete di tubi o percorsi di trasporto, come dimostrato in un articolo presentato all’ultimo Symposium on Foundations of Computer Science (FOCS).

Li Chen, studente di dottorato presso il Georgia Institute of Technology, lavorando con matematici presso l’ETH di Zurigo, l’Università di Stanford e l’Università di Toronto, ha sviluppato un meccanismo basato sulla discesa del gradiente, lo stesso approccio fondamentale utilizzato per addestrare le reti neurali, per spostarsi progressivamente verso la migliore soluzione per massimizzare il flusso attraverso una rete. Questo algoritmo è riuscito a ridurre il tempo di calcolo quasi alla performance lineare.

Il lato negativo delle tecniche sviluppate di recente basate sull’ottimizzazione è che sono più difficili da implementare e comprendere rispetto agli algoritmi combinatori tradizionali. “Questo tipo di approccio spesso utilizza molti algoritmi dinamici, che tendono ad essere complicati. Coinvolgono molte parti in movimento che devi mettere insieme”, afferma Danupon Nanongkai, direttore e membro scientifico dell’Istituto Max Planck per l’Informatica a Saarbrücken, in Germania.

L’algoritmo di Bellman-Ford gestisce correttamente le connessioni con pesi negativi ma manca dell’efficienza grezza della tecnica di Dijkstra.

Bernstein, Nanongkai e Christian Wulff-Nilsen, professore associato di informatica presso l’Università di Copenaghen, volevano vedere se potevano trovare una soluzione combinatoria efficiente al problema del percorso più breve da una singola sorgente con pesi negativi.

Il team si è prima rivolto a un articolo degli inizi degli anni ’90 di Andrew Goldberg e colleghi che aveva ridotto la complessità alla radice quadrata del numero di vertici moltiplicato per il numero di nodi cercando di scalare i valori dei pesi per renderli positivi e consentire così di trovare il percorso più breve utilizzando l’approccio di Dijkstra. “L’obiettivo originale era solo quello di migliorare leggermente il risultato di Goldberg, ma alla fine si è scoperto che una volta che tutto era a posto potevamo andare fino in fondo”, afferma Nanongkai.

Una tecnica consolidata per la scalatura è l’uso di funzioni di prezzo, anche se può essere difficile assegnare prezzi in modo efficiente e in modo che non distorcano la relazione tra i pesi. Il team ha trovato un algoritmo efficiente che funzionava su un tipo specifico di grafo: quelli con un diametro basso. Questo si è rivelato la chiave per una scoperta più grande e che potrebbe aiutare a trovare soluzioni combinatorie più efficienti ad altri problemi.

I grafi a basso diametro sono strutture in cui i percorsi sono brevi e possono essere visti come fortemente collegati tra loro. La proprietà del basso diametro è stata un componente chiave per trovare modi per suddividere i grafi in sezioni in modo che l’elaborazione possa essere distribuita su più computer. Assicurare che i componenti fortemente connessi siano mantenuti sulla stessa macchina aiuta a ridurre al minimo il traffico di rete.

Il team ha scoperto che era possibile dividere il grafo di input in cluster di sottografi a basso diametro, e poi rielaborare progressivamente i pesi utilizzando una serie di funzioni di prezzo per costruire un grafo ristrutturato che potesse essere elaborato quasi completamente utilizzando l’algoritmo di Dijkstra. Questo ha comportato la rimozione casuale di percorsi con pesi negativi che avrebbero permesso al grafo di origine di essere convertito in un grafo aciclico diretto: uno con solo percorsi in avanti e senza loop che collegano i cluster fortemente connessi tra loro. Questa forma è stata selezionata perché ha aperto la porta a strumenti che avrebbero consentito l’uso dell’algoritmo più veloce. Una fase successiva reintroduce poi i bordi mancanti con pesi negativi. Il ridotto numero di questi percorsi può essere elaborato utilizzando l’algoritmo di Bellman-Ford con un impatto relativamente ridotto sul tempo di esecuzione.

Anche se una forma di decomposizione a basso diametro costruita per i grafi diretti si è rivelata fondamentale per la soluzione, Bernstein afferma che non era immediatamente evidente come la decomposizione tradizionale fosse stata sviluppata per i grafi non diretti. “Quando abbiamo iniziato a guardarlo, non era chiaro cosa significasse la decomposizione a basso diametro in questo contesto e non ci è venuto in mente che potesse essere una nozione rilevante. È stato solo perché abbiamo iniziato a lavorare da una direzione diversa e abbiamo scoperto di avere a che fare con grafi collegati alla proprietà del basso diametro che abbiamo iniziato a vedere come poteva essere utilizzata”, afferma.

La decomposizione ha reso possibile suddividere i calcoli delle funzioni di prezzo in diversi passaggi, e farlo in modo efficiente senza rischiare la distorsione che un approccio a singolo passaggio avrebbe imposto.

“In un certo senso, quello che il nostro algoritmo sta facendo è decomporre il grafo, risolvere le cose con pochi pesi di bordo negativi, fissare quelli e poi passare al passo successivo, cercando progressivamente di rendere le cose sempre meno negative”, aggiunge Bernstein.

L’algoritmo di base ha diversi elementi con una dipendenza logaritmica dal numero di vertici nel grafo, ognuno dei quali rappresenta spazio per miglioramenti.

Wulff-Nilsen nota: “Questo miglioramento progressivo avviene cambiando gli archi utilizzando più volte le funzioni di prezzo. Quindi, non è come se trovassimo solo un punto di prezzo.”

Il risultato è stato un algoritmo con prestazioni quasi lineari e con una leggermente migliore performance rispetto alla tecnica di ottimizzazione del flusso massimo presentata da Chen nello stesso evento FOCS dell’anno scorso. Entrambi hanno condiviso il premio come miglior articolo al simposio, e diversi insegnanti hanno successivamente incorporato l’algoritmo combinatoriale e i colleghi nelle loro lezioni a causa della sua relativa semplicità.

Anche se l’algoritmo di base è quasi lineare, ha diversi elementi che dipendono in modo logaritmico dal numero di vertici nel grafo, ognuno dei quali presenta spazio per miglioramenti. Karl Bringmann e Alejandro Cassis dell’Università di Saarland si sono uniti a Nick Fischer dell’Istituto Weizmann di Scienza in Israele e sono riusciti a ottimizzare sei dei otto fattori logaritmici in un articolo pubblicato ad aprile. Alcuni di essi sono stati considerati semplici, come cambiare l’ordine in cui gli elementi vengono presentati all’algoritmo di Dijkstra sottostante, ma altri erano “più complessi”.

Nel loro lavoro, Bringmann e colleghi hanno sviluppato quella che descrivono come una forma più diretta di decomposizione per il loro algoritmo più efficiente, insieme a una forma diversa di decomposizione a basso diametro che non hanno utilizzato per questo particolare problema.

Tali approcci potrebbero rivelarsi utili anche per grafi diretti come la decomposizione a basso diametro è stata utile per il lavoro con grafi non diretti. “Credo che le persone fossero entusiaste nel vedere che la decomposizione a basso diametro potesse essere utilizzata in questo modo. Ci hanno parlato tutti di utilizzarla per altri problemi con grafi diretti”, afferma Bernstein.

Tornando alla decomposizione a basso diametro, Bernstein, Nanongkai e altri hanno pubblicato un articolo a marzo che dimostra un algoritmo distribuito per il calcolo dei cammini minimi. Tuttavia, trovare soluzioni combinatorie efficienti per problemi come la massimizzazione del flusso rimane una sfida difficile, e nonostante la maggiore complessità e la dipendenza da tecniche che richiedono la manipolazione di strutture dati dinamiche, gli approcci basati sull’ottimizzazione rimangono strumenti chiave per l’informatica.

Bernstein osserva: “Le tecniche di ottimizzazione sono davvero l’unico modo che conosciamo per risolvere alcuni problemi. Il nostro algoritmo ha mostrato una soluzione combinatoria per un problema, ma è ancora un problema particolare. Ad esempio, per il flusso a costo minimo, non abbiamo ancora un’idea di come farlo in modo combinatorio.”

Approfondimenti

Bernstein, A., Nanongkai, D., e Wulff-Nilsen, C. Negative-Weight Single-Source Shortest Paths in Near-Linear Time Proceedings of the 63 rd IEEE Annual Symp. on Foundations of Computer Science (2022), 600–611

Chen, L., Kyng, R., Liu, Y.P., Peng, R., Probst Gutenberg, M., e Sachdeva, S. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time Proceedings of the 63 rd IEEE Annual Symp. on Foundations of Computer Science (2022), 612–623

Bringmann, K., Cassis, A., e Fischer, N. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! ArXiv 2304.05279 (2023)

Linial, N. e Saks, M. Low-Diameter Graph Decompositions Combinatorica 13 (4) (1993) 441–454

Torna all’inizio

Autore

Chris Edwards è uno scrittore con sede a Surrey, nel Regno Unito, che si occupa di elettronica, IT e biologia sintetica.

©2023 ACM  0001-0782/23/8

È concessa l’autorizzazione a copiare digitalmente o su supporto cartaceo parte o tutto questo lavoro per uso personale o didattico senza alcun costo a condizione che le copie non siano fatte o distribuite a scopo di lucro o vantaggio commerciale e che le copie riportino questa notifica e la citazione completa sulla prima pagina. Il copyright per i componenti di questo lavoro di proprietà di terzi diversi da ACM deve essere rispettato. È consentito l’abstracting con accredito. Per copiare altrimenti, per ripubblicare, per pubblicare su server o per distribuire in elenchi, è necessario ottenere il permesso specifico e/o il pagamento anticipato. Richiedere autorizzazione alla pubblicazione a [email protected] o via fax al numero (212) 869-0481.

La biblioteca digitale è pubblicata dall’Associazione per la Macchina di Calcolo. Copyright © 2023 ACM, Inc.