Obousměrné vyhledávání - Bidirectional search

Obousměrné vyhledávání je algoritmus pro vyhledávání grafů který najde a nejkratší cesta z iniciály vrchol k cílovému vrcholu v a řízený graf. Spustí dvě simultánní vyhledávání: jedno vpřed z počátečního stavu a jedno vzad od cíle a zastaví se, když se dva setkají. Důvodem tohoto přístupu je, že v mnoha případech je rychlejší: například ve zjednodušeném modelu složitosti vyhledávacího problému, ve kterém obě vyhledávání rozšiřují strom s větvící faktor ba vzdálenost od začátku do cíle je d, každé ze dvou vyhledávání má složitost Ó(b^d/2) (v Velká O notace ) a součet těchto dvou vyhledávacích časů je mnohem menší než Ó(b^d) složitost, která by vyplynula z jediného hledání od začátku do cíle.

Andrew Goldberg a další vysvětlili správné podmínky ukončení pro obousměrnou verzi Dijkstrův algoritmus.^[1]

Jako v A* vyhledávání, obousměrné vyhledávání může být vedeno a heuristický odhad zbývající vzdálenosti k cíli (ve stromu vpřed) nebo od začátku (ve stromu vzad).

Ira Pohl (1971 ) byl první, kdo navrhl a implementoval obousměrný heuristický vyhledávací algoritmus. Uprostřed prostoru řešení se nepodařilo setkat vyhledávací stromy vycházející z počátečních a cílových uzlů. Algoritmus BHFFA opravil tuto vadu Champeaux (1977).

Řešení nalezené jednosměrným algoritmem A * používajícím přípustnou heuristiku má nejkratší délku cesty; stejná vlastnost platí pro obousměrnou heuristickou verzi BHFFA2 popsanou v de Champeaux (1983). BHFFA2 má mimo jiné pečlivější podmínky ukončení než BHFFA.

Popis

Obousměrné heuristické vyhledávání je hledání stavového prostoru z nějakého státu ${ displaystyle s}$ do jiného státu ${ displaystyle t}$, vyhledávání z ${ displaystyle s}$ na ${ displaystyle t}$ a od ${ displaystyle t}$ na ${ displaystyle s}$ zároveň. Vrátí platný seznam operátorů, které, pokud se použijí ${ displaystyle s}$ dá nám ${ displaystyle t}$.

I když se může zdát, že operátoři musí být pro reverzní vyhledávání invertibilní, je pouze nutné, aby bylo možné najít daný uzel ${ displaystyle n}$, sada nadřazených uzlů ${ displaystyle n}$ takže existuje nějaký platný operátor z každého z nadřazených uzlů do ${ displaystyle n}$. Toto bylo často přirovnáváno k jednosměrné ulici v doméně hledání trasy: není nutné být schopen cestovat oběma směry, ale je nutné, když stojíte na konci ulice, abyste určili začátek ulice jako možná trasa.

Podobně pro ty hrany, které mají inverzní oblouky (tj. Oblouky probíhající v obou směrech), není nutné, aby každý směr měl stejnou cenu. Zpětné vyhledávání vždy použije inverzní cenu (tj. Cenu oblouku ve směru dopředu). Více formálně, pokud ${ displaystyle n}$ je uzel s rodičem ${ displaystyle p}$, pak ${ displaystyle k_ {1} (p, n) = k_ {2} (n, p)}$, definované jako náklady od ${ displaystyle p}$ na ${ displaystyle n}$(Auer Kaindl 2004)

Terminologie a notace

${ displaystyle b}$

the větvící faktor vyhledávacího stromu

${ displaystyle k (n, m)}$

náklady spojené s přesunem z uzlu ${ displaystyle n}$ do uzlu ${ displaystyle m}$

${ displaystyle g (n)}$

náklady od kořene po uzel ${ displaystyle n}$

${ displaystyle h (n)}$

heuristický odhad vzdálenosti mezi uzlem ${ displaystyle n}$ a cíl

${ displaystyle s}$

počáteční stav

${ displaystyle t}$

stav cíle (někdy ${ displaystyle g}$, nezaměňovat s funkcí)

${ displaystyle d}$

aktuální směr hledání. Podle konvence ${ displaystyle d}$ se rovná 1 pro směr vpřed a 2 pro směr vzad (Kwa 1989)

${ displaystyle d '}$

opačný směr vyhledávání (tj. ${ displaystyle d '= 3-d}$)

${ displaystyle mathrm {STROM} _ {d}}$

vyhledávací strom ve směru d. Li ${ displaystyle d = 1}$, kořen je ${ displaystyle s}$, pokud ${ displaystyle d = 2}$, kořen je ${ displaystyle t}$

${ displaystyle mathrm {OPEN} _ {d}}$

listy ${ displaystyle mathrm {STROM} _ {d}}$ (někdy označované jako ${ displaystyle mathrm {FRINGE} _ {d}}$). Z této sady je vybrán uzel pro expanzi. V obousměrném vyhledávání se jim někdy říká „hranice“ nebo „vlnová fronta“, což znamená, jak vypadají, když je vyhledávání graficky znázorněno. V této metaforě dochází ke „kolizi“, když se během fáze expanze zjistí, že uzel z jednoho vlnoplochy má nástupce v opačném vlnoploše.

${ displaystyle mathrm {ZAVŘENO} _ {d}}$

nelistové uzly ${ displaystyle mathrm {STROM} _ {d}}$. Tato sada obsahuje uzly, které již vyhledávání navštívilo

Přístupy k obousměrnému heuristickému vyhledávání

Obousměrné algoritmy lze obecně rozdělit do tří kategorií: Front-to-Front, Front-to-Back (nebo Front-to-End) a Perimeter Search (Kaindl Kainz 1997). Liší se funkcí použitou k výpočtu heuristiky.

Zepředu dozadu

Algoritmy zepředu dozadu vypočítají ${ displaystyle h}$ hodnota uzlu ${ displaystyle n}$ pomocí heuristického odhadu mezi ${ displaystyle n}$ a kořen opačného vyhledávacího stromu, ${ displaystyle s}$ nebo ${ displaystyle t}$.

Front-to-Back je nejaktivněji zkoumaný ze tří kategorií. Aktuální nejlepší algoritmus (alespoň v Patnáct puzzle doména) je algoritmus BiMAX-BS * F, vytvořený Auerem a Kaindlem (Auer, Kaindl 2004).

Zepředu dozadu

Algoritmy front-to-front počítají h hodnota uzlu n pomocí heuristického odhadu mezi n a některé podmnožiny ${ displaystyle mathrm {OPEN} _ {d '}}$. Kanonickým příkladem je příklad BHFFA (Obousměrný heuristický front-to-front algoritmus ),^[2] Kde h funkce je definována jako minimum všech heuristických odhadů mezi aktuálním uzlem a uzly na protilehlé frontě. Nebo formálně:

${ displaystyle h_ {d} (n) = min _ {i} vlevo {H (n, o_ {i}) | o_ {i} v mathrm {OPEN} _ {d '} vpravo }}$

kde ${ displaystyle H (n, o)}$ vrací přípustný (tj. nepřeceňovaný) heuristický odhad vzdálenosti mezi uzly n a Ó.

Front-to-Front trpí příliš výpočetní náročností. Pokaždé uzel n je vložen do otevřeného seznamu ${ displaystyle f = g + h}$ hodnota musí být vypočítána. To zahrnuje výpočet heuristického odhadu z n ke každému uzlu protivníka OTEVŘENO set, jak je popsáno výše. The OTEVŘENO nastaví zvětšení velikosti exponenciálně pro všechny domény s b > 1.

Reference

• de Champeaux, Dennis; Sint, Lenie (1977), „Vylepšený obousměrný heuristický vyhledávací algoritmus“, Deník ACM, 24 (2): 177–191, doi:10.1145/322003.322004.
• de Champeaux, Dennis (1983), „Znovu obousměrné heuristické vyhledávání“, Deník ACM, 30 (1): 22–32, doi:10.1145/322358.322360.
• Pohl, Ira (1971), "Obousměrné vyhledávání", Meltzer, Bernard; Michie, Donald (eds.), Inteligence strojů, 6, Edinburgh University Press, s. 127–140.
• Russell, Stuart J.; Norvig, Peter (2002), „3.4 Neinformované vyhledávací strategie“, Umělá inteligence: moderní přístup (2. vyd.), Prentice Hall.