211service.com
Il nuovo algoritmo può semplificare drasticamente le soluzioni al problema del 'flusso massimo'
Trovare il modo più efficiente per trasportare oggetti attraverso una rete come il sistema autostradale degli Stati Uniti o Internet è un problema che ha messo a dura prova matematici e informatici per decenni.
Per affrontare il problema, i ricercatori hanno tradizionalmente utilizzato un algoritmo di flusso massimo, noto anche come flusso massimo, in cui una rete è rappresentata come un grafo con una serie di nodi, noti come vertici, e linee di collegamento tra loro, chiamati bordi.
Dato che ogni bordo ha una capacità massima, proprio come le strade o i cavi in fibra ottica utilizzati per trasmettere informazioni su Internet, tali algoritmi cercano di trovare il modo più efficiente per inviare merci da un nodo all'altro del grafo, senza superare questi vincoli.
Ma poiché le dimensioni di reti come Internet sono cresciute in modo esponenziale, risolvere questi problemi utilizzando tecniche di calcolo tradizionali richiede spesso un tempo proibitivo, secondo Jonathan Kelner, professore associato di matematica applicata al MIT e membro del MIT's. Laboratorio di informatica e intelligenza artificiale (CSAIL).
Quindi, in un documento che sarà presentato al Simposio ACM-SIAM sugli algoritmi discreti a Portland, Oregon, questa settimana, Kelner e il suo collega Lorenzo Orecchia, un insegnante di matematica applicata, insieme agli studenti laureati Yin Tat Lee e Aaron Sidford, descriveranno un nuovo algoritmo teorico in grado di ridurre drasticamente il numero di operazioni necessarie per risolvere il problema del flusso massimo, rendendo possibile affrontare anche reti enormi come Internet o il genoma umano.
IMMAGINE: CHRISTINE DANILOFF / CON
Recentemente c'è stata un'esplosione nelle dimensioni dei grafici studiati, dice Kelner. Ad esempio, se volessi instradare il traffico su Internet, studiare tutte le connessioni su Facebook o analizzare i dati genomici, potresti facilmente ritrovarti con grafici con milioni, miliardi o addirittura trilioni di bordi.
I precedenti algoritmi di flusso massimo sono arrivati al problema un bordo, o percorso, alla volta, dice Kelner. Quindi, ad esempio, quando si inviano articoli dal nodo A al nodo B, gli algoritmi trasmettono parte delle merci lungo un percorso, fino a raggiungere la sua capacità massima, e quindi iniziano a inviarne alcuni lungo il percorso successivo.
Molti algoritmi precedenti, afferma Kelner, avrebbero trovato un percorso dal punto A al punto B, avrebbero inviato del flusso lungo di esso e quindi avrebbero detto: 'Dato quello che ho già fatto, posso trovare un altro percorso lungo il quale posso inviare di più?' Quando è necessario inviare flusso contemporaneamente lungo molti percorsi diversi, ciò porta a una limitazione intrinseca della velocità dell'algoritmo.
Ma nel 2011 Kelner, lo studente laureato CSAIL Aleksander Madry, lo studente universitario di matematica Paul Christiano e i colleghi della Yale University e della University of Southern California hanno sviluppato una tecnica per analizzare tutti i percorsi contemporaneamente.
I ricercatori hanno visto il grafico come una raccolta di resistori elettrici, quindi hanno immaginato di collegare una batteria al nodo A e una massa al nodo B e consentire alla corrente di fluire attraverso la rete. La corrente elettrica non sceglie un solo percorso, invierà un po' di corrente su ogni resistore della rete, afferma Kelner. Quindi sonda l'intero grafico a livello globale, studiando molti percorsi contemporaneamente.
Ciò ha permesso al nuovo algoritmo di risolvere il problema del flusso massimo sostanzialmente più velocemente rispetto ai tentativi precedenti.
Ora il team del MIT ha sviluppato una tecnica per ridurre ulteriormente il tempo di esecuzione, rendendo possibile l'analisi di reti anche gigantesche, afferma Kelner.
A differenza dei precedenti algoritmi, che consideravano uguali tutti i percorsi all'interno di un grafico, la nuova tecnica identifica quei percorsi che creano un collo di bottiglia all'interno della rete. L'algoritmo del team divide ogni grafico in cluster di nodi ben collegati e i percorsi tra di essi che creano colli di bottiglia, afferma Kelner.
Il nostro algoritmo individua quali parti del grafico possono facilmente indirizzare ciò di cui hanno bisogno e quali sono i colli di bottiglia. Ciò ti consente di concentrarti sulle aree problematiche e sulla struttura di alto livello, invece di dedicare molto tempo a prendere decisioni non importanti, il che significa che puoi utilizzare il tuo tempo in modo molto più efficiente, afferma.
Il risultato è un algoritmo quasi lineare, afferma Kelner, il che significa che la quantità di tempo necessaria per risolvere un problema è molto vicina all'essere direttamente proporzionale al numero di nodi sulla rete. Quindi, se il numero di nodi sul grafico viene moltiplicato per 10, la quantità di tempo verrebbe moltiplicata per qualcosa di molto vicino a 10, invece di essere moltiplicata per 100 o 1.000, dice. Ciò significa che si ridimensiona essenzialmente come potresti sperare con la dimensione dell'input, dice.
Shanghua Teng, un professore di informatica presso l'Università della California del Sud che non è stato coinvolto nell'ultimo documento, afferma che rappresenta un importante passo avanti negli algoritmi grafici e nei software di ottimizzazione.
Questo documento, che è il vincitore del premio per il miglior articolo alla conferenza [ACM-SIAM], è il risultato degli sforzi sostenuti da Kelner e dai suoi colleghi nell'applicazione di flussi elettrici per progettare algoritmi grafici efficienti, afferma Teng. Il documento contiene un'incredibile serie di contributi tecnici.