algorithm
A * Pathfinding

Introductie tot A *

A * (een ster) is een zoekalgoritme dat wordt gebruikt voor het vinden van een pad van het ene knooppunt naar het andere. Dus het kan worden vergeleken met Breadth First Search , of Dijkstra's algoritme , of Depth First Search , of Best First Search. Een * algoritme wordt veel gebruikt bij het zoeken naar grafieken om de efficiëntie en nauwkeurigheid te verbeteren, waarbij voorbewerking van de grafiek geen optie is.

A * is een specialisatie van Best First Search, waarbij de functie van evaluatie f op een bepaalde manier wordt gedefinieerd.

f (n) = g (n) + h (n) zijn de minimale kosten sinds het initiële knooppunt voor de doelstellingen geconditioneerd om te gaan denken knooppunt n .

g (n) zijn de minimale kosten van het initiële knooppunt tot n .

h (n) zijn de minimumkosten van n naar de doelstelling die het dichtst bij n ligt

A * is een geïnformeerd zoekalgoritme en het garandeert altijd het kleinste pad (pad met minimale kosten) te vinden in de minst mogelijke tijd (als gebruik toelaatbare heuristiek ). Het is dus zowel compleet als optimaal . De volgende animatie toont A * zoeken-

8-puzzel probleem oplossen met A * algoritme

Probleem definitie :

Een 8-puzzel is een eenvoudig spel bestaande uit een 3 x 3-raster (met 9 vierkanten). Een van de vierkanten is leeg. Het doel is om naar vierkanten in verschillende posities rond te bewegen en de getallen in de "doelstatus" te laten verschijnen.

Gegeven een initiële status van 8-puzzelspel en een definitieve status van te bereiken, vind je het meest kosteneffectieve pad om de definitieve status te bereiken vanuit de initiële status.

Uitgangsstatus :

_ 1 3
4 2 5
7 8 6

Laatste staat :

1 2 3
4 5 6
7 8 _

Heuristisch te veronderstellen :

Laten we de Manhattan-afstand tussen de huidige en de uiteindelijke toestand beschouwen als de heuristiek voor deze probleemstelling.

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

Totale kostenfunctie :

Dus de totale kostenfunctie f(n) wordt gegeven door,

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

Oplossing voor een voorbeeldprobleem :

Eerst vinden we de heuristische waarde die nodig is om de eindtoestand te bereiken vanuit de initiële toestand. De kostenfunctie, g (n) = 0, omdat we ons in de begintoestand bevinden

h(n) = 8

De bovenstaande waarde wordt verkregen, omdat 1 in de huidige status 1 horizontale afstand is dan de 1 in de uiteindelijke status. Hetzelfde geldt voor 2 , 5 , 6 . _ ligt op 2 horizontale afstand en 2 verticale afstand. De totale waarde voor h(n) is dus 1 + 1 + 1 + 1 + 2 + 2 = 8. De totale kostenfunctie f(n) is gelijk aan 8 + 0 = 8.

Nu worden de mogelijke toestanden gevonden die vanaf de beginstatus kunnen worden bereikt en het gebeurt dat we _ naar rechts of naar beneden kunnen bewegen.

Dus staten verkregen na het verplaatsen van die bewegingen zijn:

1 _ 3    4 1 3
4 2 5    _ 2 5
7 8 6    7 8 6
 (1)      (2)

Opnieuw wordt de totale kostenfunctie berekend voor deze toestanden met behulp van de hierboven beschreven methode en deze blijkt respectievelijk 6 en 7 te zijn. We hebben de staat met minimale kosten gekozen, namelijk staat (1). De volgende mogelijke zetten kunnen Links, Rechts of Omlaag zijn. We gaan niet naar links zoals we eerder in die staat waren. We kunnen dus naar rechts of omlaag gaan.

Opnieuw vinden we de toestanden verkregen van (1).

1 3 _    1 2 3
4 2 5    4 _ 5
7 8 6    7 8 6
 (3)      (4)

(3) leidt tot kostenfunctie gelijk aan 6 en (4) leidt tot 4. Ook zullen we beschouwen (2) eerder verkregen waarvan de kostenfunctie gelijk is aan 7. Kiezen van minimum van hen leidt tot (4). Volgende mogelijke zetten kunnen Links of Rechts of Omlaag zijn. We krijgen staten:

1 2 3    1 2 3    1 2 3
_ 4 5    4 5 _    4 8 5
7 8 6    7 8 6    7 _ 6
 (5)      (6)      (7)

We krijgen kosten gelijk aan 5, 2 en 4 voor respectievelijk (5), (6) en (7). We hebben ook eerdere toestanden (3) en (2) met respectievelijk 6 en 7. We hebben gekozen voor de minimale kostenstatus (6). De volgende mogelijke zetten zijn Omhoog, en Omlaag en duidelijk Omlaag zullen ons naar de eindtoestand leiden die leidt tot een heuristische functiewaarde gelijk aan 0.

A * Pathfinding door een doolhof zonder obstakels

Laten we zeggen dat we het volgende 4 bij 4 raster hebben:

Laten we aannemen dat dit een doolhof is . Er zijn echter geen muren / obstakels. We hebben alleen een beginpunt (het groene vierkant) en een eindpunt (het rode vierkant). Laten we ook aannemen dat we niet diagonaal kunnen bewegen om van groen naar rood te gaan. Laten we dus vanaf het groene vierkant kijken naar welke vierkanten we kunnen gaan en deze blauw markeren:

Om te kiezen naar welk vierkant we moeten gaan, moeten we rekening houden met 2 heuristieken:

1. De "g" -waarde - Dit is hoe ver deze knoop van het groene vierkant verwijderd is.
2. De "h" -waarde - Dit is hoe ver deze knoop van het rode vierkant is.
3. De "f" -waarde - Dit is de som van de "g" -waarde en de "h" -waarde. Dit is het laatste nummer dat ons vertelt naar welk knooppunt we moeten gaan.

Om deze heuristieken te berekenen, is dit de formule die we zullen gebruiken: distance = abs(from.x - to.x) + abs(from.y - to.y)

Dit staat bekend als de "Manhattan Distance" -formule.

Laten we de "g" -waarde berekenen voor het blauwe vierkant direct links van het groene vierkant: abs(3 - 2) + abs(2 - 2) = 1

Super goed! We hebben de waarde: 1. Laten we nu proberen de "h" -waarde te berekenen: abs(2 - 0) + abs(2 - 0) = 4

Perfect. Laten we nu de "f" -waarde krijgen: 1 + 4 = 5

De uiteindelijke waarde voor dit knooppunt is dus "5".

Laten we hetzelfde doen voor alle andere blauwe vierkanten. Het grote getal in het midden van elk vierkant is de waarde "f", terwijl het getal linksboven de waarde "g" is en het getal rechtsboven de waarde "h":

We hebben de g-, h- en f-waarden berekend voor alle blauwe knooppunten. Welke kiezen we nu?

Welke heeft de laagste f-waarde.

In dit geval hebben we echter 2 knooppunten met dezelfde f-waarde, 5. Hoe kiezen we hiertussen?

Kies eenvoudig een willekeurige of stel een prioriteit in. Meestal heb ik liever zo'n prioriteit: "Rechts> Omhoog> Omlaag> Links"

Een van de knooppunten met de f-waarde van 5 neemt ons mee in de richting "Omlaag" en de andere brengt ons "Links". Omdat Down een hogere prioriteit heeft dan Left, kiezen we het vierkant dat ons "Down" brengt.

Ik markeer nu de knooppunten waarvoor we de heuristiek hebben berekend, maar niet zijn verplaatst naar, als oranje, en de knoop die we hebben gekozen als cyaan:

Oké, laten we nu dezelfde heuristieken berekenen voor de knooppunten rond de cyaanknoop:

Nogmaals, we kiezen het knooppunt dat omlaag gaat vanaf het cyaanknooppunt, omdat alle opties dezelfde f-waarde hebben:

Laten we de heuristieken berekenen voor de enige buurman die de cyaanknoop heeft:

Oké, omdat we hetzelfde patroon zullen volgen dat we hebben gevolgd:

Laten we nogmaals de heuristiek voor de buurman van de knoop berekenen:

Laten we daarheen gaan:

Eindelijk kunnen we zien dat we een winnend vierkant naast ons hebben, dus we gaan daarheen en we zijn klaar.