Încetinirea rețelei ar putea fi în curând un lucru din trecut, datorită unui nou algoritm superrapid.
Descoperirea oferă o soluție dramatic mai rapidă la o problemă care a afectat oamenii de știință din computere încă din anii 1950: fluxul maxim sau modul de a obține cel mai rapid flux de informații printr-un sistem cu capacitate limitată.
Algoritmii anterioare de flux maxim au făcut progrese constante și incrementale, dar totuși au durat mai mult pentru a găsi fluxul optim decât pentru a procesa datele din rețea. Dar noua cercetare, prezentată pe 11 iunie la Proceedings of the 56th Annual ACM Symposium on Theory of Computingdetaliază un algoritm care poate rezolva problema aproximativ la fel de repede cât este nevoie pentru a scrie detaliile rețelei.
Problema debitului maxim este o piatră de temelie a științei algoritmice și a inspirat multe dintre cele mai semnificative progrese în domeniu. Prima încercare de a o rezolva a venit în 1956, când matematicienii Delbert Fulkerson și Lester Ford propus ceea ce ei au numit o „soluție lacomă” la întrebare.
Algoritmii greedy funcționează făcând cele mai imediate alegeri avantajoase în fiecare punct de-a lungul arborelui de decizie, alegând cea mai bună cale în fața acestuia, indiferent de rutele pe care le-ar putea bloca în viitor.
Imaginează-ți problema optimizarea traficului care se deplasează de la A la B de-a lungul mai multor căi posibile, un traseu fiind alcătuit dintr-un prim segment care este o autostradă cu șase benzi și cel din urmă un drum cu trei benzi. Pentru a rezolva acest lucru, algoritmul lacom va lansa cât mai mult trafic posibil (trei benzi de mașini) de-a lungul traseului, ajustându-și capacitatea și repetând aceiași pași pentru alte rute până când fiecare cale posibilă este la capacitate maximă.
Algoritmul lui Fulkerson și Ford s-a dovedit suficient de eficient, dar adesea nu a produs cel mai bun flux posibil: dacă alte rute au fost întrerupte și au apărut blocaje suboptime, așa să fie. Următorii 70 de ani de contribuții la problemă au încercat să perfecționeze acest aspect al soluției, netezind încetinirile inutile prin construirea unui proces decizional mai bun în algoritm.
Aceste ajustări au schimbat timpul de rulare al algoritmului de la un multiplu m^2 (unde m este numărul de noduri din rețea) la un multiplu de m^1,33 în 2004, dar apoi progresul a blocat.
Pentru a ajunge la descoperirea lor, cercetătorii studiului au combinat două abordări anterioare: soluția originală care a tratat rețelele ca trafic; și una ulterioară care le-a privit în schimb ca pe o rețea electrică. Spre deosebire de mașini sau trenuri, fluxul de electroni poate fi deviat parțial pentru a se alătura curentului de-a lungul unei alte rute, permițând informaticienților să cartografieze cel mai bun flux în întreaga rețea înainte de a se aplica abordarea traficului segment cu segment.
Combinarea acestor două abordări a dus la un algoritm hibrid care a fost „absurd de rapid”. Daniel A. Spielmanprofesor de matematică aplicată și informatică la Universitatea Yale, care a coordonat programul de doctorat al unuia dintre cercetători, a spus într-o declarație. Spielman a comparat noua soluție cu cele anterioare ca fiind ca „un Porsche care depășește trăsurile trase de cai”.
Odată perfecționat, noul algoritm ar putea fi aplicat unui număr de aplicații, inclusiv date de internet, programarea companiilor aeriene și îmbunătățirea eficienței piețelor, au spus cercetătorii.