A* algoritmus

Sablon:Infobox algorithmSablon:Infobox algorithm Az A * ("A-csillag" -nak ejtve ) egy grafbejáró és útvonal-keresési algoritmus, amelyet teljessége, optimális hatékonysága miatt gyakran használnak a számítástechnikában. Az egyik fő gyakorlati hátránya az $O(b^{d})$ hely bonyolultsága, mivel az összes generált csomópontot tárolja a memóriában. Így a gyakorlati útválasztó rendszerekben általában olyan algoritmusokkal cserélik fel, amelyek elősegítik a gráfok bejárásában a jobb teljesítmény elérését , valamint a memóriával megkötött megközelítéseket. Sok esetben azonban az A * továbbra is a legjobb megoldás.

Peter Hart, Nils Nilsson és Bertram Raphael, a Stanford Kutatóintézet (ma SRI International )1968-ban publikálta először az algoritmust. Ez Edsger Dijkstra 1959 - es algoritmusának kiterjesztéseként tekinthető. Az A * jobb teljesítményt ér el, ha heurisztikát használ a keresés irányításához.

Történelem

Az A * -ot a Shakey the Robot útjának tervezésén dolgozó kutatók találták ki.

Az A * -ot a Shakey projekt részeként hozták létre, amelynek célja egy mobil robot felépítése volt, amely meg tudja tervezni a saját tevékenységeit. Nils Nilsson eredetileg a Graph Traverser algoritmus használatát javasolta Shakey útjának tervezéséhez. A Graph Traverser programot heurisztikus funkció vezérli $h(n),$ $n$ a csomóponttól a cél csomópontjáig becsült távolság : $g(n)$ teljesen figyelmen kívül hagyja a kezdő csomóponttól való távolságot. Bertram Raphael javasolta az összeg felhasználását, $g(n)+h(n)$ . Peter Hart megalkotta azokat a fogalmakat, amelyeket most a heurisztikus funkciók elfogadhatóságának és konzisztenciának hívunk.   Az A * -ot eredetileg a legolcsóbb útvonalak megtalálására tervezték, amikor egy út költsége a szélső költségek összege. De kimutatták, hogy az A * felhasználható bármely olyan probléma megoldására, ahol olyan optimális útvonalak megtalálásá a cél, amelyek megfelelnek a költség-algebrai feltételeknek. .

Az eredeti 1968-as A * cikkben szerepel egy tétel, miszerint egyetlen A * -hoz hasonló algoritmus kevesebb csomópontot tud kibővíteni, mint az A *, ha a heurisztikus függvény konzisztens, és az A * kötési szakadékát megfelelően választják meg. Néhány évvel később egy ″ korrekciót ″ tettek közzé amelyben azt állították, hogy nincs szükség konzisztenciára, de ez valótlannak bizonyult Dechter és Pearl által az A * optimálisságának (ma optimális hatékonyságnak nevezett) végleges tanulmányában, amely példát adott. Az A * értéke elfogadható heurisztikával rendelkezik, amely nem következetesen több csomópontot tetszőlegesen kibővít, mint egy alternatív A * -szerű algoritmus.

Leírás

Az A * egy informális keresési algoritmus,a legjobbat–először keresés egyik változata, azaz azt súlyozott gráfok szerint kell megfogalmazni: a gráf egy adott kezdő csomópontjától kezdve arra törekszik, hogy olyan utat keressen az adott célcsomóponthoz, amelynek a legkisebb a költség (a legrövidebb távolság, a legrövidebb idő, stb). Ezt úgy éri el fenntartása fa utak származó, a start csomópontot és meghosszabbításáról útvonalakat egyik szélén, addig, amíg annak megszüntetését feltétele.

A fő hurok minden iterációjánál az A * -nak meg kell határoznia, melyik útvonalát kívánja meghosszabbítani. Ezt az út költségén és a becslés alapján veszi figyelembe, ha az út egészen a célig meghosszabbodik. Pontosabban, az A * kiválasztja a minimalizálható utat

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

ahol n a pálya következő csomópontja, g(n) a kezdő csomóponttól az n ig tartó út költsége, és h(n) egy heurisztikus függvény, amely becsüli meg a legolcsóbb út költségét n től a célig. Az A * akkor fejeződik be, amikor a meghosszabbítani kívánt út egy út az indulástól a célig, vagy ha nincsenek meghosszabbítható utak. A heurisztikus funkció probléma-specifikus. Ha a heurisztikus funkció elfogadható, ami azt jelenti, hogy soha nem értékeli túl a cél eléréséhez szükséges tényleges költségeket, akkor az A * garantálja, hogy a legkevesebb költséggel jár az indulástól a célig.

Az A * tipikus megvalósítása egy prioritási sort alkalmaz a minimális (becsült) költségcsomópontok ismételt kiválasztására a kibővítéshez. Ezt a prioritási várólistát nyitott halmaznak vagy perem sornak nevezzük. Az algoritmus minden lépésénél a legkisebb f(x) értékű csomópontot eltávolítja a sorból, a szomszédainak f és g értékeit ennek megfelelően frissítik, és ezeket a szomszédokat hozzáadják a sorhoz. Az algoritmus addig folytatódik, amíg a célcsomópont alacsonyabb f értékkel rendelkezik, mint a sorban lévő bármelyik csomópont (vagy amíg a sor üres). A cél f értéke ekkor a legrövidebb út költsége, mivel a célnál a h nulla egy megengedett heurisztikában.

Az eddig leírt algoritmus csak a legrövidebb út hosszát adja meg. A tényleges lépések sorrendjének megtalálásához az algoritmus könnyen átdolgozható, hogy az útvonalon lévő minden csomópont nyomon kövesse elődjét. Az algoritmus futtatása után a záró csomópont az elődjére mutat, és így tovább, mindaddig, amíg valamelyik csomópont elődje a kezdő csomópont.

Például amikor a térképen a legrövidebb utat keressük, a h(x) a célhoz vezető egyenes vonalú távolságot képviseli, mivel fizikailag ez a lehető legkisebb távolság a két pont között.

Ha a h heurisztika kielégíti a h(x) ≤ d(x, y) + h(y) kiegészítő feltételt a grafikon minden szélén (x, y) (ahol d az adott él hosszát jelöli), akkor h monoton vagy konzisztens . Konzisztens heurisztikával garantált, hogy az A * optimális utat talál egy csomópont többszöri feldolgozása nélkül, és A * egyenértékű Dijkstra algoritmusának futtatásával csökkentett d(x, y) = d(x, y) + h(y) − h(x) költséggel d(x, y) = d(x, y) + h(y) − h(x) .

pszeudókód

A következő álkód leírja az algoritmust:

function reconstruct_path(cameFrom, current)
  total_path := {current}
  while current in cameFrom.Keys:
    current := cameFrom[current]
    total_path.prepend(current)
  return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
  // The set of discovered nodes that may need to be (re-)expanded.
  // Initially, only the start node is known.
  // This is usually implemented as a min-heap or priority queue rather than a hash-set.
  openSet := {start}

  // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
  // to n currently known.
  cameFrom := an empty map

  // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
  gScore := map with default value of Infinity
  gScore[start] := 0

  // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
  // how short a path from start to finish can be if it goes through n.
  fScore := map with default value of Infinity
  fScore[start] := h(start)

  while openSet is not empty
    // This operation can occur in O(1) time if openSet is a min-heap or a priority queue
    current := the node in openSet having the lowest fScore[] value
    if current = goal
      return reconstruct_path(cameFrom, current)

    openSet.Remove(current)
    for each neighbor of current
      // d(current,neighbor) is the weight of the edge from current to neighbor
      // tentative_gScore is the distance from start to the neighbor through current
      tentative_gScore := gScore[current] + d(current, neighbor)
      if tentative_gScore < gScore[neighbor]
        // This path to neighbor is better than any previous one. Record it!
        cameFrom[neighbor] := current
        gScore[neighbor] := tentative_gScore
        fScore[neighbor] := gScore[neighbor] + h(neighbor)
        if neighbor not in openSet
          openSet.add(neighbor)

  // Open set is empty but goal was never reached
  return failure

Megjegyzés: Ebben az álkódban, ha egy csomópontot egy úttal érnek el, eltávolítják az openSet-ből, majd később egy olcsóbb elérési útvonalon érik el, akkor az újra hozzáadódik az openSet-hez. Ez elengedhetetlen annak garantálásához, hogy a visszatérő út optimális legyen, ha a heurisztikus funkció elfogadható, de nem következetes . Ha a heurisztika konzisztens, és egy csomópontot eltávolítanak az openSet-ből, akkor az elérési út garantáltan optimális lesz, tehát ha a csomópontot ismét elérik a 'tentative_gScore <gScore [szomszéd]' teszt mindig sikertelen.

A robot mozgástervezési problémájának kezdőcsomóponttól egy célcsomópontig történő elérési út keresésének A * ábrája. Az üres körök a nyitott halmaz csomópontjait képviselik, azaz azokat, amelyeket még ki kell vizsgálni, és a kitöltött zárt halmazban vannak. Az egyes zárt csomópontok színe jelzi a távolságot a kezdetektől: minél zöldebb, annál távolabb van. Először láthatjuk, hogy az A * egyenes vonalban halad a cél felé, majd amikor akadályba ütközik, alternatív útvonalakat fedez fel a csomópontokon keresztül a nyitott készletből.

Példa

Példa egy működő A * algoritmusra, ahol a csomópontok utakkal összekötött városok és h (x) a célponthoz való egyenes távolság:

Kulcs: zöld: indítás; kék: gól; narancs: meglátogatott

Az A * algoritmus valós alkalmazásokkal is rendelkezik. Ebben a példában az élek vasutak és h (x) a nagy kör távolsága (a gömbön a lehető legrövidebb távolság) a célig. Az algoritmus utat keres Washington, DC és Los Angeles között.

A végrehajtás részletei

Számos egyszerű optimalizálás vagy megvalósítási részlet létezik, amelyek jelentősen befolyásolhatják az A * megvalósítási teljesítményét. Az első, amelyet meg kell jegyezni az, hogy a prioritási sor hogyan kezeli a kapcsolatokat, bizonyos helyzetekben, mert ez jelentős hatással lehet a teljesítményre. Ha a kapcsolatok megszakadnak,a sor LIFO módon viselkedik, akkor A * úgy viselkedik, mint egy mélységi keresés az egyenlő költségek között (elkerülve, hogy egynél több ugyanolyan optimális megoldást fedezzen fel).

Ha a keresés végén elérési út szükséges, általában minden csomópontnál hivatkozást kell megadni a csomópont szülőjére. A keresés végén ezek a referenciák felhasználhatók az optimális út visszaállítására. Ha ezeket a hivatkozásokat megtartjuk, akkor fontos lehet, hogy ugyanaz a csomópont csak egyszer jelenjen meg a prioritási sorban (mindegyik bejegyzés a csomópont eltérő útvonalának felel meg, és mindegyik eltérő költséggel rendelkezik). Általános megközelítés itt annak ellenőrzése, hogy a hozzáadandó csomópont már megjelenik-e a prioritási sorban. Ha igen, akkor a prioritási és a szülői mutatókat megváltoztatjuk, hogy azok megfeleljenek az alacsonyabb költségek útjának. A szokásos bináris halom alapú prioritási sor nem támogatja közvetlenül egyik elemének keresését sem, de kiegészíthető egy hash táblával, amely feltérképezi az elemek halomban lévő helyzetét, lehetővé téve ezzel a végrehajtáskor a prioritási művelet logaritmikus idejének csökkentését. Alternatív megoldásként egy Fibonacci-halom ugyanazokat a csökkenési prioritást élvező műveleteket hajthatja végre állandó amortizált idő alatt .

Különleges esetek

Dijkstra algoritmusa, mint egy egységes költségű keresési algoritmus további példája, tekinthető az A * speciális esetének, ahol Értelmezés sikertelen (formai hiba): {\displaystyle <semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{tmath|1=h(x) = 0}} </mi><mo stretchy="false"> {{tmath|1=h(x) = 0}} </mo><mi> {{tmath|1=h(x) = 0}} </mi><mo stretchy="false"> {{tmath|1=h(x) = 0}} </mo><mo> {{tmath|1=h(x) = 0}} </mo><mn> {{tmath|1=h(x) = 0}} </mn></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics>} h(x) = 0 minden x-re . Az általános mélységi keresés az A * használatával valósítható meg, figyelembe véve, hogy létezik egy nagyon nagy értékkel inicializált globális C számláló. Minden egyes csomópont feldolgozásakor C- t rendelünk az összes újonnan felfedezett szomszédához. Minden egyes hozzárendelés után csökkentjük a C számlálót eggyel. Így minél korábban fedez fel egy csomópontot, annál magasabb Értelmezés sikertelen (formai hiba): {\displaystyle <semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{tmath|h(x)}} </mi><mo stretchy="false"> {{tmath|h(x)}} </mo><mi> {{tmath|h(x)}} </mi><mo stretchy="false"> {{tmath|h(x)}} </mo></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics>} h(x) értéke. Mind Dijkstra algoritmusa, mind a mélyreható keresés hatékonyabban megvalósítható anélkül, hogy bele kellene foglalni Értelmezés sikertelen (formai hiba): {\displaystyle <semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{tmath|h(x)}} </mi><mo stretchy="false"> {{tmath|h(x)}} </mo><mi> {{tmath|h(x)}} </mi><mo stretchy="false"> {{tmath|h(x)}} </mo></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics>} h(x) értékét minden csomóponton.

Tulajdonságok

Végesség és teljesség

A nem negatív élsúlyú véges gráfokon garantált, hogy az A * véget ér és teljes, azaz mindig megtalálja a megoldást (egy utat a kezdetektől a célig), ha létezik. Végtelen grafikonokon, véges elágazási tényezővel és nulla ponttól határolt élköltségekkel ( ${\textstyle d(x,y)>\varepsilon >0}$ néhány rögzített $\varepsilon$ ) esetén az A * garantáltan csak akkor szűnik meg, ha van megoldás.

Az elfogadhatóságról

A keresési algoritmus elfogadhatónak bizonyul, ha garantáltan megtalálja az optimális megoldást. Ha az A * által használt heurisztikus funkció elfogadható, akkor A * megengedett. Ennek intuitív „bizonyítéka” a következő:

Amikor A * befejezi a keresést, megtalált egy utat az indulástól a célig, amelynek tényleges költsége alacsonyabb, mint az indulástól a célig tartó bármely út becsült költsége bármely nyitott csomóponton (a csomópont f értéke). Ha a heurisztika elfogadható, ezek a becslések optimisták (nem egészen - lásd a következő bekezdést), így az A * biztonságosan figyelmen kívül hagyhatja ezeket a csomópontokat, mert nem vezethetnek olcsóbb megoldáshoz, mint amelyik már megvan. Más szavakkal, az A * soha nem hagyja figyelmen kívül az alacsonyabb költségekkel járó út lehetőségét a kezdetektől a célig, ezért folytatja a kutatást, amíg ilyen lehetőségek léteznek.

A tényleges bizonyíték egy kicsit inkább érintett, mert a nyitott csomópontok f értékei nem garantálják, hogy optimálisak, még akkor se, ha a heurisztika elfogadható. Ennek oka az, hogy a nyitott csomópontok g értéke nem garantáltan optimális, tehát az összeg g+h nem garantált, hogy optimális.

Optimális hatékonyság

Ha minden probléma P és minden algoritmus A 'Alt, a csomópontok halmaza bővül. A megoldásában P egy részhalmaza (esetleg egyenlő) az A '-vel kibővített csomóponthalmazból a P megoldásában. Az A * optimális hatékonyságának végleges vizsgálata Rina Dechter és Judea Pearl eredménye. Az Alts és a P sokféle meghatározását tekintették úgy, hogy az A * heurisztikája pusztán elfogadható, vagy következetes és elfogadható. A legérdekesebb pozitív eredmény, amelyet bebizonyítottak, az, hogy az A * következetes heurisztikával, optimálisan hatékony az összes elfogadható A * -hoz hasonló keresési algoritmus szempontjából az összes ″ nem patológiai ″ keresési probléma esetén. A nem patológiás probléma fogalmán az értjük, amit most ″ a nyakkendő megszorításán ″ értünk. Ez az eredmény nem érvényes, ha az A * heurisztikája elfogadható, de nem következetes. Ebben az esetben Dechter és Pearl megmutatta, hogy léteznek olyan megengedett A * -algoritmusok, amelyek bizonyos nem patológiai problémák esetén önkényesen kevesebb csomópontot tudnak kibővíteni, mint az A *.

Optimális a hatékonyság,ha a csomópontok halmaza expandált és nem a száma, a csomópontok bővülnek ( az A * iterációinak száma). Ha a heurisztika elfogadható, de nem következetes, akkor egy csomópontot A * -gal meghosszabbíthatunk, a legrosszabb esetben pedig exponenciálisan növelhetünk. Ilyen körülmények között Dijkstra algoritmusa nagymértékben felülmúlhatja az A * -ot.

Határokon átnyúló pihenés

Egy A * keresés, amely egy heurisztikát használ, amely 5,0 (= ε) szorzata egy konzisztens heurisztikának, és szuboptimális útvonalat kap.

Noha az elfogadhatósági kritérium garantálja az optimális megoldási utat, ez azt is jelenti, hogy az A * -nak meg kell vizsgálnia az összes olyan érdemes utat, amellyel megtalálja az optimális utat. A hozzávetőleges legrövidebb utak kiszámításához az elfogadhatóság kritériumának enyhítésével fel lehet gyorsítani a keresést az optimalitás rovására. Gyakran szeretnénk megkötni ezt az egyességet, hogy garantáljuk, hogy a megoldás útja nem rosszabb, mint az optimális megoldási út (1 + ε ) szorzata. Ezt az új garanciát ε- elfogadhatónak nevezzük.

Számos ε- elfogadható algoritmus létezik:

• Súlyozott A * / statikus súlyozás. Ha H _a (n) egy megengedhető heurisztikus függvény, a súlyozott változata az A * keres egy h_w(n) = ε h_a(n) ε > 1 felhasználási heurisztikus funkciót, és elvégezi az A * keresést, mint általában (ami végül gyorsabban történik, mint a h használata _, mivel kevesebb csomópont van kibontva). Ennélfogva a keresési algoritmus által megtalált út legfeljebb ε-szerű költséggel járhat, mint a grafikon legolcsóbb útja.

• A dinamikus súlyozás a költségfüggvényt használja : f(n) = g(n) + (1 + εw(n))h(n) , ahol $w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{otherwise}}\end{cases}}$, és hol Értelmezés sikertelen (formai hiba): {\displaystyle <semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{tmath|d(n)}} </mi><mo stretchy="false"> {{tmath|d(n)}} </mo><mi> {{tmath|d(n)}} </mi><mo stretchy="false"> {{tmath|d(n)}} </mo></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics>} d(n) a keresés mélysége, N pedig a megoldási út várható hossza.

• A mintavételezett dinamikus súlyozás a csomópontok mintavételével a heurisztikus hibát jobban becsüli meg és távolítja el.

• $A_{\varepsilon }^{*}$ . két heurisztikus függvényt használ. Az első a FOCAL lista, amelyet a jelölt csomópontok kiválasztására használunk, a második h _F pedig a legígéretesebb csomópont kiválasztására szolgál a FOCAL listából.

• A _ε csomópontot választja ki a funkcióval A f(n) + B h_F(n) , ahol A és B konstans. Ha nem lehet csomópontot kiválasztani, akkor az algoritmus visszalép a funkcióhoz C f(n) + D h_F(n)Értelmezés sikertelen (formai hiba): {\displaystyle <semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{tmath|C f(n) + D h_F(n)}} </mi><mi> {{tmath|C f(n) + D h_F(n)}} </mi><mo stretchy="false"> {{tmath|C f(n) + D h_F(n)}} </mo><mi> {{tmath|C f(n) + D h_F(n)}} </mi><mo stretchy="false"> {{tmath|C f(n) + D h_F(n)}} </mo><mo> {{tmath|C f(n) + D h_F(n)}} </mo><mi> {{tmath|C f(n) + D h_F(n)}} </mi><msub><mi> {{tmath|C f(n) + D h_F(n)}} </mi><mrow class="MJX-TeXAtom-ORD"><mi> {{tmath|C f(n) + D h_F(n)}} </mi></mrow></msub><mo stretchy="false"> {{tmath|C f(n) + D h_F(n)}} </mo><mi> {{tmath|C f(n) + D h_F(n)}} </mi><mo stretchy="false"> {{tmath|C f(n) + D h_F(n)}} </mo></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics>} , ahol C és D konstans.

• Az AlphA * megpróbálja elősegíteni az első mélységű kiaknázást azáltal, hogy a nemrégiben kibővített csomópontokat részesíti előnyben. Az AlphA * a költségfüggvényt használja $f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)$, ahol $w_{\alpha }(n)={\begin{cases}\lambda &g(\pi (n))\leq g({\tilde {n}})\\\Lambda &{\text{otherwise}}\end{cases}}$, ahol λ és Λ konstans $\lambda \leq \Lambda$, Π (n) a szülő a N, és n jelentése a legutóbb expandált csomópontot.

Bonyolultság

Az A * időbeli összetettsége a heurisztikától függ. A korlátlan keresési hely legrosszabb esetben a kibontott csomópontok száma exponenciális a megoldás mélységében (a legrövidebb út) d : O(b^d), ahol b az elágazási tényező (az utódok átlagos száma államonként) ). Ez feltételezi, hogy egy célállapot egyáltalán létezik, és a kiindulási állapotból elérhető ; ha nem, és az állapottér végtelen, akkor az algoritmus nem fejeződik be.

A heurisztikus funkció nagymértékben befolyásolja az A * keresés gyakorlati végrehajtását, mivel egy jó heurisztika lehetővé teszi, hogy az A * sok olyan b^d csomópontot megrajzoljon, amelyeket egy tudatlan keresés kiterjeszt. Minőségét kifejezhetjük a tényleges b* elágazási tényezővel, amelyet empirikusan meg lehet határozni egy probléma esetén a kibővített csomópontok számának, N és a megoldás mélységének megmérésével, majd a megoldással

$N+1=1+b^{*}+(b^{*})^{2}+\dots +(b^{*})^{d}.$

A jó heurisztika alacsony effektív elágazási tényezővel rendelkezik (az optimális b* = 1 ).

Az idő bonyolultsága polinomiális, ha a keresési terület egy fa, egyetlen célállapot van, és a h heurisztikus függvény megfelel a következő feltételnek:

$|h(x)-h^{*}(x)|=O(\log h^{*}(x))$

ahol h^* az optimális heurisztika, az x től a célig való eljutás pontos költsége. Más szóval, a h hibája nem fog gyorsabban növekedni, mint a "tökéletes heurisztikus" h^* logaritmusa, amely visszatér az x től a célig tartó valódi távolságig.

A tér összetettsége A * nagyjából ugyanaz, mint az összes többi grafikon keresési algoritmus, mivel ez tartja az összes generált csomópontot a memóriában. A gyakorlatban ez az A * keresés legnagyobb hátránya, ami a memóriával összefüggő heurisztikus keresések kifejlesztéséhez vezet, mint például az I * Iteratív mélyítése, A * határolt memória és SMA * .

Alkalmazások

Az A * -ot gyakran használják az általános útmeghatározási problémára olyan alkalmazásokban, mint például a videojátékok, de eredetileg egy általános gráf-átjárási algoritmusként tervezték. Alkalmazásokat talál különféle problémákban, beleértve a sztochasztikus nyelvtanok elemzésével kapcsolatos problémát az NLP-ben . Más esetek között szerepel egy információs keresés online tanulással.

Kapcsolatok más algoritmusokkal

Az A * különbséget tesz egy kapzsi, és elsőként kereső algoritmus között úgy, hogy figyelembe veszi a már megtett költségeket / távolságot, g(n) .

A Dijkstra algoritmusának néhány általános változatát az A * speciális esetének tekinthetjük, ahol heurisztikus $h(n)=0$ minden csomópontra; pedig Dijkstra és A * egyaránt a dinamikus programozás különleges esetei. Maga az A * az ág általános és általános megkötésének különleges esete.

Változatok

• Bármikor A * vagy bármikor javítható A * (ARA *)
• Bármikor Dynamic A *
• A * blokk
• D *
• D mező *
• Rojt
• Perem megtakarítás * (FSA *)
• Általános adaptív A * (GAA *)
• Növekményes heurisztikus keresés
• Információs keresés
• Iteratív elmélyítés A * (IDA *)
• Ugráspont keresés
• Egész életen át tartó tervezés A * (LPA *)
• Szorzóval gyorsított A * (MAA *)
• Új kétirányú A * (NBA *)
• Egyszerűsített memória, határolt A * (SMA *)
• Valós idejű A *
• Theta *
• Időkorlátozott A * (TBA *)

Az A * egy kétirányú keresési algoritmushoz is adaptálható. Különös figyelmet kell fordítani a megállási kritériumra.

Lásd még

• Szélességi-első keresés
• Mélységi-első keresés
• Bármely szögű útvonaltervezés, keressen olyan útvonalakat, amelyek nem korlátozódnak a gráf szélei mentén, hanem bármilyen szöget felvehetnek

További irodalom

• Nilsson, N. J.. Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company (1980). ISBN 978-0-935382-01-3 

Külső linkek

• Tiszta vizuális A * magyarázat, tanácsokkal és gondolatokkal az ösvény-felfedezésről
• Változat az A * -on, úgynevezett hierarchikus útmeghatározó A * -on (HPA *)