Dijkstras algoritme og Best-First-Search#
Dijkstras algoritme fungerer ved at besøge toppunkter i grafen med udgangspunkt i objektets startpunkt. Derefter undersøger den gentagne gange det nærmeste endnu ikke undersøgte toppunkt og tilføjer dets toppunkt til mængden af toppunkter, der skal undersøges. Den udvider sig udad fra startpunktet, indtil den når frem til målet. Dijkstras algoritme finder med garanti den korteste vej fra startpunktet til målet, så længe ingen af kanterne har negative omkostninger. (Jeg skriver “en korteste vej”, fordi der ofte er flere tilsvarende korte veje). I det følgende diagram er den lyserøde firkant startpunktet, den blå firkant er målet, og de tealfarvede områder viser, hvilke områder Dijkstras algoritme har scannet. De lyseste teal-områder er de områder, der ligger længst væk fra startpunktet og udgør således “grænsen” for udforskningen:
Greedy Best-First-Search-algoritmen fungerer på samme måde, bortset fra at den har et eller andet skøn (kaldet en heuristik) over, hvor langt fra målet et hvilket som helst toppunkt er. I stedet for at vælge det toppunkt, der ligger tættest på startpunktet, vælger den det toppunkt, der ligger tættest på målet. Greedy Best-First-Search er ikke garanteret at finde den korteste vej. Den kører dog meget hurtigere end Dijkstras algoritme, fordi den bruger den heuristiske funktion til at lede sig meget hurtigt frem mod målet. Hvis målet f.eks. ligger syd for startpositionen, vil Greedy Best-First-Search have en tendens til at fokusere på stier, der fører sydpå. I det følgende diagram repræsenterer gult de knuder med en høj heuristisk værdi (høje omkostninger for at nå målet) og sort repræsenterer knuder med en lav heuristisk værdi (lave omkostninger for at nå målet). Det viser, at Greedy Best-First-Search kan finde stier meget hurtigt sammenlignet med Dijkstras algoritme:
Disse to eksempler illustrerer dog begge det enkleste tilfælde – når kortet ikke har nogen forhindringer, og den korteste vej virkelig er en lige linje. Lad os betragte den konkave forhindring som beskrevet i det foregående afsnit. Dijkstras algoritme arbejder hårdere, men finder med garanti den korteste vej:
Greedy Best-First-Search på den anden side gør mindre arbejde, men dens vej er tydeligvis ikke så god:
Problemet er, at Greedy Best-First-Search er “grådig” og forsøger at bevæge sig mod målet, selv om det ikke er den rigtige vej. Da den kun tager hensyn til omkostningerne for at nå frem til målet og ignorerer omkostningerne ved vejen indtil videre, fortsætter den, selv om den vej, den er på, er blevet rigtig lang.
Vil det ikke være rart at kombinere det bedste af begge dele? A* blev udviklet i 1968 for at kombinere heuristiske tilgange som Greedy Best-First-Search og formelle tilgange som Dijsktra’s Algorithm. Det er lidt usædvanligt, fordi heuristiske metoder normalt giver dig en tilnærmelsesvis måde at løse problemer på uden at garantere, at du får det bedste svar. A* er imidlertid bygget oven på heuristikken, og selv om heuristikken i sig selv ikke giver dig en garanti, kan A* garantere en korteste vej.