Hledání okrajů

V informatice je okrajové vyhledávání algoritmus prohledávání grafů [ , který najde cestu s nejnižšími náklady z daného počátečního uzlu do jediného cílového uzlu .

Hranové vyhledávání je v podstatě středem mezi vyhledávacím algoritmem A* a variantou iterativního prohlubování A* ( IDA* [1] ).

Jestliže g ( x ) je cena vyhledávací cesty od prvního uzlu k aktuálnímu a h ( x ) je nákladová heuristika od aktuálního uzlu k cíli, pak ƒ ( x ) = g ( x ) + h ( x ) jsou skutečné náklady na cestu k cílům. Uvažujme IDA* , které provádí rekurzivní hloubkové prohledávání zleva doprava z kořenového uzlu a zastavuje rekurzi, jakmile je nalezen cíl nebo uzly dosáhnou své maximální hodnoty ƒ . Pokud cíl není nalezen při první iteraci ƒ, iterace je poté inkrementována a algoritmus znovu hledá. To znamená, že se opakuje v iteracích.

IDA* má tři hlavní nevýhody. Za prvé, IDA* bude opakovat stavy, když existuje více (někdy neoptimálních) cest k cílovému uzlu - to se často řeší udržováním mezipaměti navštívených stavů. Takto upravený IDA* se označuje jako paměťově rozšířený IDA* ( ME-IDA* [2] ), protože využívá určitou paměť. IDA* navíc znovu a znovu opakuje všechna předchozí vyhledávání, což je nutné pro práci bez úložiště. Tím, že ponecháme listové uzly předchozí iterace a použijeme je jako výchozí pozici pro další iteraci, účinnost IDA* se výrazně zlepší (jinak by musel vždy navštívit každý uzel ve stromu v poslední iteraci).

Edge search implementuje tato vylepšení v IDA* pomocí datové struktury sestávající z víceméně dvou seznamů k iteraci přes hranici nebo okraj vyhledávacího stromu. Jeden seznam „nyní“ ukládá aktuální iteraci a druhý seznam „pozdější“ ukládá nejbližší další iteraci. Kořenový uzel vyhledávacího stromu „nyní“ je tedy kořenem a „později“ je prázdný. Algoritmus pak provede jednu ze dvou věcí: Pokud je ƒ ( head ) větší než prahová hodnota, odebere hlavu z „nyní“ a přidá ji na konec „později“ , tj. uloží hlavu pro další iteraci. V opačném případě, pokud je ƒ ( head ) menší nebo rovno prahu, rozvine a zahodí head , zváží své potomky a přidá je na začátek "nyní" . Na konci iterace se práh zvýší, seznam „později“ se stane seznamem „nyní“ a vyprázdní se.

Důležitý rozdíl mezi edge -search a A* spočívá v tom, že obsah seznamů v edge-search nemusí být tříděn – to je významný zisk oproti A* , což vyžaduje často nákladné udržování pořádku v otevřeném seznamu. Hranové vyhledávání však bude muset na rozdíl od A* navštěvovat stejné uzly opakovaně, ale náklady na každou takovou návštěvu jsou v nejhorším případě konstantní ve srovnání s logaritmickou dobou řazení seznamu v A* .

Pseudokód

Implementace obou seznamů v jediném dvojitě propojeném seznamu, kde uzly předcházející aktuálnímu uzlu jsou „pozdější“ částí a vše ostatní je seznam „nyní“ . Použitím pole předem přidělených uzlů v seznamu pro každý uzel v mřížce se doba přístupu k uzlům v seznamu zkrátí na konstantu. Podobně pole značek umožňuje vyhledávat uzel v seznamu v konstantním čase. g je uloženo jako hashovací tabulka a poslední pole tokenů je uloženo, aby se neustále zjišťovalo, zda byl uzel již dříve navštíven a zda je záznam v mezipaměti platný .