Fringe vyhledávání - Fringe search
Algoritmy pro vyhledávání grafů a stromů |
---|
Výpisy |
související témata |
Ve vědě o počítačích , třásně vyhledávání je vyhledávací algoritmus graf , který najde cestu nejméně-cost z daného počátečního uzlu na jeden gól uzlu .
V podstatě je okrajové vyhledávání prostředníkem mezi A * a iterativní prohlubující se A * variantou (IDA *).
Pokud g ( x ) je cena cesty hledání od prvního uzlu k proudu a h ( x ) je heuristický odhad nákladů od aktuálního uzlu k cíli, pak ƒ ( x ) = g ( x ) + h ( x ) a h * je skutečná cena cesty k cíli. Zvažte IDA *, které provádí rekurzivní prohledávání zleva doprava od kořenového uzlu a zastaví rekurzi, jakmile byl nalezen cíl nebo uzly dosáhly maximální hodnoty ƒ . Pokud není cílem nalézt v první prahová ƒ , mezní hodnota se dále zvyšuje a opět algoritmus vyhledávání. IE 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ěma seznamy k iteraci přes hranice nebo okraje vyhledávacího stromu. Jeden seznam nyní ukládá aktuální iteraci a druhý seznam později ukládá okamžitou další iteraci. Takže z kořenového uzlu vyhledávacího stromu, nyní budou kořen a později bude prázdná. Potom algoritmus provede jednu ze dvou akcí: Pokud je ƒ (head) větší než aktuální prahová hodnota, odeberte head od nynějška a připojte jej na konec později ; tj. uložit hlavu pro další iteraci. V opačném případě, pokud ƒ (hlava) je menší než nebo rovna prahové hodnotě, rozšířit hlavy a vyhoďte hlavu , zvážit své děti, jejich přidání do začátku teď . Na konci iterace se prahová hodnota zvýší, pozdější seznam se stane seznamem now a později se vyprázdní.
Důležitým rozdílem mezi okraji a A * je to, ž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 uzly, které předcházejí aktuálnímu uzlu, jsou pozdější částí a všechny ostatní jsou nyní . 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ženo jako hash tabulka a poslední pole značek je uloženo pro konstantní vyhledávání toho, zda byl uzel dříve navštíven či nikoli a zda je položka mezipaměti platná.
init(start, goal)
fringe F = s
cache C[start] = (0, null)
flimit = h(start)
found = false
while (found == false) AND (F not empty)
fmin = ∞
for node in F, from left to right
(g, parent) = C[node]
f = g + h(node)
if f > flimit
fmin = min(f, fmin)
continue
if node == goal
found = true
break
for child in children(node), from right to left
g_child = g + cost(node, child)
if C[child] != null
(g_cached, parent) = C[child]
if g_child >= g_cached
continue
if child in F
remove child from F
insert child in F past node
C[child] = (g_child, node)
remove node from F
flimit = fmin
if reachedgoal == true
reverse_path(goal)
Reverzní pseudokód.
reverse_path(node)
(g, parent) = C[node]
if parent != null
reverse_path(parent)
print node
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). Univerzita Essex, Colchester, Essex, Velká Británie, 4. – 6. Dubna 2005. IEEE 2005. https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/ publikace / cig2005.pdf
externí odkazy
- Jesús Manuel Mager Hois implementace Fringe Search v C https://github.com/pywirrarika/fringesearch