* Vyhledávací algoritmus - A* search algorithm

Třída	Vyhledávací algoritmus
Datová struktura	Graf
Nejhorší případ výkon	${ displaystyle O (| E |) = O (b ^ {d})}$
Nejhorší případ složitost prostoru	${ displaystyle O (| V |) = O (b ^ {d})}$

A* (vyslovuje se „A-star“) je a přechod grafu a hledání cesty algoritmus, který se díky své úplnosti, optimalitě a optimální efektivitě často používá v mnoha oblastech informatiky.^[1] Jednou z hlavních praktických nevýhod je jeho ${ displaystyle O (b ^ {d})}$ složitost prostoru, protože ukládá všechny generované uzly do paměti. Prakticky tedy cestovní směrovací systémy, je obecně překonán algoritmy, které mohou předem zpracovat graf a dosáhnout tak lepšího výkonu,^[2] stejně jako přístupy vázané na paměť; A * je však v mnoha případech stále nejlepším řešením.^[3]

Peter Hart, Nils Nilsson a Bertram Raphael Stanfordského výzkumného ústavu (nyní SRI International ) poprvé publikoval algoritmus v roce 1968.^[4] Lze to považovat za rozšíření Edsger Dijkstra 1959 algoritmus. A * dosahuje lepšího výkonu používáním heuristika řídit jeho vyhledávání.

Dějiny

A * vynalezli vědci pracující na plánování tras robotem Shakey.

A * byl vytvořen jako součást projekt Shakey, jehož cílem bylo postavit mobilního robota, který by mohl plánovat své vlastní akce. Nils Nilsson původně navrhoval použití algoritmu Graph Traverser^[5] pro Shakeyho plánování cesty.^[6] Graph Traverser je veden heuristickou funkcí h(n), odhadovaná vzdálenost od uzlu n do uzlu cíle: zcela ignoruje G(n), vzdálenost od počátečního uzlu do n. Bertram Raphael navrhl použít součet, G(n) + h(n).^[6] Peter Hart vynalezl koncepty, které nyní nazýváme přípustnost a konzistence heuristických funkcí. A * byl původně navržen pro hledání cest s nejnižšími náklady, když cena cesty je součtem jejích nákladů, ale ukázalo se, že A * lze použít k nalezení optimálních cest pro jakýkoli problém splňující podmínky nákladové algebry.^[7]

Originální papír A * z roku 1968^[4] obsahoval teorém o tom, že žádný algoritmus podobný *^[8] by mohlo rozšířit méně uzlů než A *, pokud je heuristická funkce konzistentní a je vhodně zvoleno pravidlo rozbití tie * A *. „Oprava“ byla zveřejněna o několik let později^[9] prohlašovat, že konzistence není nutná, ale toto se ukázalo jako nepravdivé v Dechterově a Pearlově definitivní studii optimality A * (nyní nazývané optimální účinnost), která poskytla příklad A * s heuristikou, která byla přípustná, ale ne důsledná libovolně více uzlů než alternativní algoritmus podobný *.^[10]

Popis

A * je informovaný vyhledávací algoritmus nebo nejlepší první vyhledávání, což znamená, že je formulován ve smyslu vážené grafy: od konkrétního začátku uzel grafu si klade za cíl najít cestu k danému cílovému uzlu s nejmenšími náklady (nejmenší ujetá vzdálenost, nejkratší čas atd.). Dělá to udržováním a strom cest pocházejících z počátečního uzlu a rozšiřujících tyto cesty o jednu hranu po druhé, dokud není splněno kritérium ukončení.

Při každé iteraci své hlavní smyčky musí A * určit, kterou ze svých cest rozšířit. Činí tak na základě nákladů na cestu a odhadu nákladů potřebných k prodloužení cesty až k cíli. Konkrétně A * vybere cestu, která minimalizuje

${ displaystyle f (n) = g (n) + h (n)}$

kde n je další uzel na cestě, G(n) je cena cesty z počátečního uzlu do n, a h(n) je heuristický funkce, která odhaduje náklady na nejlevnější cestu z n do cíle. A * končí, když cesta, kterou se rozhodne prodloužit, je cesta od začátku k cíli nebo pokud neexistují žádné cesty způsobilé k prodloužení. Heuristická funkce je specifická pro daný problém. Pokud je heuristická funkce přípustný, což znamená, že nikdy nadhodnocuje skutečné náklady na dosažení cíle, je zaručeno, že A * vrátí cestu s nejnižšími náklady od začátku k cíli.

Typické implementace A * použití a prioritní fronta provést opakovaný výběr uzlů s minimální (odhadovanou) cenou k rozšíření. Tato prioritní fronta je známá jako otevřená sada nebo třásně. V každém kroku algoritmu uzel s nejnižší F(X) hodnota je odstraněna z fronty, F a G hodnoty jeho sousedů jsou odpovídajícím způsobem aktualizovány a tito sousedé jsou přidáni do fronty. Algoritmus pokračuje, dokud není odstraněn uzel (tedy uzel s nejnižším F hodnota ze všech okrajových uzlů) je cílový uzel.^[A] The F hodnotou tohoto cíle jsou pak také náklady na nejkratší cestu od té doby h v cíli je nula v přípustné heuristice.

Doposud popsaný algoritmus nám dává pouze délku nejkratší cesty. Chcete-li najít skutečnou sekvenci kroků, lze algoritmus snadno revidovat, aby každý uzel na cestě sledoval svého předchůdce. Po spuštění tohoto algoritmu bude koncový uzel ukazovat na svého předchůdce atd., Dokud nebude předchůdcem některého uzlu počáteční uzel.

Například při hledání nejkratší trasy na mapě h(X) může představovat přímá vzdálenost k cíli, protože to je fyzicky nejmenší možná vzdálenost mezi kterýmikoli dvěma body. Pro mapu mřížky z videohry použijte Vzdálenost na Manhattanu nebo se oktilní vzdálenost zlepší v závislosti na sadě dostupných pohybů (4-cestný nebo 8-cestný).

Pokud heuristický h splňuje další podmínku h(X) ≤ d(X, y) + h(y) pro každou hranu (X, y) grafu (kde d označuje délku této hrany) h je nazýván monotónní nebo konzistentní. Díky konzistentní heuristice je zaručeno, že A * najde optimální cestu bez zpracování jakéhokoli uzlu více než jednou a A * je ekvivalentní spuštění Dijkstrův algoritmus s snížené náklady d '(X, y) = d(X, y) + h(y) − h(X).

Pseudo kód

Následující pseudo kód popisuje algoritmus:

funkce rekonstruovat_cesta(přišel z, proud)    celková_cesta := {proud}    zatímco proud v přišel z.Klíče:        proud := přišel z[proud]        celková_cesta.předřadit(proud)    vrátit se celková_cesta// A * najde cestu od začátku k cíli.// h je heuristická funkce. h (n) odhaduje náklady na dosažení cíle z uzlu n.funkce Hvězda(Start, fotbalová branka, h)    // Sada objevených uzlů, které bude možná nutné (znovu) rozšířit.    // Zpočátku je znám pouze počáteční uzel.    // Toto se obvykle implementuje jako min-halda nebo prioritní fronta, nikoli jako hash.    openSet := {Start}    // Pro uzel n je cameFrom [n] uzel, který jej bezprostředně předchází na nejlevnější cestě od začátku    // až n aktuálně známé.    přišel z := an prázdný mapa    // U uzlu n je gScore [n] cena nejlevnější cesty od začátku do aktuálně známých n.    gScore := mapa s výchozí hodnota z Nekonečno    gScore[Start] := 0    // Pro uzel n, fScore [n]: = gScore [n] + h (n). fScore [n] představuje náš současný nejlepší odhad    // jak krátká může být cesta od začátku do konce, pokud prochází n.    fScore := mapa s výchozí hodnota z Nekonečno    fScore[Start] := h(Start)    zatímco openSet je ne prázdný        // K této operaci může dojít v čase O (1), pokud je openSet halda min nebo prioritní fronta        proud := the uzel v openSet mít the Nejnižší fScore[] hodnota        -li proud = fotbalová branka            vrátit se rekonstruovat_cesta(přišel z, proud)        openSet.Odstranit(proud)        pro každý soused z proud            // d (aktuální, soused) je váha hrany od aktuálního k sousedovi            // tentative_gScore je vzdálenost od začátku k sousedovi prostřednictvím proudu            nezávazně_g skóre := gScore[proud] + d(proud, soused)            -li nezávazně_g skóre < gScore[soused]                // Tato cesta k sousedovi je lepší než kterákoli předchozí. Zaznamenejte to!                přišel z[soused] := proud                gScore[soused] := nezávazně_g skóre                fScore[soused] := gScore[soused] + h(soused)                -li soused ne v openSet                    openSet.přidat(soused)    // Otevřená sada je prázdná, ale cíle nebylo nikdy dosaženo    vrátit se selhání

Poznámka: V tomto pseudokódu, pokud je uzel dosažen jednou cestou, odstraněn z openSet a následně dosažen levnější cestou, bude přidán do openSet znovu. To je nezbytné k zajištění, že vrácená cesta je optimální, pokud je heuristická funkce přípustný ale ne konzistentní. Pokud je heuristika konzistentní, je při odebrání uzlu z openSetu zaručena optimální cesta k němu, takže test ‚tentative_gScore

Ilustrace hledání A * pro hledání cesty z počátečního uzlu do uzlu cíle v a robot plánování pohybu problém. Prázdné kruhy představují uzly v otevřená sada, tj. ty, které zbývají prozkoumat, a naplněné jsou v uzavřené sadě. Barva na každém uzavřeném uzlu označuje vzdálenost od začátku: zelenější, čím dále. Jeden může nejprve vidět, jak se A * pohybuje po přímce ve směru k cíli, pak při nárazu na překážku zkoumá alternativní cesty uzly z otevřené sady.

Viz také: Dijkstrův algoritmus

Příklad

Příkladem algoritmu A * v akci, kde uzly jsou města spojená se silnicemi a h (x) je přímka vzdálenost k cílovému bodu:

Klíč: zelená: start; modrá: cíl; oranžová: navštíveno

Algoritmus A * má také aplikace v reálném světě. V tomto příkladu jsou hrany železnice a h (x) je vzdálenost velkého kruhu (nejkratší možná vzdálenost na kouli) k cíli. Algoritmus hledá cestu mezi Washingtonem, DC a Los Angeles.

Podrobnosti implementace

Existuje celá řada jednoduchých optimalizací nebo podrobností implementace, které mohou významně ovlivnit výkon implementace A *. První detail, který je třeba si uvědomit, je, že způsob, jakým fronta priorit zpracovává vazby, může mít v některých situacích významný vliv na výkon. Pokud jsou vazby přerušeny, fronta se chová v LIFO způsobem se A * bude chovat jako hloubkové vyhledávání mezi cestami se stejnými náklady (vyhýbání se zkoumání více než jednoho stejně optimálního řešení).

Když je na konci hledání vyžadována cesta, je běžné uchovat u každého uzlu odkaz na nadřízeného uzlu. Na konci hledání lze tyto odkazy použít k obnovení optimální cesty. Pokud jsou tyto odkazy zachovány, může být důležité, aby se stejný uzel neobjevil v prioritní frontě více než jednou (každá položka odpovídá jiné cestě k uzlu a každá s jinými náklady). Standardním přístupem je zde zkontrolovat, zda se uzel, který má být přidán, již objeví ve frontě priorit. Pokud ano, změní se prioritní a nadřazené ukazatele tak, aby odpovídaly cestě s nižšími náklady. Standard binární hromada založená prioritní fronta přímo nepodporuje operaci hledání jednoho z jejích prvků, ale lze ji rozšířit pomocí a hash tabulka který mapuje prvky na jejich pozici v haldě, což umožňuje provádění této operace s prioritou snížení v logaritmickém čase. Alternativně a Fibonacciho hromada může provádět stejné operace s prioritou snižování v konstantě amortizovaný čas.

Speciální případy

Dijkstrův algoritmus Jako další příklad vyhledávacího algoritmu jednotných nákladů lze nahlížet jako na speciální případ A * where ${ displaystyle h (x) = 0}$ pro všechny X.^[11][12] Všeobecné hloubkové vyhledávání lze implementovat pomocí A * zvážením, že existuje globální počítadlo C inicializováno s velmi velkou hodnotou. Pokaždé, když zpracováváme uzel, který přiřadíme C všem svým nově objeveným sousedům. Po každém jednotlivém přiřazení snižujeme počítadlo C jedním. Čím dříve je uzel objeven, tím vyšší je ${ displaystyle h (x)}$ hodnota. Algoritmus Dijkstra i vyhledávání do hloubky lze efektivněji implementovat bez použití ${ displaystyle h (x)}$ hodnota v každém uzlu.

Vlastnosti

Ukončení a úplnost

U konečných grafů se zápornými hranovými vahami je zaručeno, že A * bude a je kompletní, tj. vždy najde řešení (cestu od začátku do cíle), pokud existuje. Na nekonečných grafech s konečným větvícím faktorem a hraničními náklady, které jsou ohraničeny od nuly (${ textstyle d (x, y)> varepsilon> 0}$ pro některé pevné ${ displaystyle varepsilon}$), A * je zaručeno, že bude ukončeno, pouze pokud existuje řešení.

Přípustnost

Vyhledávací algoritmus se říká, že je přípustný pokud je zaručeno, že vrátí optimální řešení. Pokud je heuristická funkce používaná A * přípustný, pak je přípustné A *. Intuitivní „důkaz“ toho je následující:

Když A * ukončí vyhledávání, našel cestu od začátku do cíle, jejíž skutečné náklady jsou nižší než odhadované náklady na jakoukoli cestu od začátku do cíle přes libovolný otevřený uzel (uzel ${ displaystyle f}$ hodnota). Je-li heuristika přípustná, jsou tyto odhady optimistické (ne tak docela - viz další odstavec), takže A * může tyto uzly bezpečně ignorovat, protože nemohou vést k levnějšímu řešení, než jaké již má. Jinými slovy, A * nikdy nepřehlédne možnost levnější cesty od začátku do cíle, a tak bude pokračovat v hledání, dokud takové možnosti neexistují.

Skutečný důkaz je trochu více zapojen, protože ${ displaystyle f}$ není zaručeno, že hodnoty otevřených uzlů budou optimistické, i když je heuristika přípustná. Je to proto, že ${ displaystyle g}$ hodnoty otevřených uzlů nejsou zaručeně optimální, takže součet ${ displaystyle g + h}$ není zaručeno, že bude optimistický.

Optimální účinnost

Algoritmus A je optimálně efektivní s ohledem na sadu alternativních algoritmů Alts na soubor problémů P pokud pro každý problém P in P a každý algoritmus A 'v Alts, množina uzlů rozšířených o A při řešení P je podmnožinou (možná rovnou) množiny uzlů rozšířených o A ′ při řešení P. Definitivní studium optimální účinnosti A * je způsobeno Rinou Dechterovou a Judea Pearl.^[10]Uvažovali o různých definicích Alts a P v kombinaci s heuristikou A * je pouze přípustná nebo konzistentní a přípustná. Nejzajímavějším pozitivním výsledkem, který dokázali, je, že A *, s konzistentní heuristikou, je optimálně efektivní ve vztahu ke všem přípustným vyhledávacím algoritmům podobným A * u všech „nepatologických“ vyhledávacích problémů. Zhruba řečeno, jejich představa o nepatologickém problému je to, co nyní myslíme pod pojmem „až po zlomení“. Tento výsledek neplatí, pokud je heuristika A * přípustná, ale není konzistentní. V takovém případě Dechter a Pearl ukázali, že existují přípustné algoritmy podobné A *, které mohou u některých nepatologických problémů rozšířit libovolně méně uzlů než A *.

Optimální účinnost je o soubor rozšířených uzlů, nikoli číslo rozšíření uzlů (počet iterací hlavní smyčky A *). Pokud je použitá heuristika přípustná, ale není konzistentní, je možné, aby byl uzel mnohokrát rozšířen o A *, v nejhorším případě exponenciální počet.^[13]Za takových okolností by Dijkstrův algoritmus mohl překonat A * s velkým náskokem.

Omezená relaxace

Hledání *, které používá heuristiku, která je 5,0 (= ε) krát a důsledná heuristika a získá neoptimální cestu.

I když kritérium přípustnosti zaručuje optimální cestu řešení, znamená to také, že A * musí prozkoumat všechny stejně záslužné cesty, aby našla optimální cestu. Chcete-li vypočítat přibližné nejkratší cesty, je možné urychlit hledání na úkor optimality uvolněním kritéria přípustnosti. Často chceme tuto relaxaci svázat, abychom mohli zaručit, že cesta řešení nebude horší než (1 + ε) krát optimální cesta řešení. Tato nová záruka se označuje jako ε-přípustný.

Existuje celá řada ε-přípustné algoritmy:

• Vážené A * / statické vážení.^[14] Li h_A(n) je přípustná heuristická funkce ve vážené verzi vyhledávání A *, kterou člověk používá h_w(n) = ε h_A(n), ε > 1 jako heuristická funkce a proveďte vyhledávání A * jako obvykle (což se nakonec stane rychleji než při použití h_A protože je rozbaleno méně uzlů). Cesta tedy nalezená vyhledávacím algoritmem může mít cenu maximálně ε násobek cesty s nejnižšími náklady v grafu.^[15]

• Dynamické vážení^[16] používá nákladovou funkci ${ Displaystyle f (n) = g (n) + (1+ varepsilon w (n)) h (n)}$, kde ${ displaystyle w (n) = { begin {případech} 1 - { frac {d (n)} {N}} & d (n) leq N 0 & { text {jinak}} end {případů }}}$, a kde ${ displaystyle d (n)}$ je hloubka hledání a N je očekávaná délka cesty řešení.

• Vzorkované dynamické vážení^[17] používá vzorkování uzlů k lepšímu odhadu a debiaření heuristické chyby.

• ${ displaystyle A _ { varepsilon} ^ {*}}$.^[18] používá dvě heuristické funkce. Prvním je FOKÁLNÍ seznam, který se používá k výběru kandidátských uzlů, a druhým h_F slouží k výběru nejslibnějšího uzlu ze seznamu FOCAL.

• A_ε^[19] vybírá uzly s funkcí ${ displaystyle Af (n) + Bh_ {F} (n)}$, kde A a B jsou konstanty. Pokud nelze vybrat žádné uzly, algoritmus se vrátí zpět s funkcí ${ displaystyle Cf (n) + Dh_ {F} (n)}$, kde C a D jsou konstanty.

• AlphA *^[20] pokusí se propagovat využití do hloubky upřednostňováním nedávno rozšířených uzlů. AlphA * používá funkci nákladů ${ displaystyle f _ { alpha} (n) = (1 + w _ { alpha} (n)) f (n)}$, kde ${ displaystyle w _ { alpha} (n) = { begin {cases} lambda & g ( pi (n)) leq g ({ tilde {n}}) Lambda & { text {jinak }} end {cases}}}$, kde λ a Λ jsou konstanty s ${ displaystyle lambda leq Lambda}$, π(n) je rodičem n, a - je naposledy rozšířený uzel.

Složitost

The časová složitost A * závisí na heuristice. V nejhorším případě neomezeného prostoru pro vyhledávání je počet rozšířených uzlů exponenciální v hloubce řešení (nejkratší cesta) d: Ó(b^d), kde b je větvící faktor (průměrný počet nástupců za stát).^[21] To předpokládá, že stav cíle vůbec existuje a je dosažitelný od počátečního stavu; pokud tomu tak není a stavový prostor je nekonečný, algoritmus nebude ukončen.

Heuristická funkce má zásadní vliv na praktický výkon vyhledávání A *, protože dobrá heuristika umožňuje A * odříznout mnoho b^d uzly, které by neinformované vyhledávání rozšířilo. Jeho kvalitu lze vyjádřit pomocí efektivní větvící faktor b*, které lze určit empiricky pro problémovou instanci měřením počtu uzlů generovaných expanzí, N, a hloubku řešení, pak řešení^[22]

${ displaystyle N + 1 = 1 + b ^ {*} + (b ^ {*}) ^ {2} + tečky + (b ^ {*}) ^ {d}.}$

Dobré heuristiky jsou ty s nízkým účinným větvícím faktorem (optimální bytost b* = 1).

Časová složitost je polynomiální když je vyhledávacím prostorem strom, existuje jediný stav cíle a heuristická funkce h splňuje následující podmínku:

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

kde h^* je optimální heuristika, přesné náklady, z nichž lze získat X do cíle. Jinými slovy, chyba h nebude růst rychleji než logaritmus „dokonalé heuristiky“ h^* která vrací skutečnou vzdálenost od X do cíle.^[15][21]

The složitost prostoru A * je zhruba stejný jako u všech ostatních algoritmů pro vyhledávání grafů, protože udržuje všechny generované uzly v paměti.^[23] V praxi se to ukazuje jako největší nevýhoda vyhledávání A *, což vede k vývoji heuristických vyhledávání vázaných na paměť, jako například Iterativní prohlubování A *, paměť ohraničená A * a SMA *.

Aplikace

A * se často používá pro běžné hledání cesty problém v aplikacích, jako jsou videohry, ale původně byl navržen jako obecný algoritmus pro procházení grafů.^[4]Najde uplatnění v různých problémech, včetně problému analýza použitím stochastické gramatiky v NLP.^[24]Mezi další případy patří Informační vyhledávání s online výukou.^[25]

Vztahy k jiným algoritmům

Co odlišuje A * od a chamtivý nejlepší vyhledávací algoritmus spočívá v tom, že bere již ujetou cenu / vzdálenost, G(n), v úvahu.

Některé běžné varianty Dijkstrův algoritmus lze považovat za speciální případ A *, kde je heuristika ${ displaystyle h (n) = 0}$ pro všechny uzly;^[11][12] zase Dijkstra a A * jsou speciální případy dynamické programování.^[26]Samotné * je zvláštní případ zobecnění větev a svázaný.^[27]

Varianty

• Kdykoli *^[28] nebo kdykoli opravit A * (ARA *)^[29]
• Kdykoli Dynamic A *
• Blok A *
• D *
• Pole D *
• Třásně
• Fringe Saving A * (FSA *)
• Zobecněný adaptivní A * (GAA *)
• Inkrementální heuristické vyhledávání
• Informační vyhledávání^[25]
• Iterativní prohlubování A * (IDA *)
• Hledání skokových bodů
• Celoživotní plánování A * (LPA *)
• Multiplikátor zrychlený A * (MAA *) ^[30]
• Nový obousměrný A * (NBA *)^[31]
• Zjednodušená paměť ohraničená A * (SMA *)
• Realtime A *^[32]
• Theta *
• Časově ohraničený A * (TBA *)^[33]

A * lze také upravit na a obousměrné vyhledávání algoritmus. Zvláštní kritérium je třeba věnovat kritériu zastavení.^[34]

Viz také

• Šířka první vyhledávání
• Hledání do hloubky
• Plánování cesty v libovolném úhlu, hledat cesty, které se neomezují pouze na pohyb po okrajích grafu, ale mohou nabrat jakýkoli úhel

Poznámky

Reference

Další čtení

• Nilsson, N.J. (1980). Principy umělé inteligence. Palo Alto, Kalifornie: Tioga Publishing Company. ISBN  978-0-935382-01-3.

externí odkazy

• Jasné vizuální A * vysvětlení s radami a myšlenkami na hledání cesty
• Variace na A * volána Hierarchické hledání cesty A * (HPA *)