Steg-för-steg guide till att genomföra en * Sök Algoritm med Exempel Beräkningar

A * sökalgoritmen är en populär banfinding och graftraversal teknik som används i olika applikationer som robotik, spelutveckling och nätverksruttning. Det kombinerar funktionerna i uniform-kostnadsökning och giriga bäst-först-sökning för att effektivt hitta den kortaste vägen från en startnod till en målnod. Denna guide ger en steg-för-steg-process för att genomföra A *-algoritmen med exempel beräkningar för att illustrera varje steg.

Förstå A * Algoritmen

A*-algoritmen använder en kostnadsfunktion, f(n) = g(n) + h(n), där:

Algoritmen utforskar noder med det lägsta f(n) värdet, balansera faktiska och uppskattade kostnader för att hitta den optimala vägen effektivt.

Steg-för-steg-implementering

Följ dessa steg för att implementera A*-algoritmen:

1. Initiera öppna och stängda listor

Den öppna listan innehåller noder som ska utvärderas, med början med den ursprungliga noden. Den stängda listan innehåller noder som redan utvärderats.

2. Välj noden med lägsta f(n)

Ta bort denna nod från den öppna listan och lägg till den i den stängda listan.

3. Generate grannnoder

Beräkna g(n) och h(n) för varje granne. Om en granne inte finns i den öppna listan eller har en lägre g(n), uppdatera sina värden och ställa in sin förälder till den nuvarande noden.

Upprepa tills målet nås

Fortsätt processen tills målnoden läggs till i den stängda listan, vilket indikerar att den kortaste vägen har hittats.

Exempel Beräkningar

Tänk på ett enkelt rutnät med startnod A och målnod G. Den heuristiska h(n) är det raka avståndet. Initiala beräkningar är följande:

Börjar vid nod A, g(A) = 0, h(A) = 4. f(A) = 4. De närliggande noderna B och C utvärderas:

För nod B: g(B) = g(A) + cost(A, B) = 0 + 1 = 1, h(B) = 3, f(B) = 4.

För nod C: g(C) = 1, h(C) = 2, f(C) = 3. Nod C har den lägsta f(n), så det väljs nästa.

Denna process fortsätter, uppdatering av g, h och f-värden, tills målnoden G uppnås med den kortaste vägen identifierad.