A* search algorithm

Angol

Főnév

A* search algorithm (tsz. A* search algorithms)

1. (informatika) A* algoritmus

---

Az A* (ejtsd: „A csillag”) egy útkereső algoritmus, amelyet széles körben használnak mesterséges intelligenciában, robotikában, játékszoftverekben, térképekben és grafokban a legrövidebb út megtalálására egy kezdőpont és egy célpont között.

Az A* algoritmus az egyik leghatékonyabb és legmegbízhatóbb keresési algoritmus, amely ötvözi a Greedy Best-First Search és a Dijkstra-algoritmus előnyeit.

---

🚀 1. Alapötlet

Az A* algoritmus a csomópontokhoz két értéket rendel:

• g(n) – a kezdőponttól a csomópontig megtett út költsége (eddig megtett út)
• h(n) – egy heurisztika, amely becsüli a csomóponttól a célhoz vezető út költségét

A keresés során a következő érték alapján rangsorolja a csomópontokat:

$$f(n)=g(n)+h(n)$$

Az algoritmus mindig azt a csomópontot vizsgálja meg következőként, amelynek az ${\textstyle f(n)}$ értéke a legkisebb.

---

📦 2. A* működése lépésekben

1. Tedd a kezdőpontot az Open listába (vizsgálatra váró csomópontok)
2. Az Open listából válaszd ki a legkisebb f(n) értékű csomópontot
3. Ha ez a cél, akkor út megtalálva
4. Egyébként:
   • Mozgasd a csomópontot a Closed listába (már feldolgozott)
   • Vizsgáld meg a szomszédait:
     • Számold ki a g(n), h(n), f(n) értékeket
     • Ha a csomópont már az Open listában van jobb úttal, frissítsd
     • Ha nincs rajta, tedd fel az Open listára
5. Ismételd, amíg Open lista üres vagy cél elérve

---

💡 3. Heurisztikák – a h(n) becslés

A sikeres A* működésének kulcsa a jó heurisztika:

• Admissible: sosem becsli túl a valódi távolságot (pl. mindig kisebb vagy egyenlő)
• Consistent (monoton): teljesül, hogy ${\textstyle h(n)\leq c(n,n')+h(n')}$

Példák:

Helyzet	h(n) (heurisztika)
Rács (4 irány)	Manhattan-távolság: (	x_1 - x_2	+	y_1 - y_2	)
Rács (8 irány)	Diagonális távolság
Térkép (valóságos)	Euklideszi távolság: ${\textstyle {\sqrt {(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}}}$

---

📍 4. Példa

Rács (grid) – kezdő: A(0,0), cél: B(3,3)

Heurisztika: Manhattan-távolság

Pont	g(n)	h(n)	f(n)
A(0,0)	0	6	6
… következő

Az algoritmus azokat a csomópontokat vizsgálja meg, amelyek a legkisebb ${\textstyle f(n)}$ értékűek, és folyamatosan közelít a célhoz.

---

🧮 5. Pseudokód

function A*(start, goal):
    open_set := {start}
    came_from := empty map
    g_score[start] := 0
    f_score[start] := h(start)

    while open_set not empty:
        current := node in open_set with lowest f_score

        if current = goal:
            return reconstruct_path(came_from, current)

        remove current from open_set
        for each neighbor of current:
            tentative_g = g_score[current] + dist(current, neighbor)
            if tentative_g < g_score[neighbor]:
                came_from[neighbor] := current
                g_score[neighbor] := tentative_g
                f_score[neighbor] := g_score[neighbor] + h(neighbor)
                if neighbor not in open_set:
                    add neighbor to open_set
    return failure

---

✅ 6. Előnyök

• Optimális megoldás: ha h(n) admissible, akkor garantáltan a legrövidebb utat találja meg
• Hatékonyabb, mint Dijkstra, ha jó a heurisztika
• Általánosítható sokféle problémára (játék, robot, térkép)

---

⚠️ 7. Hátrányok

• Tárigényes: az Open és Closed listák sok memóriát igényelhetnek
• Sebesség: nagy gráfokon lelassulhat, ha h(n) túl gyenge
• Heurisztika tervezése nem mindig egyszerű

---

🤖 8. Alkalmazási példák

• Google Maps: útvonaltervezés
• Játékfejlesztés: NPC mozgás, labirintus keresés
• Robotika: akadálykerülés, mozgástervezés
• Webrobotok: keresési problémák optimalizálása
• AI problémák: puzzle-k, gráfoptimalizálás, logikai játékok

---

🧠 9. Változatok

Algoritmus	Leírás
Dijkstra	Mint A*, de nincs h(n) (h = 0)
Greedy Best-First Search	f(n) = h(n) – gyors, de nem garantáltan optimális
IDA*	Iteratív mélységkorlátos A*, kevesebb memória
Theta*	A* módosítás, amely átlós mozgást is enged
Weighted A*	f(n) = g(n) + w × h(n) – gyorsabb, de nem mindig optimális

---

🧪 10. Összefoglalás

Az A* algoritmus a leghatékonyabb útkeresési algoritmusok egyike, amely pontos eredményeket ad, ha a heurisztika megfelelően van megválasztva. Kombinálja az ismert legolcsóbb út nyilvántartását a jövőbeni költség jóslásával, így biztosítja az optimalitást és hatékonyságot. Az A* máig az egyik legfontosabb algoritmus az AI és a számítástudomány világában.

További információk

• A* search algorithm - Szótár.net (en-hu)
• A* search algorithm - Sztaki (en-hu)
• A* search algorithm - Merriam–Webster
• A* search algorithm - Cambridge
• A* search algorithm - WordNet
• A* search algorithm - Яндекс (en-ru)
• A* search algorithm - Google (en-hu)
• A* search algorithm - Wikidata
• A* search algorithm - Wikipédia (angol)