A* search algorithm

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.

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:

$${\displaystyle 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.

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

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')}$

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}}}}$

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.

function A*(start, goal):
    open_set := {start}
    came_from := empty map
    g_score := 0
    f_score := 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 + dist(current, neighbor)
            if tentative_g < g_score:
                came_from := current
                g_score := tentative_g
                f_score := g_score + h(neighbor)
                if neighbor not in open_set:
                    add neighbor to open_set
    return failure

• 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)

• 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ű

• 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

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.

• 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)