Un algoritm „absurd de rapid” a rezolvat o problemă de trafic veche de 70 de ani. Cum funcționează

Publicat: 4 august 2024, 8:12 / Actualizat: 4 august 2024, 10:53
Reclamă

Încetinirea rețelelor, fie că vorbim de date sau de zboruri, ar putea fi rezolvată cu ajutorul unui nou algoritm extrem de rapid. Descoperirea oferă o soluție mult mai rapidă la problema pe care experții încearcă să o rezolve încă din anu 1956. 

De aproape 70 de ani, cercetătorii au încercat să găsească o soluție pentru un flux maxim. Adică cel mai rapid flux de informații care poate să treacă printr-un sistem cu o capacitate limitată, scrie Live Science. 

Algoritmii din trecut pentru flux maxim au avansat soluția, dar niciodată la acest nivel.

ARTICOLUL CONTINUĂ DUPĂ RECLAMĂ

Un algoritm „absurd de rapid” a rezolvat o problemă de trafic veche de 70 de ani

Noua cercetare a fost prezentată recent în cadrul Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 

Studiul detaliază un algoritm „absurd de rapid” ce poate rezolva problema la o viteză aproape egală cu introducerea detaliilor despre rețea. Adică aproape instant după ce deține datele necesare calculului.  

Reclamă
Reclamă

Problema fluxului maxim reprezintă un punct important în științele algoritmice. A inspirat numeroase avansuri în acest sector. Prima încercare de rezolvare a avut loc în anul 1956. Atunci, matematicienii Delbert Fulkerson și Lester Ford au propus o teorie pe care au numit-o „soluția lacomă”.

Un astfel de algoritm funcționează prin potențarea alegerilor imediat avantajoase în fiecare punct din rețeaua de decizii. Adică alege cea mai bună cale care se află fix în fața sa, indiferent de repercusiunile pe termen lung. 

Acest algoritm s-a dovedit îndeajuns de eficient pentru moment. Dar nu a produs cel mai bun flux. Dacă alte rute erau blocate, în traficul de pe carosabil, de exemplu, sau apăreau anumite blocaje pe stradă, atunci sistemul nu mai era la fel de eficient.

Contribuțiile în această arie din următorii 70 de ani tot nu au găsit o soluție la fel de eficientă precum cea pe care a dezvoltat-o un algoritm „absurd de rapid” prezentat recent. Schimbări din ultimele decenii au reușit să crească viteza, dar nu au atins fluxul maxim. De exemplu, în 2004, schimbările au dus la creșterea vitezei algoritmului de la un multiplu de m^2 (m fiind numărul nodurilor din rețea) la un multiplu de m^1.33. Dar din 2004, progresul a stagnat. 

Algoritmul poate oferi soluții pentru traficul terestru și aerian

Pentru a ajunge la această descoperire, experții au combinat 2 abordări din trecut. Soluția originală prin care orice rețea era privită drept trafic. Și o altă teorie care vedea rețeaua drept o rețea electrică. 

Spre deosebire de trenuri și mașini, fluxul electronilor poate fi parțial redirecționat pentru a se alătură unui curent care merge paralel, pe o altă rută. Ceea ce a permis experților să creeze cel mai bun flux pe întreaga rețea. După aceea au aplicat abordarea segment pe segment pentru a  obținut un algoritm „absurd de rapid”.

Prin combinarea acestor 2 abordări, au ajuns la un algoritm hibrid. Daniel A. Spielman, profesor din cadrul Universității Yale, a numit acest algoritm „absurd de rapid”. Spielman a condus programul doctoral al unuia dintre cercetătorii care au participat la studiu.

Spielman a comparat noua soluție cu cele precedente și a concluzionat că e „ca un Porsche care depășește o căruță trasă de cai”. Algoritmul poate fi folosit în numeroase industrii, de la datele transmise pe Internet, la eficientizarea piețelor internaționale și traficului aerian sau terestru. 

Reclamă
Te-ar mai putea interesa și
Logo-urile YouTube și TikTok, ce colectează cele mai multe date ale utilizatorilor, pe ecranul unui telefon
Câte date sunt generate online în fiecare zi. Volumul e mult mai mare decât cred mulți
Câte date sunt generate online în fiecare zi. Volumul e mult mai mare decât cred mulți
Oameni care stau la masă, în fața unui laptop, pentru a ilustra ce înseamnă advertorial
(P) Ce înseamnă advertorial și care este rolul său în promovare
(P) Ce înseamnă advertorial și care este rolul său în promovare
Persoană care scrie la o tastatură albă, îmbrăcată într-o cămașă albastră. A fost dezvăluit topul cu țările cu cel mai rapid Internet
„Jumătate din Internet a picat” într-o nouă pană Cloudflare. Ultima a avut loc acum doar câteva săptămâni
„Jumătate din Internet a picat” într-o nouă pană Cloudflare. Ultima a avut loc acum doar câteva săptămâni
RECOMANDĂRI USEIT.RO
1
Samsung Galaxy S24 Ultra, de culoare albă, pe fundal gri
Primele informații despre seria Samsung Galaxy S27 au fost scurse pe Internet. Ce camere ar avea viitoarele smartphone-uri
Primele informații despre seria Samsung Galaxy S27 au ajuns deja pe Internet, cu detalii despre camerele dispozitivelor. Potrivit unor noi scurgeri de informații, telefoanele din viitoarea serie Galaxy S27 de la Samsung vor avea...
Primele informații despre seria Samsung Galaxy S27 au fost scurse pe Internet. Ce camere ar avea viitoarele smartphone-uri
2
Imagine cu un controller PlayStation, în fața unui panou albastru PlayStation Plus. Trei jocuri PlayStation Plus vor fi disponibile din ianuarie 2022
Jocuri PlayStation Plus din noiembrie 2026. Ce titluri vor fi disponibile
Sony a dezvăluit jocurile care vor fi disponibile în noiembrie 2026 pentru abonații PlayStation Plus. Platforma de jocuri video continuă anul cu titluri din serii cunoscute la nivel mondial, cu milioane de fani. Pentru...
Jocuri PlayStation Plus din noiembrie 2026. Ce titluri vor fi disponibile
3
Logo-urile YouTube și TikTok, ce colectează cele mai multe date ale utilizatorilor, pe ecranul unui telefon
Câte date sunt generate online în fiecare zi. Volumul e mult mai mare decât cred mulți
În contextul digital actual, puțini știu câte date sunt generate online în fiecare zi, cu miliarde de utilizatori care folosesc Internetul.  Miliarde de utilizatori folosesc Internetul în fiecare zi, ceea ce generează un volum...
Câte date sunt generate online în fiecare zi. Volumul e mult mai mare decât cred mulți
4
Mark Zuckerberg într-un pulover gri la o conferință de presă din 2022
Fun
Miliardarul care l-a depășit pe Mark Zuckerberg în topul celor mai bogați oameni din lume. Ce avere fantastică are Michael Dell
Michael Dell l-a depășit pe Mark Zuckerberg în topul celor mai bogați oameni din lume, în urma creșterii acțiunilor companiei sale.  Clasamentul celor mai bogați oameni din lume a avut numeroase schimbări în ultima...
Miliardarul care l-a depășit pe Mark Zuckerberg în topul celor mai bogați oameni din lume. Ce avere fantastică are Michael Dell
5
Telefon Samsung Galaxy S2, Android, pe alb, care e la încarcat. Când vine vorba de cum poți verifica starea bateriei telefonului, există câteva trucuri simple
De ce ți se descarcă mai repede telefonul toamna și iarna. Puțini știu ce se întâmplă cu bateria
Te-ai întrebat de ce ți se descarcă mai repede telefonul toamna și iarna? Temperaturile scăzute pot avea un impact semnificativ asupra bateriilor dispozitivelor. Atunci când vine vorba de baterii, acestea sunt sensibile la schimbările...
De ce ți se descarcă mai repede telefonul toamna și iarna. Puțini știu ce se întâmplă cu bateria
PARTENERI
×