A számítástechnika egyik legrégebbi és legismertebb problémája a legrövidebb út keresése. Ez nemcsak az útvonaltervezésben hasznos, hanem minden olyan helyzetben, ahol hálózatokat, kapcsolatokat vagy összeköttetéseket kell optimalizálni – legyen szó internetről, közlekedésről, logisztikáról vagy akár mesterséges intelligenciáról. Most azonban egy új kutatói csapat olyan algoritmust mutatott be, amely áttörte a korábbi korlátokat, és gyorsabb, mint a tankönyvekben szereplő klasszikus megoldások.
A legrövidebb út problémája – miért olyan fontos?
A feladat lényege egyszerű: adott egy hálózat (más néven gráf), amely csomópontokból és az azokat összekötő élekből áll. Az élekhez súlyok tartoznak, amelyek jelenthetik a megtett távolságot, az utazási időt vagy akár a költséget. A kérdés: hogyan találjuk meg a legrövidebb (vagy legkisebb költségű) utat egy kiindulóponttól a hálózat összes többi pontjához?
Ezt a problémát először Edsger Dijkstra holland számítógép-tudós oldotta meg 1956-ban, amikor megalkotta az azóta híressé vált Dijkstra-algoritmust. Ez a módszer lépésről lépésre halad a kezdőponttól, mindig a legközelebbi csomópontot választva, és innen építi tovább az útvonalakat.
Az algoritmus zseniálisan egyszerű, és máig a számítástechnika egyik alapköve. Azonban van egy beépített sebességkorlátja, amelyet „rendezési akadálynak” (sorting barrier) neveznek. Ennek oka, hogy minden lépésnél meg kell állapítani, melyik csomópont van a legközelebb – ez pedig rendezési műveleteket igényel, amelyek meghatározzák az algoritmus futási idejét.
A rendezési akadály és a kutatók küzdelme vele
Az elmúlt évtizedekben számos kutató próbálta gyorsabbá tenni a legrövidebb út keresését. Már az 1980-as években világossá vált, hogy a Dijkstra-algoritmus nem léphet túl a rendezési akadályon – vagyis nem lehet gyorsabb annál az időnél, amit a távolságok sorba rendezése megkövetel.
A 2000-es években ugyan születtek próbálkozások a sebességkorlát átlépésére, ám ezek mindig kompromisszumokkal jártak. Az új algoritmusok többnyire csak bizonyos típusú hálózatokon – például az oda-vissza bejárható, úgynevezett irányítatlan gráfokon – vagy előre meghatározott súlyértékek mellett működtek hatékonyan. Emiatt sokáig úgy tűnt, hogy nem létezhet minden esetre érvényes, univerzális megoldás.
Ez is érdekelhet: Egy új algoritmussal gyorsabban visszafejthető minden titkosítás
Ran Duan és csapatának áttörése
A fordulatot Ran Duan, a Pekingi Tsinghua Egyetem kutatója hozta el. Duan már évek óta foglalkozott a problémával, és 2021-ben kezdett kísérletezni egy új megközelítéssel. Az áttörést végül 2024-ben érte el, amikor három kollégájával közösen kifejlesztett egy olyan algoritmust, amely nem rendezéssel dolgozik, így képes kikerülni a hagyományos korlátokat.
A módszer lényege, hogy a hálózat feldolgozását nem szigorúan sorrendben végzi, hanem csomópontokat csoportosít és rétegekre bontja. Emellett beépítettek elemeket a korábban sokkal lassabbnak tartott Bellman–Ford algoritmusból, de csak részlegesen, néhány lépés erejéig. Ez lehetővé teszi, hogy az algoritmus mindig a stratégiai szempontból legfontosabb csomópontokra fókuszáljon – olyanokra, amelyek sok más rövid út alapját adják.
Így elérték, hogy az algoritmus gyorsabb legyen a legjobb Dijkstra-alapú megoldásoknál, és mind irányított, mind irányítatlan gráfokra működjön.
Miért nagy dolog ez?
Az új algoritmus jelentősége több szinten mérhető:
Elméleti áttörés: egy több évtizedes matematikai korlátot sikerült megkerülni, amelyet sokan áthághatatlannak hittek.
Gyakorlati alkalmazások: gyorsabb útkeresésre van szükség a navigációs rendszerektől kezdve az internetes adatforgalom optimalizálásán át egészen a mesterséges intelligencia tanulási folyamataiig.
Új lehetőségek: ha a rendezési akadály megkerülhető, akkor más klasszikus algoritmikus problémák is újragondolhatók lehetnek.
Hogyan tovább?
A kutatók jelenleg azon dolgoznak, hogy az algoritmust még egyszerűbbé és gyorsabbá tegyék. Bár most már sikerült bizonyítani, hogy a rendezési akadály nem áthághatatlan, a fejlesztések még nem értek véget.
Robert Tarjan, a Princeton Egyetem legendás számítógép-tudósa szerint ez „csak az első lépés”, és jó eséllyel még hatékonyabb módszerek is születhetnek.
