Az „abszurd gyors” algoritmus 70 éves leállást old meg - felgyorsítja a hálózati forgalmat a légitársaságok menetrendjétől az internetig

A kutatók egy "abszurd gyors" algoritmust dolgoztak ki a hálózaton keresztüli leggyorsabb áramlás megtalálásának problémájának megoldására.

Amikor a webhelyünkön található linkeken keresztül vásárol, társult jutalékot kaphatunk. Íme, hogyan működik.

Egy szupergyors új algoritmusnak köszönhetően a hálózat lassulása hamarosan a múlté lehet.

Az áttörés drámaian gyorsabb megoldást kínál az informatikusokat az 1950-es évek óta sújtó problémára: a maximális áramlásra, vagyis arra, hogyan lehet a leggyorsabb információáramlást elérni egy korlátozott kapacitású rendszeren keresztül.

A korábbi maximális áramlási algoritmusok folyamatosan és fokozatosan haladtak előre, de továbbra is tovább tartott az optimális áramlás megtalálása, mint a hálózati adatok feldolgozása. Az új kutatás azonban, amelyet június 11-én mutattak be az Az 56. éves ACM Symposium on Computing Theory rendezvényen, egy olyan algoritmust részletez, amely nagyjából olyan gyorsan képes megoldani a problémát, mint amennyire a részletek megírása szükséges. hálózat le.

A maximális áramlási probléma az algoritmikus tudomány egyik sarokköve, és számos legjelentősebb előrelépést inspirált a területen. Az első kísérlet a megoldására 1956-ban történt, amikor Delbert Fulkerson és Lester Ford matematikusok egy általuk „kapzsi megoldást” javasoltak a kérdésre.

A mohó algoritmusok úgy működnek, hogy a döntési fa minden pontján a legelőnyösebb döntéseket hozzák meg, és a legjobb utat választják előtte, függetlenül attól, hogy ez milyen útvonalakat akadályozhat meg a jövőben.

Kapcsolódó:Az új kvantumszámítógép 100-szorosára dönti meg a „kvantumfölény” rekordját - és 30 000-szer kevesebb energiát fogyaszt

Képzelje el az A-ból B-be több lehetséges útvonalon haladó forgalom optimalizálásának problémáját, ahol az egyik útvonal egy első szakaszból áll, amely egy hatsávos autópálya, az utolsó pedig egy háromsávos útszakaszból. Ennek megoldására a mohó algoritmus a lehető legnagyobb forgalmat (három sávos autó) indítja el az útvonalon, módosítja a kapacitását, és megismétli ugyanazokat a lépéseket más útvonalakon, amíg minden lehetséges útvonal teljes kapacitással nem lesz.

Fulkerson és Ford algoritmusa elég hatékonynak bizonyult, de gyakran nem a lehető legjobb áramlást produkálta: Ha más útvonalakat elvágtak és szuboptimális dugulások alakultak ki, hát legyen. Az ezt követő 70 évnyi hozzájárulás a problémához próbálta finomítani a megoldás ezen aspektusát, elsimítva a szükségtelen lassulásokat azáltal, hogy jobb döntéshozatalt épített be az algoritmusba.

Ezek a módosítások az algoritmus futási idejét m^2 többszörösről (ahol m a csomópontok száma a hálózatban) m^1,33 többszörösére tolták el 2004-ben, de aztán a fejlődés megakadt.

Az áttörés elérése érdekében a kutatók két korábbi megközelítést kombináltak: az eredeti megoldást, amely a hálózatokat forgalomként kezelte; és egy későbbi, amely ehelyett elektromos hálózatnak tekintette őket. Az autókkal vagy vonatokkal ellentétben az elektronok áramlása részben elterelhető, hogy egy másik útvonalon csatlakozzon az áramhoz, így az informatikusok feltérképezhetik a legjobb áramlást a teljes hálózaton, mielőtt a szegmensenkénti forgalmi megközelítést alkalmaznák.

E két megközelítés kombinálásával egy "abszurdan gyors" hibrid algoritmus jött létre - mondta Daniel A. Spielman, a Yale Egyetem alkalmazott matematika és számítástechnika professzora, aki az egyik kutató doktori programját irányította. Spielman az új megoldást a korábbiakhoz hasonlította, mintha „a Porsche előzné a lovas kocsikat”.

Finomítás után az új algoritmus potenciálisan számos alkalmazásban alkalmazható, beleértve az internetes adatokat, a légitársaságok menetrendjét és a piacok hatékonyságának javítását, mondták a kutatók.