Een nieuw algoritme maakt het sneller om de kortste paden te vinden

De originele versie van dit verhaal verscheen in Quanta Magazine .

Als je een lastig probleem wilt oplossen, helpt het vaak om je te organiseren. Je kunt het probleem bijvoorbeeld in stukken opdelen en de makkelijkste stukken eerst aanpakken. Maar dit soort sorteren heeft een prijskaartje. Je kunt uiteindelijk te veel tijd besteden aan het ordenen van de stukken.

Dit dilemma is vooral relevant voor een van de meest iconische problemen in de informatica: het vinden van de kortste route van een specifiek startpunt in een netwerk naar elk ander punt. Het is als een opgepoetste versie van een probleem dat je elke keer dat je verhuist moet oplossen: de beste route vinden van je nieuwe huis naar je werk, de sportschool en de supermarkt.

“Kortste paden is een prachtig probleem waar iedereen ter wereld zich mee kan identificeren”, aldus Mikkel Thorup , computerwetenschapper aan de Universiteit van Kopenhagen.

Intuïtief gezien zou het het makkelijkst moeten zijn om de kortste route naar dichtstbijzijnde bestemmingen te vinden. Dus als je het snelst mogelijke algoritme voor het kortste-padprobleem wilt ontwerpen, lijkt het redelijk om te beginnen met het vinden van het dichtstbijzijnde punt, vervolgens het op één na dichtstbijzijnde, enzovoort. Maar om dat te doen, moet je herhaaldelijk uitzoeken welk punt het dichtstbij is. Je sorteert de punten gaandeweg op afstand. Er is een fundamentele snelheidslimiet voor elk algoritme dat deze aanpak volgt: je kunt niet sneller gaan dan de tijd die nodig is om te sorteren.

Veertig jaar geleden liepen onderzoekers die algoritmen voor de kortste route ontwierpen tegen deze 'sorteerbarrière' aan. Nu heeft een team onderzoekers een nieuw algoritme ontwikkeld dat deze barrière doorbreekt . Het sorteert niet en is sneller dan alle algoritmen die dat wel doen.

"De auteurs hadden de lef om te denken dat ze deze barrière konden doorbreken", aldus Robert Tarjan , computerwetenschapper aan de Princeton University. "Het is een verbluffend resultaat."

Om het kortste-padprobleem wiskundig te analyseren, gebruiken onderzoekers de taal van grafieken: netwerken van punten, of knooppunten, verbonden door lijnen. Elke verbinding tussen knooppunten is gelabeld met een getal, het zogenaamde gewicht, dat de lengte van dat segment of de tijd die nodig is om het te doorkruisen kan weergeven. Er zijn meestal meerdere routes tussen twee knooppunten, en het kortste is de route waarvan de gewichten optellen tot het kleinste getal. Gegeven een grafiek en een specifiek "bronknooppunt", is het doel van een algoritme om het kortste pad naar elk ander knooppunt te vinden.

Het bekendste algoritme voor kortste paden , bedacht door de baanbrekende computerwetenschapper Edsger Dijkstra in 1956, begint bij de bron en werkt stapsgewijs naar buiten. Dit is een effectieve aanpak, omdat het kennen van het kortste pad naar nabijgelegen knooppunten je kan helpen de kortste paden naar verder weg gelegen knooppunten te vinden. Maar omdat het eindresultaat een gesorteerde lijst met kortste paden is, stelt de sorteerbarrière een fundamentele limiet aan de snelheid van het algoritme.

Illustratie: Mark Belan, Samuel Velasco/Quanta Magazine

In 1984 verbeterden Tarjan en een andere onderzoeker Dijkstra's oorspronkelijke algoritme , zodat het aan deze snelheidslimiet voldeed. Verdere verbeteringen zouden moeten komen van een algoritme dat sortering vermijdt.

Eind jaren negentig en begin jaren 2000 ontwikkelden Thorup en andere onderzoekers algoritmen die de sorteerbarrière doorbraken, maar ze moesten wel bepaalde aannames doen over gewichten. Niemand wist hoe ze hun technieken moesten uitbreiden naar willekeurige gewichten. Het leek erop dat ze het einde van hun Latijn waren.

"Het onderzoek heeft heel lang stilgelegen", zegtRan Duan , computerwetenschapper aan de Tsinghua Universiteit in Peking. "Veel mensen dachten dat er geen betere manier was."

Duan was daar niet één van. Hij droomde er al lang van om een ​​algoritme voor de kortste paden te bouwen dat de sorteerbarrière op alle grafieken zou kunnen doorbreken. Afgelopen najaar slaagde hij daar eindelijk in.

Duans interesse in de sorteerbarrière gaat bijna 20 jaar terug, naar zijn tijd als doctoraatsstudent aan de Universiteit van Michigan, waar zijn begeleider een van de onderzoekers was die uitvond hoe de barrière in specifieke gevallen te doorbreken. Maar pas in 2021 bedacht Duan een veelbelovende aanpak.

De sleutel was om te focussen op waar het algoritme bij elke stap naartoe gaat. Dijkstra's algoritme neemt het gebied dat het in eerdere stappen al heeft verkend. Het bepaalt waar het vervolgens naartoe gaat door de "grens" van dit gebied te scannen – dat wil zeggen alle knooppunten die met de grens ervan verbonden zijn. Dit kost in het begin niet veel tijd, maar het wordt langzamer naarmate het algoritme vordert.

Edsger Dijkstra bedacht een klassiek algoritme dat de kortste route vindt van een specifiek punt in een netwerk naar elk ander punt.

Foto: Hamilton Richards

Duan stelde zich voor om aangrenzende knooppunten op de grens in clusters te groeperen. Hij zou dan slechts één knooppunt per cluster in overweging nemen. Met minder knooppunten om door te spitten, zou de zoektocht bij elke stap sneller kunnen verlopen. Het algoritme zou uiteindelijk ook ergens anders dan het dichtstbijzijnde knooppunt terecht kunnen komen, waardoor de sorteerbarrière niet van toepassing zou zijn. Maar het zou een uitdaging zijn om ervoor te zorgen dat deze clustergebaseerde aanpak het algoritme daadwerkelijk sneller in plaats van langzamer zou maken.

Duan werkte dit basisidee het jaar daarop verder uit en in de herfst van 2022 was hij optimistisch dat hij de technische obstakels zou kunnen overwinnen. Hij schakelde drie promovendi in om de details uit te werken en een paar maanden later kwamen ze tot een gedeeltelijke oplossing : een algoritme dat de sorteerbarrière voor alle gewichten doorbrak, maar alleen voor zogenaamde ongerichte grafieken.

In ongerichte grafieken kan elke schakel in beide richtingen worden doorlopen. Computerwetenschappers zijn doorgaans meer geïnteresseerd in de bredere klasse van grafieken met eenrichtingsverkeer, maar deze "gerichte" grafieken zijn vaak lastiger te navigeren.

"Het zou kunnen dat A B heel gemakkelijk kan bereiken, maar B niet zo gemakkelijk A", aldus Xiao Mao , een student computerwetenschappen aan Stanford University. "Dat levert je een hoop problemen op."

In de zomer van 2023 hoorde Mao Duan een lezing geven over het ongerichte-graafalgoritme op een conferentie in Californië. Hij raakte in gesprek met Duan, wiens werk hij al lang bewonderde.

"Ik ontmoette hem voor het eerst in het echt", herinnerde Mao zich. "Het was heel spannend."

Na de conferentie begon Mao in zijn vrije tijd over het probleem na te denken. Ondertussen onderzochten Duan en zijn collega's nieuwe benaderingen die zouden kunnen werken op gerichte grafieken. Ze lieten zich inspireren door een ander eerbiedwaardig algoritme voor het kortste-padenprobleem, het Bellman-Ford-algoritme, dat geen gesorteerde lijst oplevert. Op het eerste gezicht leek het een onverstandige strategie, aangezien het Bellman-Ford-algoritme veel langzamer is dan dat van Dijkstra.

"Wanneer je onderzoek doet, probeer je altijd een veelbelovende weg te bewandelen", zei Thorup. "Ik zou het bijna anti-belovend noemen om Bellman-Ford te kiezen, want het lijkt wel het domste wat je kunt doen."

Duans team omzeilde de traagheid van het Bellman-Ford-algoritme door het slechts enkele stappen tegelijk te laten lopen. Dit selectieve gebruik van Bellman-Ford stelde hun algoritme in staat om vooruit te kijken naar de meest waardevolle knooppunten om in latere stappen te verkennen. Deze knooppunten zijn vergelijkbaar met kruispunten van belangrijke verkeersaders in een wegennetwerk.

"Je moet erdoorheen om de kortste weg naar veel andere dingen te vinden", zei Thorup.

In maart 2024 bedacht Mao een andere veelbelovende aanpak. Enkele belangrijke stappen in de oorspronkelijke aanpak van het team maakten gebruik van willekeur. Gerandomiseerde algoritmen kunnen veel problemen efficiënt oplossen, maar onderzoekers geven nog steeds de voorkeur aan niet-willekeurige benaderingen. Mao bedacht een nieuwe manier om het kortste-padprobleem zonder willekeur op te lossen. Hij sloot zich aan bij het team en de daaropvolgende maanden werkten ze samen via groepsgesprekken en videogesprekken om hun ideeën te bundelen. Uiteindelijk, in de herfst, realiseerde Duan zich dat ze een techniek konden aanpassen van een algoritme dat hij in 2018 had bedacht en dat de sorteerbarrière voor een ander grafiekprobleem doorbrak. Die techniek was het laatste stukje dat ze nodig hadden voor een algoritme dat sneller werkte dan dat van Dijkstra, zowel op gerichte als ongerichte grafieken.

Het voltooide algoritme verdeelt de grafiek in lagen, die net als Dijkstra's algoritme vanuit de bron naar buiten toe werken. Maar in plaats van de hele grens bij elke stap te behandelen, gebruikt het het Bellman-Ford-algoritme om invloedrijke knooppunten te lokaliseren, gaat het vanuit deze knooppunten verder om de kortste paden naar andere knooppunten te vinden en keert het later terug naar andere grensknooppunten. Het vindt de knooppunten binnen elke laag niet altijd in volgorde van toenemende afstand, waardoor de sorteerbarrière niet van toepassing is. En als je de grafiek op de juiste manier opdeelt, werkt het iets sneller dan de beste versie van Dijkstra's algoritme. Het is aanzienlijk complexer en vertrouwt op veel stukjes die precies in elkaar moeten passen. Maar vreemd genoeg maakt geen van de stukjes gebruik van ingewikkelde wiskunde.

"Dit ding had net zo goed 50 jaar geleden ontdekt kunnen worden, maar dat is niet zo," zei Thorup. "Dat maakt het des te indrukwekkender."

Duan en zijn team zijn van plan te onderzoeken of het algoritme gestroomlijnd kan worden om het nog sneller te maken. Nu de sorteerbarrière geslecht is, nadert de looptijd van het nieuwe algoritme nog lang geen fundamentele limiet waar computerwetenschappers weet van hebben.

"Als optimist zou het me niet verbazen als je het nog verder naar beneden zou brengen," zei Tarjan. "Ik denk zeker niet dat dit de laatste stap in het proces is."

Oorspronkelijk verhaal met toestemming overgenomen uit Quanta Magazine , een redactioneel onafhankelijke publicatie van de Simons Foundation. De missie van dit tijdschrift is om het begrip van wetenschap bij het publiek te vergroten door verslag te doen van ontwikkelingen en trends in het onderzoek naar wiskunde, natuurkunde en levenswetenschappen.