Fringe vyhledávání - Fringe search
Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace.červen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Graf a strom vyhledávací algoritmy |
---|
Výpisy |
|
související témata |
v počítačová věda, okrajové vyhledávání je algoritmus pro vyhledávání grafů který najde cestu s nejnižšími náklady z dané iniciály uzel do jednoho uzel cíle.
V podstatě je okrajové hledání prostředníkem mezi nimi A* a iterativní prohlubování A * varianta (IDA *).
Li G(X) je cena vyhledávací cesty z prvního uzlu do aktuálního a h(X) je heuristický pak odhad nákladů ze současného uzlu do cíle ƒ(X) = G(X) + h(X), a h* je skutečná cena cesty k cíli. Zvažte IDA *, který dělá rekurzivní zleva do prava hloubkové vyhledávání z kořenového uzlu zastavení rekurze, jakmile byl nalezen cíl nebo uzly dosáhly maximální hodnoty ƒ. Pokud v první hranici není nalezen žádný cíl ƒ, poté se zvýší prahová hodnota a algoritmus znovu vyhledá. TJ. Iteruje na prahové hodnotě.
U IDA * existují tři hlavní neúčinnosti. Nejprve IDA * bude opakovat stavy, když k cílovému uzlu existuje více (někdy neoptimálních) cest - to se často řeší udržováním mezipaměti navštívených stavů. Takto pozměněný IDA * je označen jako IDA * s rozšířenou pamětí (ME-IDA *), protože využívá určité úložiště. Kromě toho IDA * opakuje všechny předchozí operace ve vyhledávání, když iteruje s novou prahovou hodnotou, která je nezbytná pro provoz bez úložiště. Uložením listových uzlů předchozí iterace a jejich použitím jako výchozí pozice další se efektivita IDA * výrazně zlepší (jinak by v poslední iteraci musel vždy navštívit každý uzel ve stromu).
Fringe search implementuje tato vylepšení na IDA * využitím datové struktury, která je víceméně dvě seznamy iterovat přes hranici nebo okraj vyhledávacího stromu. Jeden seznam Nyní, uloží aktuální iteraci a další seznam později ukládá okamžitou další iteraci. Takže z kořenového uzlu vyhledávacího stromu, Nyní bude kořen a později bude prázdný. Potom algoritmus provede jednu ze dvou akcí: If ƒ(hlava) je větší než aktuální prahová hodnota, odeberte hlava z Nyní a připojit jej do konce roku později; tj. uložit hlava pro další iteraci. Jinak, pokud ƒ(hlava) je menší nebo roven prahové hodnotě, rozbalte hlava a odhodit hlava, zvažte jeho děti a přidejte je na začátek Nyní. Na konci iterace se prahová hodnota zvýší, později ze seznamu se stane Nyní seznam a později je vyprázdněn.
Důležitým rozdílem mezi okrajem a A * je, že obsah seznamů v okraji nemusí být nutně tříděn - což je výrazný zisk oproti A *, což vyžaduje často nákladnou údržbu pořadí v jeho otevřeném seznamu. Na rozdíl od A * však bude muset třásně opakovaně navštěvovat stejné uzly, ale náklady na každou takovou návštěvu jsou ve srovnání s nejhorším logaritmickým časem třídění seznamu v A * konstantní.
Pseudo kód
Implementace obou seznamů v jednom dvojnásobně propojeném seznamu, kde jsou uzly, které předcházejí aktuálnímu uzlu později část a všechny ostatní jsou Nyní seznam. Pomocí pole předem přidělených uzlů v seznamu pro každý uzel v mřížce se přístupová doba k uzlům v seznamu sníží na konstantu. Podobně pole značek umožňuje vyhledávání uzlu v seznamu v konstantním čase. G je uložen jako hash tabulka a poslední pole značek je uloženo pro neustálé vyhledávání toho, zda byl uzel dříve navštíven či nikoli, a zda je položka mezipaměti platná.
inic(Start, fotbalová branka) třásně F = s mezipaměti C[Start] = (0, nula) flimit = h(Start) nalezeno = Nepravdivé zatímco (nalezeno == Nepravdivé) A (F ne prázdný) fmin = ∞ pro uzel v F, z vlevo, odjet na že jo (G, rodič) = C[uzel] F = G + h(uzel) -li F > flimit fmin = min(F, fmin) pokračovat -li uzel == fotbalová branka nalezeno = skutečný přestávka pro dítě v děti(uzel), z že jo na vlevo, odjet g_child = G + náklady(uzel, dítě) -li C[dítě] != nula (g_cached, rodič) = C[dítě] -li g_child >= g_cached pokračovat -li dítě v F odstranit dítě z F vložit dítě v F minulost uzel C[dítě] = (g_child, uzel) odstranit uzel z F flimit = fmin -li dosáhl cíle == skutečný reverzní_cesta(fotbalová branka)
Reverzní pseudokód.
reverzní_cesta(uzel) (G, rodič) = C[uzel] -li rodič != nula reverzní_cesta(rodič) tisk uzel
Experimenty
Při testování v prostředí založeném na mřížce typickém pro počítačové hry, včetně neprůchodných překážek, třásně překonaly A * přibližně o 10 až 40 procent, v závislosti na použití dlaždic nebo oktilů. Další možná vylepšení zahrnují použití datové struktury, která se snáze zapůjčí do mezipaměti.
Reference
- Björnsson, Yngvi; Enzenberger, Markus; Holte, Robert C .; Schaeffer, Johnathan. Fringe Search: Bití A * při Pathfindingu na herních mapách. Sborník konference IEEE Symposium 2005 on Computational Intelligence and Games (CIG05). Essex University, Colchester, Essex, Velká Británie, 4. – 6. Dubna 2005. IEEE 2005. https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf
externí odkazy
- Jesús Manuel Mager Hois implementace Fringe Search v C https://github.com/pywirrarika/fringesearch