Dijkstras algoritm och Best-First-Search#
Dijkstras algoritm fungerar genom att besöka hörn i grafen från objektets startpunkt. Den undersöker sedan upprepade gånger den närmaste ännu inte undersökta hörnpunkten och lägger till dess hörnpunkter till mängden hörnpunkter som ska undersökas. Den expanderar utåt från startpunkten tills den når målet. Dijkstras algoritm hittar garanterat den kortaste vägen från startpunkten till målet, så länge ingen av kanterna har en negativ kostnad. (Jag skriver ”en kortaste väg” eftersom det ofta finns flera likvärdigt korta vägar). I följande diagram är den rosa kvadraten startpunkten, den blå kvadraten är målet och de tealfärgade områdena visar vilka områden Dijkstras algoritm har skannat. De ljusaste kritvita områdena är de områden som ligger längst bort från startpunkten och utgör således ”gränsen” för utforskningen:
Greedy Best-First-Search-algoritmen fungerar på liknande sätt, förutom att den har en uppskattning (som kallas en heuristik) av hur långt från målet som varje hörn ligger. Istället för att välja den vertex som ligger närmast startpunkten väljer den den vertex som ligger närmast målet. Greedy Best-First-Search är inte garanterat att hitta den kortaste vägen. Den går dock mycket snabbare än Dijkstras algoritm eftersom den använder den heuristiska funktionen för att guida vägen mot målet mycket snabbt. Om målet till exempel ligger söder om startpositionen tenderar Greedy Best-First-Search att fokusera på vägar som leder söderut. I följande diagram representerar gult de noder som har ett högt heuristiskt värde (hög kostnad för att nå målet) och svart de noder som har ett lågt heuristiskt värde (låg kostnad för att nå målet). Det visar att Greedy Best-First-Search kan hitta vägar mycket snabbt jämfört med Dijkstras algoritm:
Båda dessa exempel illustrerar dock det enklaste fallet – när kartan inte har några hinder och den kortaste vägen verkligen är en rak linje. Låt oss betrakta det konkava hindret enligt beskrivningen i föregående avsnitt. Dijkstras algoritm arbetar hårdare men hittar garanterat den kortaste vägen:
Greedy Best-First-Search å andra sidan gör mindre arbete men dess väg är helt klart inte lika bra:
Problemet är att Greedy Best-First-Search är ”girig” och försöker röra sig mot målet även om det inte är den rätta vägen. Eftersom den bara tar hänsyn till kostnaden för att nå målet och ignorerar kostnaden för vägen hittills, fortsätter den att gå även om vägen har blivit riktigt lång.
Vore det inte trevligt att kombinera det bästa av båda? A* utvecklades 1968 för att kombinera heuristiska metoder som Greedy Best-First-Search och formella metoder som Dijsktras algoritm. Det är lite ovanligt eftersom heuristiska metoder vanligtvis ger dig ett ungefärligt sätt att lösa problem utan att garantera att du får det bästa svaret. A* bygger dock på heuristiken, och även om heuristiken i sig inte ger någon garanti kan A* garantera en kortaste väg.