Dijkstra’s algoritme en Best-First-Search#
Dijkstra’s algoritme werkt door vertices in de grafiek te bezoeken, beginnend met het beginpunt van het object. Het onderzoekt dan herhaaldelijk het dichtstbijzijnde nog niet onderzochte hoekpunt, waarbij de hoekpunten worden toegevoegd aan de verzameling te onderzoeken hoekpunten. Het breidt zich uit naar buiten vanaf het beginpunt tot het doel is bereikt. Dijkstra’s algoritme vindt gegarandeerd een kortste weg van het beginpunt naar het doel, zolang geen van de randen negatieve kosten heeft. (Ik schrijf “een kortste pad” omdat er vaak meerdere gelijkwaardig korte paden zijn). In het volgende diagram is het roze vierkant het startpunt, het blauwe vierkant het doel, en de groenblauwe gebieden geven aan welke gebieden Dijkstra’s algoritme heeft onderzocht. De lichtste groenblauwe gebieden liggen het verst van het beginpunt, en vormen dus de “grens” van de verkenning:
Het Greedy Best-First-Search-algoritme werkt op een vergelijkbare manier, behalve dat het een schatting (een heuristiek genoemd) heeft van hoe ver elk hoekpunt van het doel af ligt. In plaats van het hoekpunt te kiezen dat het dichtst bij het beginpunt ligt, kiest het het hoekpunt dat het dichtst bij het doel ligt. Greedy Best-First-Search vindt niet gegarandeerd het kortste pad. Het loopt echter veel sneller dan Dijkstra’s algoritme, omdat het de heuristische functie gebruikt om heel snel naar het doel te leiden. Als het doel bijvoorbeeld ten zuiden van de startpositie ligt, zal Greedy Best-First-Search geneigd zijn zich te concentreren op paden die zuidwaarts leiden. In het volgende diagram vertegenwoordigt geel de knooppunten met een hoge heuristische waarde (hoge kosten om bij het doel te komen) en zwart de knooppunten met een lage heuristische waarde (lage kosten om bij het doel te komen). Hieruit blijkt dat Greedy Best-First-Search zeer snel paden kan vinden in vergelijking met Dijkstra’s algoritme:
Beide voorbeelden illustreren echter het eenvoudigste geval – wanneer de kaart geen obstakels heeft en het kortste pad echt een rechte lijn is. Laten we het concave obstakel beschouwen zoals beschreven in de vorige sectie. Dijkstra’s algoritme werkt harder maar vindt gegarandeerd een kortste pad:
Greedy Best-First-Search daarentegen doet minder werk maar zijn pad is duidelijk minder goed:
Het probleem is dat Greedy Best-First-Search “hebzuchtig” is en naar het doel probeert te gaan, zelfs als dat niet het juiste pad is. Aangezien alleen wordt gekeken naar de kosten om het doel te bereiken en de kosten van het pad tot nu toe worden genegeerd, blijft het doorgaan, zelfs als het pad erg lang is geworden.
Zou het niet mooi zijn om het beste van beide te combineren? A* is in 1968 ontwikkeld om heuristische benaderingen zoals Greedy Best-First-Search te combineren met formele benaderingen zoals Dijsktra’s Algorithm. Het is een beetje ongebruikelijk in die zin dat heuristische benaderingen je gewoonlijk een benaderende manier geven om problemen op te lossen zonder te garanderen dat je het beste antwoord krijgt. A* is echter bovenop de heuristiek gebouwd, en hoewel de heuristiek zelf je geen garantie geeft, kan A* een kortste weg garanderen.