Foto : Ingeniøren
Algoritmer til de store grafer: Den korteste vej fra A til B
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.
DataTech giver dig ny viden, cases og erfaringer med at lykkes med AI og data science i praksis. Få 3 ugers gratis og uforpligtende prøveabonnement
Klik her I dette eksempel har vi en graf med 9 knuder og 14 kanter og ønsker at bestemme den korteste vej fra 0 til enhver af de øvrige knuder.
Dijkstras algoritme begynder i 0 og gennemsøger alle knuder for at komme frem til en reduceret graf, der udeluk-kende viser de korteste veje fra 0 til enhver af de andre knuder.
Det følgende er en forenklet og ikke fuldstændig korrekt gengivelse af Dijkstras algoritme. Den går gradvist frem og begynder med at fjerne kanten mellem 1 og 7, da den direkte vej fra 0 til 7 er kortere end vejen via 1. Da afstanden til 8 er den samme via 6 som direkte fra 7, kan vi også fjerne kanten mellem 7 og 8.
Hermed kommer vi frem til dette mellemresultat, hvor vejene til de grønne knuder (1, 6 og 7) er fastlagt, mens vejene til de viste røde knuder og videre frem endnu ikke er bestemt.
Dernæst undersøges kanterne fra knuderne 2, 5 og 8, og grafen opdateres. Endelig undersøges kanterne, der går til 3 og 4. Det fører slutteligt frem til denne graf, der angiver de korteste veje fra 0 til enhver anden knude. Den oprindelige graf havde kredse, hvor man i princippet kunne bevæge sig i rund-kreds, som fra 6 til 7 til 8 til 6 osv. Det er ikke muligt i den endelige version, som i fagterminologien kaldes en rettet acyklisk graf eller en DAG for directed acyclic graph.
Ved ruteplanlægning kan man komme ud for, at kanternes vægt ændrer sig (det tager længere tid at komme frem, fordi der er kø), eller en kant helt forsvinder (vejen er lukket). Hvis kanten mellem 5 og 6 ovenfor forsvinder, kan vi ikke komme frem til hverken 4 eller 5. Der skal beregnes en ny rute, som bliver beskrevet ved grafen til venstre, hvor algoritmen igen benytter kanten mellem 2 og 5, der tidligere var blevet udeladt.
Inden for datalogi benytter man den såkaldte store O-notation til at beskrive kompleksiteten af en beregning.
Lad os antage, at vi har et problem, hvor løsningstiden vokser som funktion af inputtets størrelse på denne måde T(n) = 73n³ + 221n² + 58.
For store n er det kun tredjepotensleddet, der har betydning, ja selv faktoren 73 foran tredjepotensleddet har ikke den store betydning. Vi siger, at T(n) asymptotisk set (for store n) ikke vokser hurtigere end n³. Det skriver vi som T(n) = O(n³).
I andre situationer kan der indgå en logaritmeafhængig i udtrykket, så vi f.eks. har O(n³log⁴n). I den såkaldte O-tilde notation (Õ), ser man også bort fra disse log n-faktorer og skriver Õ(n³) i stedet for O(n³log⁴n).
