Om het kortste pad te bepalen in een gewogen graaf denk je misschien meteen aan het algoritme van Dijkstra. Maar soms kan het beter: Stel dat je jouw GPS instelt om van Gent naar Brussel te navigeren. Het algoritme van Dijkstra zal de toppen in de graaf van wegen overlopen volgens afstand tot het vertrekpunt. Hierdoor zal dat algoritme op een bepaald moment kruispunten in Brugge aan het analyseren zijn, maar dat ligt helemaal aan de andere kant van Gent. Je voelt hier dus al aan dat je dit algoritme slimmer kan maken door bij de zoektocht van een pad ook rekening te houden met hoe dicht je bij je eindbestemming bent.

Je ziet in onderstaande animatie dat Dijkstra bijna alle toppen bezoekt in de graaf:

Het A*-algoritme (uitgesproken als A-ster in het Nederlands en A-star in het Engels) doet exact dit. Het is een uitbreiding op het algoritme van Dijkstra dat naast de afstand van het pad tot het vertrekpunt, ook een schatting van gebruikt de overblijvende afstand. Deze schatting wordt ook vaak de heuristiek genoemd.

Dat het A*-algoritme een stuk vlugger de bestemming kan vinden, zie je in onderstaande animatie:

Meer precies: gegeven een gewogen, gerichte graaf waarin we een pad zoeken tussen een top \(u\) en een bestemming \(v\). Voor een voorlopig pad \(n\) vanaf het vertrekpunt, is \(g(n)\) de som van het gewicht van alle bogen op dit pad, en \(h(n)\) (de heuristiek) die de geschatte resterende afstand is tussen de bestemming \(v\) en de laatste top uit het pad \(n\). Het A*-algoritme zal verder gaan op het pad waarvoor de volgende functie minimaal is:

\[f(n) = g(n) + h(n)\]

(Bij het algoritme van Dijkstra heb je geen heuristiek en is \(h(n) = 0\) en dus \(f(n) = g(n)\)).

Implementeer het algoritme van A* in Java voor het bepalen van een kortste pad van een gegeven top u naar een bestemming v in een gerichte, euclidische graaf G in het vlak. Hierbij heeft elke top een coordinaat \((x, y)\) in het vlak, en is de ‘natuurlijke lengte’ tussen twee toppen \(a\) en \(b\) bepaald door de euclidische afstand:

\[|a, b| = \sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}\]

De effectieve lengte van de weg tussen top \(a\) en \(b\) (als die bestaat) wordt gegeven door het gewicht van de boog \((a,b)\).

Gebruik als schatter of heuristiek \(g(n)\) voor een voorlopig pad, de euclidische afstand tussen de laatste top in het pad en de eindbestemming.

Tip: aangezien A* kan gezien worden als een uitbreiding op het algoritme van Dijkstra, is het een goed idee om eerst het algoritme van Dijkstra te implementeren. Daarna kan je met een kleine aanpassing je algoritme omvormen naar A*.

---

Implementeer de gegeven interface PathFinder¹ met een klasse ASter. Je zal ook de record Coordinate² nodig hebben. Hiervoor schrijf je een methode public List<Node<Coordinate>> shortestPath(DirectedGraph<Coordinate> graph, Node<Coordinate> source, Node<Coordinate> dest) die het kortste pad van source naar dest in de (gerichte!) graaf graph teruggeeft. De eerste en laatste toppen in dit pad zijn respectievelijk source en dest. Als er meerdere mogelijke (kortste) paden zijn, maakt het niet uit welk pad je terug geeft. Zijn er geen paden van source naar dest, dan geef je null terug.

De lengte van elke boog is het gewicht van de boog in de meegegeven graaf. Als heuristiek gebruik je de euclidische afstand tot de bestemming. Je mag (en moet) aannemen dat deze heuristiek een toelaatbare en consistente schatter is voor de gegeven graaf (zoals dat ook in een echt wegennetwerk zou zijn).

Zoals steeds kan je met behulp van de klasse SimpleTest³ jouw code lokaal testen. De documentatie over de gebruikte grafenbibliotheek⁴ vind je hier⁵.