A*

Hledat A * (vyslovuje se „A star“ nebo „A star“, z angličtiny  A star ) – v informatice a matematice algoritmus vyhledávání pro první nejlepší shodu v grafu , který najde cestu s nejnižší cenou z jednoho vrcholu ( počáteční) na jiný (cíl, konečný).

Pořadí, ve kterém se vrcholy procházejí, je určeno heuristickou funkcí vzdálenost + náklady (běžně označované jako f(x) ). Tato funkce je součtem dvou dalších: nákladové funkce dosažení uvažovaného vrcholu ( x ) z počátečního (obvykle se označuje jako g(x) a může být buď heuristická, nebo ne) a funkce heuristického odhadu vzdálenosti. z uvažovaného vrcholu do konečného (označeného jako h (x) ).

Funkce h(x) musí být platným heuristickým odhadem , to znamená, že nesmí nadhodnocovat vzdálenosti k cílovému vrcholu. Například pro problém se směrováním by h(x) mohla být vzdálenost k cíli v přímce, protože je to fyzicky nejmenší možná vzdálenost mezi dvěma body.

Tento algoritmus poprvé popsali v roce 1968 Peter Hart , Nils Nilsson a Bertram Raphael . Bylo to v podstatě rozšíření Dijkstrova algoritmu vytvořeného v roce 1959. Nový algoritmus dosáhl vyššího výkonu (v čase) pomocí heuristiky. V jejich práci je označován jako „Algoritmus A“. Ale protože vypočítává nejlepší trasu pro danou heuristiku, dostal název A*.

Zobecněním je obousměrný heuristický vyhledávací algoritmus .

Historie

V roce 1964 Nils Nilsson vynalezl heuristický přístup k urychlení Dijkstrova algoritmu . Tento algoritmus byl nazván A1 . V roce 1967 provedl Bertram Raphael významná vylepšení tohoto algoritmu, ale nepodařilo se mu dosáhnout optimality. Nazval tento algoritmus A2 . V roce 1968 pak Peter E. Hart předložil argumenty, které tvrdily, že A2 je optimální při použití sekvenční heuristiky pouze s malými úpravami. Jeho důkaz o algoritmu také obsahoval část, která ukázala, že nový algoritmus A2 je možná nejlepší algoritmus za daných podmínek. Označil tedy nový algoritmus v syntaxi hvězdičkou, začíná na A a obsahuje všechna možná čísla verzí.

Popis algoritmu

A* iteruje všechny cesty vedoucí od počátečního vrcholu ke koncovému vrcholu, dokud nenajde tu nejmenší. Stejně jako všechny informované vyhledávací algoritmy se nejprve podívá na trasy, které „zdá se“, že vedou k cíli. Od greedy algorithm , což je také vyhledávací algoritmus pro první nejlepší shodu, se liší tím, že při výběru vrcholu bere v úvahu mimo jiné celou cestu k němu ujetou. Komponenta g(x)  je cena cesty z počátečního vrcholu, a ne z předchozího, jak je tomu v chamtivém algoritmu.

Na začátku práce se prohlédnou uzly sousedící s počátečním; je vybrán ten, který má minimální hodnotu f(x) , a poté je tento uzel rozšířen. V každé fázi algoritmus pracuje na sadě cest od výchozího bodu ke všem dosud neprozkoumaným (listovým) vrcholům grafu - sada konkrétních řešení - která je umístěna do prioritní fronty . Priorita cesty je určena hodnotou f(x) = g(x) + h(x) . Algoritmus pokračuje ve své práci, dokud hodnota f(x) cílového vrcholu není menší než jakákoli hodnota ve frontě, nebo dokud není naskenován celý strom. Z množiny řešení je vybráno řešení s nejnižší cenou.

Čím menší je heuristika h(x) , tím vyšší priorita, takže třídicí stromy lze použít k implementaci fronty .

Sada zobrazených vrcholů je uložena v closeda cesty, které je třeba vzít v úvahu, jsou ve frontě priority open. Priorita cesty se vypočítá pomocí funkce f(x) uvnitř implementace prioritní fronty.

Pseudo kód:

funkce A* ( start, cíl, f ) % množiny vrcholů již prošlo var closed : = prázdná množina % sady jednotlivých řešení var open := make_queue ( f ) zařadit do fronty ( otevřít , cesta ( start )) zatímco otevřeno není prázdné _ var p := remove_first ( otevřít ) var x : = poslední uzel p _ pokud x uzavřeno _ pokračovat pokud x = cíl vrátit se p přidat ( zavřeno , x ) % přidat sousední vrcholy foreach y v následnících ( x ) zařadit do fronty ( open , add_to_path ( p , y )) selhání návratu

Množinu již prodaných vrcholů lze vynechat (v tomto případě se algoritmus změní na prohledávání rozhodovacího stromu), pokud je známo, že řešení existuje, nebo pokud successorsdokáže přerušit cykly .

Příklad

Příklad algoritmu A* v akci, kde uzly jsou města spojená silnicemi a H(x) je nejkratší vzdálenost k cílovému bodu:

Klíč: zelená - start, modrá - cíl, oranžová - navštívené uzly.

Vlastnosti

Stejně jako Breadth First Search je A* kompletní v tom smyslu, že vždy najde řešení, pokud nějaké existuje.

Pokud je heuristická funkce h přípustná, to znamená, že nikdy nepřeceňuje skutečné minimální náklady na dosažení cíle, pak A* je sama o sobě přípustná (nebo optimální ), také za předpokladu, že neodřízneme procházené vrcholy. Pokud to uděláme, pak pro optimalitu algoritmu je nutné, aby h(x) byla také monotónní nebo postupná heuristika. Vlastnost monotonie znamená, že pokud existují cesty A-B-C a A-C (ne nutně přes B ), pak odhad nákladů na cestu z A do C musí být menší nebo roven součtu odhadů cest A-B a B-C . (Monotonie je také známá jako trojúhelníková nerovnost : jedna strana trojúhelníku nemůže být delší než součet ostatních dvou stran.) Matematicky pro všechny cesty x , y (kde y  je potomkem x ) je:

A* je také optimálně efektivní pro danou heuristiku h . To znamená, že jakýkoli jiný algoritmus prozkoumá alespoň tolik uzlů jako A* (pokud neexistuje několik konkrétních řešení se stejnou heuristikou přesně odpovídající ceně optimální cesty).

Zatímco A* je optimální pro „náhodně“ dané grafy, není zaručeno, že odvede lepší práci než jednodušší, ale více doménově orientované algoritmy. Například v určitém labyrintu budete možná muset nejprve jít směrem od východu a teprve potom se vrátit zpět. V tomto případě bude průzkum na začátku těch vrcholů, které jsou blíže k východu (v přímé linii), ztrátou času.

Zvláštní příležitosti

Obecně řečeno, hloubka - první prohledávání a prohledávání do šířky jsou dva speciální případy algoritmu A*. Pro hledání do hloubky si vezměme globální počítadlo proměnných C , které inicializujeme nějakou velkou hodnotou. Pokaždé, když rozšíříme vrchol, přiřadíme hodnotu čítače sousedním vrcholům a po každém přiřazení ji snížíme o jednu. Čím dříve je tedy vrchol otevřen, tím větší hodnotu h(x) obdrží, což znamená, že bude zobrazen jako poslední. Pokud dáme h(x) = 0 pro všechny vrcholy, dostaneme další speciální případ – Dijkstrův algoritmus .

Podrobnosti implementace

Existuje několik implementačních funkcí a technik, které mohou významně ovlivnit účinnost algoritmu. První věc, které neuškodí věnovat pozornost, je to, jak prioritní fronta zpracovává spojení mezi vrcholy. Pokud se k němu přidají vrcholy tak, že fronta funguje na principu LIFO , pak v případě vrcholů se stejným hodnocením A* „půjde“ do hloubky. Pokud je však při přidávání vrcholů implementován princip FIFO , pak pro vrcholy se stejným odhadem algoritmus naopak implementuje prohledávání do šířky. V některých případech může mít tato okolnost významný dopad na výkon .

Pokud je na konci práce z algoritmu vyžadována trasa, je obvykle spolu s každým vrcholem uložena vazba na nadřazený uzel. Tyto odkazy umožňují rekonstruovat optimální trasu. Pokud ano, pak je důležité, aby se stejný vrchol neobjevil ve frontě dvakrát (a přitom měl vlastní trasu a vlastní odhad nákladů). Obvykle, aby tento problém vyřešili, při přidávání vrcholu zkontrolují, zda o něm není ve frontě záznam. Pokud ano, pak se záznam aktualizuje tak, aby odpovídal minimální ceně obou. K nalezení vrcholu v třídicím stromě mnoho standardních algoritmů trvá O(n) čas. Pokud vylepšíte strom pomocí hashovací tabulky , můžete tento čas zkrátit.

Proč je A* platné a optimální

Algoritmus A* je přípustný a zároveň prochází minimálním počtem vrcholů, protože pracuje s "optimistickým" odhadem cesty vrcholem. Optimistický v tom smyslu, že pokud projde tímto vrcholem, algoritmus „má šanci“, že skutečná cena výsledku bude rovna tomuto odhadu, ale ne menší. Ale protože A* je informovaný algoritmus, může být taková rovnost možná.

Když A* dokončí vyhledávání, podle definice našel cestu, jejíž skutečné náklady jsou nižší než odhadované náklady jakékoli cesty přes jakýkoli otevřený uzel. Ale protože jsou tyto odhady optimistické, mohou být odpovídající uzly bezpochyby vyřazeny. Jinými slovy, A* nikdy nevynechá příležitost minimalizovat délku cesty, a je proto legální.

Předpokládejme nyní, že nějaký algoritmus B vrátil jako výsledek cestu, jejíž délka je větší než odhad nákladů na cestu přes nějaký vrchol. Na základě heuristických informací pro Algoritmus B nelze vyloučit možnost, že tato cesta měla kratší reálnou délku než výsledek. V souladu s tím, zatímco algoritmus B sledoval méně vrcholů než A*, nebude platný. A* tedy prochází nejmenším počtem vrcholů grafu mezi platnými algoritmy pomocí stejné přesné (nebo méně přesné) heuristiky.

Hodnocení obtížnosti

Časová složitost A* algoritmu závisí na heuristice. V nejhorším případě počet vrcholů prozkoumaných algoritmem roste exponenciálně ve srovnání s délkou optimální cesty, ale složitost se stane polynomiální , když heuristika splní následující podmínku:

;

kde h* je optimální heuristika, tj. přesný odhad vzdálenosti od x k cíli. Jinými slovy, chyba h(x) by neměla růst rychleji než logaritmus optimální heuristiky.

Ale ještě větším problémem než časová složitost jsou paměťové zdroje spotřebované algoritmem . V nejhorším případě si musí pamatovat exponenciální počet uzlů. Aby se tomu zabránilo, bylo navrženo několik variant algoritmu, jako je algoritmus A* s iterativním prohlubováním (iterativní prohlubování A*, IDA*), A* s paměťově ohraničeným A*, MA*, zjednodušený MA* (zjednodušený MA *, SMA*) a rekurzivní vyhledávání na prvním místě (RBFS).

Literatura

  • Laurier J.-L. Systémy umělé inteligence / Per. od fr. a ed. V. L. Stefanyuk. - M .: Mir, 1991. - S. 238-244. — 20 000 výtisků. kopírovat.  — ISBN 5-03-001408-X .
  • Russell S.J., Norvig, P. Umělá inteligence: Moderní přístup = Artificial Intelligence: A Modern Approach / Per. z angličtiny. a ed. K. A. Ptitsyna. - 2. vyd. - M .: Williams, 2006. - S. 157-162. - 3000 výtisků. kopírovat.  — ISBN 5-8459-0887-6 .
  • Nilson N. Umělá inteligence: Metody pro hledání řešení = Metody řešení problémů v umělé inteligenci / Per. z angličtiny. V. L. Stefanyuk; vyd. S. V. Fomina. - M .: Mir, 1973. - S. 70 - 80.
  • Dechter, R., Pearl, J. Generalized best-first search strategy and the optimality of A*  // Journal of the ACM. - 1985. - T. 32 , č. 3 . - S. 505 - 536 .
  • Hart PE, Nilsson, NJ, Raphael, B. Formální základ pro heuristické stanovení cest minimálních nákladů // Transakce IEEE v oblasti systémové vědy a kybernetiky SSC4. - 1968. - č. 2 . - S. 100 - 107 .
  • Hart PE, Nilsson, NJ, Raphael, B. Oprava „Formální základ pro heuristické stanovení cest minimálních nákladů“ // Newsletter SIGART. - 1972. - T. 37 . - S. 28 - 29 .
  • Pearl J. Heuristika: Inteligentní vyhledávací strategie pro řešení počítačových problémů. - Addison-Wesley, 1984. - ISBN 0-201-05594-5 .

Odkazy

 Algoritmy vyhledávání grafů
Neinformované metody
Informované metody
Zkratky
Minimální kostra
jiný