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

Experții au dezvoltat un algoritm „absurd de rapid” ce a rezolvat o problemă de trafic de 70 de ani, soluție ce poate fi aplicată în mai multe sectoare.

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
O femei arheolog care descoperă rămășițele unei țestoase care au fost descoperite în Pompeii
Descoperirea care poate rescrie istoria umană. Ce tehnologie preistorică au găsit experții
Descoperirea care poate rescrie istoria umană. Ce tehnologie preistorică au găsit experții
Doi astronauți, lângă Stația Spațială Internațională, în spațiu, cu Pământul pe fundal. Acolo vor ajunge și astronauții amatori care au plătit câte 55 de milioane de dolari pentru misiune
Nokia și NASA lansează prima rețea mobilă de pe Lună. Cine o poate folosi
Nokia și NASA lansează prima rețea mobilă de pe Lună. Cine o poate folosi
Imagine cu un cip, pe fundal albastru, cu un laptop pentru pariuri sportive, pentru a ilustra inteligența artificială
(P) Ne poate ajuta Inteligența Artificială la pariuri sportive?
(P) Ne poate ajuta Inteligența Artificială la pariuri sportive?
RECOMANDĂRI USEIT.RO
1
Utilizator care ține în mână un telefon cu logo-ul Android pe ecran, cu semn malware pe fundal. Google avertizează acum milioane de utilizatori Android să șteargă aplicațiile periculoase
Spyware găsit pe zeci de aplicații Android. Ce utilizatori au fost afectați, potrivit experților
Guverne din mai multe țări au dezvăluit că spyware a fost găsit pe zeci de aplicații Android, care au fost descărcate deja de utilizatori.  O coaliție de guverne a publicat o listă cu aplicații...
Spyware găsit pe zeci de aplicații Android. Ce utilizatori au fost afectați, potrivit experților
2
Bill Gates, îmbrăcat în costum, pe scenă la Malaria Summit , Londra, Anglia, 2018, cu mov pe fundal. Averile lui Elon Musk, Jeff Bezos și Bill Gates sunt unele dintre cele mai mari din lume
Primul sistem de operare creat de Bill Gates și Paul Allen poate fi descărcat de oricine acum: „E cel mai cool cod pe care l-am scris vreodată
Primul sistem de operare creat de Bill Gates și Paul Allen în urmă cu 50 de ani poate fi descărcat acum de oricine, gratuit.  Bill Gates, co-fondatorul Microsoft, a sărbătorit istoria de 50 de...
Primul sistem de operare creat de Bill Gates și Paul Allen poate fi descărcat de oricine acum: „E cel mai cool cod pe care l-am scris vreodată
3
Dispozitiv Nintendo Switch, ce a vândut peste 100 de milioane de unități, în mâna unui utilizator, cu un joc pe ecran
Nintendo a dezvăluit data de lansare pentru consola Switch 2. Ce preț va avea
Nintendo a dezvăluit data de lansare pentru consola Switch 2, unul dintre cele mai așteptate dispozitive de gaming.  Data de lansare pentru noua consolă a fost confirmată recent de către Nintendo. Spre încântarea fanilor,...
Nintendo a dezvăluit data de lansare pentru consola Switch 2. Ce preț va avea
4
Laptop deschis cu OpenAI pe ecran și un telefon cu ChatGPT pe ecran, pentru a ilustra industria pe care ChatGPT o poate schimba
Funcția ChatGPT care a atras 1 milion de utilizatori într-o singură oră. Pentru ce opțiune există o „cerere biblică”
Funcția ChatGPT care a atras 1 milion de utilizatori într-o singură oră e disponibilă gratuit și a dus la o „cerere biblică”, potrivit OpenAI. ChatGPT a înregistrat o creștere record după ce a lansat...
Funcția ChatGPT care a atras 1 milion de utilizatori într-o singură oră. Pentru ce opțiune există o „cerere biblică”
5
Colaj cu Jeff Bezos și Elon Musk, unii dintre cei mai bogați oameni din lume. Fondatorul Amazon l-a sfătuit pe Elon Musk cu privire la sediul Twitter
Fun
Cei mai bogați oameni din lume în 2025. Câți români au ajuns pe lista miliardarilor creată de Forbes
Forbes a dezvăluit lista cu cei mai bogați oameni din lume în 2025, top în care se află și unii români, dincolo de cei mai cunoscuți miliardari din lume.  Încă din 1987, Forbes a...
Cei mai bogați oameni din lume în 2025. Câți români au ajuns pe lista miliardarilor creată de Forbes
PARTENERI
×