Obousměrné vyhledávání

Obousměrné prohledávání šířky (nebo hloubky) [1] [2] je sofistikovaný algoritmus prohledávání šířky (nebo hloubky ) , jehož myšlenkou je vytvořit proces vyhledávání od počátečního ( dopředné vyhledávání ) a od konečného vrcholu ( zpět ). vyhledávání ) grafu .

Nápad

Nalezení požadované cesty spočívá v určení cest od počátečního k nějakému mezilehlému a od něj ke konečnému vrcholu. Implementováno kontrolou jednoho nebo obou procesů, když se list jednoho vyhledávacího stromu shoduje s listem jiného, ​​načež jsou extrahovány cesty k tomuto prvku. Spojením cest získáme požadovanou cestu. Pokud jsou paralelně prováděna dvě vyhledávání  , ušetří se tím ještě více času na získání požadované cesty ve srovnání s jednosměrným vyhledáváním.

Výhody a nevýhody

• Zvýšený výkon;
• K uložení vyhledávacího stromu potřebujete paměť, abyste mohli zkontrolovat, zda list patří jinému stromu.

Skóre obtížnosti

Složitost celého algoritmu se odhaduje jako součet složitosti dopředného a zpětného vyhledávání, kontrola členství rovná jedné operaci, konstantní čas (O (n)), přístup k hashovací tabulce .

Počítání počtu operací

Příliš závislé na konkrétní situaci, pokud hledání není na n-árním stromě .

Asymptotická složitost rostoucího počtu operací

• Pokud jsou známy jediné specifické počáteční a cílové prvky, pak je asymptotická časová složitost dopředného a zpětného vyhledávání rovna , tedy celkem - + , což je mnohem menší než . Prostorová asymptotická složitost namísto přímé, protože je třeba ji uložit do paměti.
• Pokud je znám konkrétní počáteční prvek a sada prvků, z nichž jeden je cílovým prvkem.

Statistické vyhodnocení

Obousměrné vyhledávání s jedním počátečním a koncovým prvkem může zlepšit jednosměrné vyhledávání na šířku, obvykle faktorem 2. Nejobtížnějším případem pro obousměrné vyhledávání je takový problém, ve kterém je pro kontrolu cíle uveden pouze implicitní popis nějaké (možná velmi velké) množiny cílových stavů, například všechny stavy odpovídající matu cíle „Šachy "v šachu . " Při reverzním vyhledávání by bylo nutné vytvořit kompaktní popisy všech stavů, které umožňují mat s tahy atd.; a tyto popisy by musely být porovnány se stavy generovanými přímým vyhledáváním. Neexistuje obecný způsob, jak takový problém efektivně vyřešit.

Obousměrný vyhledávací algoritmus

Algoritmus se skládá z:

• přímé vyhledávání, podobné jednoduchému vyhledávání;
• zpětné vyhledávání;
• operace pro určení, zda list patří do jiného vyhledávacího stromu.

Složitost implementace

Složitost implementace spočívá v algoritmu zpětného vyhledávání.

Příklady implementace

Praktická aplikace

Viz také

• Šířka první hledání
• Hloubka první hledání

Poznámky

1. ↑ Jiné: obousměrné vyhledávání prvků - provádí se v obousměrných nebo kruhových seznamech od požadovaného prvku v obou směrech.
2. ↑ [1]  (downlink) Tento algoritmus je úplný a optimální (s jednotnými náklady na kroky), pokud jsou oba vyhledávací procesy napřed; jiné kombinace metod mohou postrádat úplnost, optimalitu nebo obojí.

Odkazy

• Algoritmy hledání cesty na pmg.org.ru
• Modely a metody řešení problémů na Mari El.ru
• Implementace C++ (aisearch.tgz) na www.cs.cmu.edu

Literatura

• Stuart Russell a Peter Norvig. Část 2. Řešení problémů // Umělá inteligence (moderní přístup) = Umělá inteligence (moderní přístup). - 2. vyd. - FGUP. "Tiskový dvůr" A.M. Gorkij: Williams, 2006. - S. 135-136. — ISBN 5-8459-0887-6 .