Algoritmer til de store grafer: Den korteste vej fra A til B

Ingeniøren grafik
Illustration: Ingeniøren. Se større version
En dansk datalog har fundet den mest effektive metode til at finde den korteste vej i et netværk, der hele tiden ændrer sig.
Tech fokus24. marts 2021 kl. 02:43
errorÆldre end 30 dage

ING.DK: At finde den korteste eller hurtigste rute fra ét sted til et andet er både big business, uhyre anvendeligt og et matematisk udfordrende problem.

Et specielt og relevant problem er, hvor hurtigt man kan finde en ny, hvis den oprindelige rute blokeres.

Matematisk set hører problemet ind under grafteori. Christian Wulff-Nilsen fra Datalogisk Institut ved Københavns Universitet har for nylig fundet en effektiv algoritme til at genberegne den korteste rute mellem to knuder i en graf, hvor man gradvist sletter kanterne (forbindelserne) i grafen.

Han har tilmed vist, at givet den nye rute må afvige en lille på forhånd bestemt procentdel fra den optimale rute, så er algoritmen den hurtigste, der eksisterer.

Dermed har han sammen med sin tidligere ph.d.-studerende Maximilian Probst Gutenberg samt Aaron Bernstein, der er assistant professor ved Rutgers University i USA, løst et klassisk datalogisk problem kaldet Decremental Single-Source Shortest Path Problem, som har interesseret og plaget dataloger de seneste 40 år.

Inden vi ser nærmere på dette problem og dets løsning, så lad os tage på café i Amsterdam i 1956.

Få fuld adgang til DataTech

DataTech skriver til dig, der arbejder professionelt med data og analytics. Vi giver dig inspirerende cases, nyheder og debat om alt fra machine learning-modeller til dataetik. Få tilsendt tilbud

Abonnementsfordele
vpn_key
Fuld adgang til DataTech
Alt indhold på DataTech er åbent for dig, så du kan nyde det fra din computer, tablet eller mobil.
drafts
Kuraterede nyhedsbreve
Nyheder, interviews, tendenshistorier og meget mere, leveret til din indbakke.
thumb_up
Adgang til debatten
Deltag i debatten med andre professionelle.
Debatten
Log ind for at deltage i den videnskabelige debat.