A* søkealgoritmen er en populær stifinding og graf traversal teknikk som brukes i ulike programmer som robotikk, spillutvikling og nettverksrute. Den kombinerer funksjonene i ensartet-kost søk og grådig best-første søk for å effektivt finne den korteste banen fra en startnode til en målnode. Denne guiden gir en trinn-for-trinn prosessen for å implementere A * algoritmen med eksempler beregninger for å illustrere hvert trinn.

Forstå A* Algoritmen

A* algoritmen bruker en kostnadsfunksjon, f(n) = g(n) + h(n), hvor:

  • ]g(n): Den faktiske kostnaden fra startnoden til node n.
  • h(n): Det heuristiske estimatet av kostnadene fra node n til målet.

Algoritmen utforsker noder med den laveste f(n) verdien, balansere faktiske og estimerte kostnader for å finne den optimale banen effektivt.

Trinn-for-steg-implementasjon

Følg disse trinnene for å implementere A* algoritmen:

1. Initier åpne og lukkede lister

Den åpne listen inneholder noder som skal evalueres, fra start med den opprinnelige noden. Den lukkede listen inneholder noder som allerede er evaluert.

2. Velg noden med den laveste f(n)

Fjern denne noden fra den åpne listen og legg den til den stengte listen.

3. Opprett naboknuter

Beregn g( n) og h( n) for hver nabo. Hvis en nabo ikke er i den åpne listen eller har en lavere g( n), oppdaterer verdiene og angir sin forelder til den aktuelle noden.

4. Gjenta til målet er nådd

Fortsett prosessen til målnoden er lagt til den lukkede listen, noe som indikerer den korteste banen er funnet.

Eksempelberegninger

Tenk på et enkelt rutenett med startnode A og målnode G. Den heuristiske h(n) er rettlinjeavstanden. Initial beregninger er som følger:

Start ved node A, g(A) = 0, h(A) = 4. F(A) = 4. Naboknutene B og C vurderes:

For node B: g(B) = g(A) + kostnad(A, B) = 0 + 1 = 1, h(B) = 3, f(B) = 4.

For node C: g(C) = 1, h(C) = 2, f(C) = 3. Node C har den laveste f(n), så den er valgt neste.

Denne prosessen fortsetter, oppdaterer g, h og f-verdier, inntil målnoden G er nådd med den korteste banen identifisert.