Algoritmul de căutare A* este o tehnică populară de căutare și de trecere grafică utilizată în diferite aplicații, cum ar fi robotica, dezvoltarea de jocuri și rutarea rețelei. Acesta combină caracteristicile de căutare uniform-cost și cele mai lacome cele mai bune-prima căutare pentru a găsi eficient cea mai scurtă cale de la un nod de pornire la un nod de obiectiv. Acest ghid oferă un proces pas cu pas pentru a implementa algoritmul A* cu calcule de exemplu pentru a ilustra fiecare etapă.

Înțelegerea Algoritmului A*

Algoritmul A* utilizează o funcție de cost, f(n) = g(n) + h(n), unde:

  • g [n] Costul efectiv de la nodul de pornire la nod n.
  • h [n]] Estimarea euristică a costului de la nod la obiectiv.

Algoritmul explorează noduri cu cea mai mică valoare f (n), echilibrând costurile reale și estimate pentru a găsi calea optimă în mod eficient.

Punerea în aplicare pas cu pas

Urmați acești pași pentru a implementa algoritmul A*:

1. Inițializează listele deschise și închise

Lista deschisă conține noduri care trebuie evaluate, începând cu nodul inițial. Lista închisă conține noduri deja evaluate.

2. Selectaţi nodul cu cel mai mic f(n)

Scoate acest nod din lista deschisă și adaugă-l pe lista închisă.

3. Generarea nodurilor învecinate

Calculați g(n) și h(n) pentru fiecare vecin. Dacă un vecin nu este în lista deschisă sau are un g mai mic (n), actualizați valorile sale și setați-l pe părintele său la nodul actual.

4. Repetaţi până când obiectivul este atins

Continuați procesul până când nodul de obiectiv este adăugat pe lista închisă, indicând cea mai scurtă cale a fost găsită.

Exemplu de calcul

Luați în considerare o grilă simplă cu nodul de pornire A și nodul de gol G. Euristul h(n) este distanța de linie dreaptă. Calculele inițiale sunt după cum urmează:

Începând de la nodul A, g(A) = 0, h(A) = 4. Nodulii B și C învecinate sunt evaluați:

Pentru nodul B: g(B) = g(A) + cost(A, B) = 0 + 1 = 1, h(B) = 3, f(B) = 4.

Pentru nodul C: g(C) = 1, h(C) = 2, f(C) = 3. Nodul C are cel mai mic f(n), astfel încât este selectat următorul.

Acest proces continuă, actualizarea valorilor g, h și f, până când nodul de obiectiv G este atins cu cea mai scurtă cale identificată.