algorithm => A * Pathfinding

Introduktion till A *

A * (En stjärna) är en sökalgoritm som används för att hitta sökvägen från en nod till en annan. Så det kan jämföras med Breadth First Search , eller Dijkstra's algoritm , eller Deepth First Search eller Best First Search. En * -algoritm används i stor utsträckning i grafsökning för att vara bättre i effektivitet och noggrannhet, där grafförbehandling inte är ett alternativ.

A * är en specialisering av Best First Search, där funktionen för utvärdering f definieras på ett visst sätt.

f (n) = g (n) + h (n) är den lägsta kostnaden sedan den initiala noden till målen förutsatt att tänka noden n .

g (n) är minimikostnaden från den initiala noden till n .

h (n) är minimikostnaden från n till det närmaste målet för n

A * är en informerad sökalgoritm och garanterar alltid att hitta den minsta sökvägen (sökväg med minimikostnad) på minst möjliga tid (om den används tillåtna heuristik ). Så det är både komplett och optimalt . Följande animation visar A * search-

Lösa 8-pussel problem med A * -algoritm

Problemdefinition :

Ett 8-pussel är ett enkelt spel som består av ett 3 x 3 rutnät (som innehåller 9 rutor). En av rutorna är tom. Syftet är att flytta till rutor runt i olika positioner och ha siffrorna som visas i "måltillståndet".

Med tanke på ett initialt tillstånd av 8-pusselspel och ett slutligt tillstånd att nås, hitta den mest kostnadseffektiva vägen för att nå det slutliga tillståndet från initialtillståndet.

Starttillstånd :

_ 1 3
4 2 5
7 8 6

Sluttillstånd :

1 2 3
4 5 6
7 8 _

Heuristisk att antas :

Låt oss betrakta Manhattan-avståndet mellan det aktuella och det slutliga tillståndet som heuristiskt för detta problem.

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

Total kostnadsfunktion :

Så den totala kostnadsfunktionen f(n) ges av,

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

Lösning på exempelproblem :

Först hittar vi det heuristiska värde som krävs för att nå det slutliga tillståndet från det initiala tillståndet. Kostnadsfunktionen, g (n) = 0, eftersom vi är i det initiala tillståndet

h(n) = 8

Ovanstående värde erhålls, eftersom 1 i det aktuella tillståndet är 1 horisontellt avstånd bort än det 1 i sluttillståndet. Samma sak gäller 2 , 5 , 6 . _ är 2 horisontella avstånd bort och 2 vertikala avstånd bort. Så det totala värdet för h(n) är 1 + 1 + 1 + 1 + 2 + 2 = 8. Total kostnadsfunktion f(n) är lika med 8 + 0 = 8.

Nu hittas de möjliga tillstånden som kan nås från det initiala tillståndet och det händer att vi antingen kan flytta _ åt höger eller nedåt.

Så stater som erhålls efter att ha flyttat dessa drag är:

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

Återigen beräknar den totala kostnadsfunktionen för dessa tillstånd med användning av metoden som beskrivs ovan och det visar sig vara respektive 6 och 7. Vi valde staten med lägsta kostnad som är stat (1). Nästa möjliga drag kan vara Vänster, Höger eller Ner. Vi kommer inte att flytta åt vänster som vi tidigare var i det tillståndet. Så vi kan flytta åt höger eller ner.

Återigen finner vi de stater som erhållits från (1).

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

(3) leder till kostnadsfunktion lika med 6 och (4) leder till 4. Vi kommer också att överväga (2) som erhållits innan som har kostnadsfunktion lika med 7. Att välja minimum från dem leder till (4). Nästa möjliga drag kan vara Vänster eller Höger eller Ner. Vi får stater:

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)

Vi får kostnader lika med 5, 2 och 4 för (5), (6) respektive (7). Vi har också tidigare tillstånd (3) och (2) med 6 respektive 7. Vi valde lägsta kostnadstillstånd som är (6). Nästa möjliga drag är Up, och Down och klart Down kommer att leda oss till det slutliga tillståndet vilket leder till heuristiskt funktionsvärde lika med 0.

En * Sökväg genom en labyrint utan hinder

Låt oss säga att vi har följande fyra med fyra rutnät:

Låt oss anta att det här är en labyrint . Det finns dock inga väggar / hinder. Vi har bara en startpunkt (det gröna torget) och en slutpunkt (den röda fyrkanten). Låt oss också anta att vi inte kan röra oss diagonalt för att komma från grönt till rött. Så från det gröna torget, låt oss se vilka rutor vi kan flytta till och markera dem med blått:

För att välja vilken kvadrat som ska flyttas till nästa måste vi ta hänsyn till 2 heuristik:

"G" -värdet - Det är så långt bort denna nod är från den gröna fyrkanten.
Värdet "h" - Det är så långt bort denna nod är från den röda fyrkanten.
Värdet "f" - Detta är summan av "g" -värdet och "h" -värdet. Detta är det sista numret som säger till vilken nod vi ska flytta till.

För att beräkna dessa heuristik är detta formeln vi kommer att använda: distance = abs(from.x - to.x) + abs(from.y - to.y)

Detta kallas formeln "Manhattan Distance" .

Låt oss beräkna "g" -värdet för den blå fyrkanten omedelbart till vänster om den gröna fyrkanten: abs(3 - 2) + abs(2 - 2) = 1

Bra! Vi har värdet: 1. Nu, låt oss försöka beräkna "h" -värdet: abs(2 - 0) + abs(2 - 0) = 4

Perfekt. Låt oss nu få "f" -värdet: 1 + 4 = 5

Så det slutliga värdet för denna nod är "5".

Låt oss göra samma sak för alla andra blå rutor. Det stora siffran i mitten av varje kvadrat är "f" -värdet, medan siffran uppe till vänster är "g" -värdet och siffran uppe till höger är "h" -värdet:

Vi har beräknat g-, h- och f-värdena för alla blå noder. Vad väljer vi nu?

Vilken som helst har det lägsta f-värdet.

Men i det här fallet har vi två noder med samma f-värde, 5. Hur väljer vi mellan dem?

Välj helt enkelt antingen en slumpmässig eller ställ in en prioritetsuppsättning. Jag föredrar vanligtvis att ha en prioritering så: "Höger> Upp> Ner> Vänster"

En av noderna med f-värdet 5 tar oss i "Ned" -riktningen, och den andra tar oss "Vänster". Eftersom Down har högre prioritet än vänster väljer vi torget som tar oss "Down".

Jag markerar nu de noder som vi beräknade heuristiken för, men flyttade inte till, som orange och den nod som vi valde som cyan: