Kombinatorické vyhledávání - Combinatorial search

v počítačová věda a umělá inteligence, kombinatorické vyhledávání studie vyhledávací algoritmy pro řešení instancí problémů, o kterých se obecně věří, že jsou těžké, efektivním prozkoumáním obvykle velkého prostoru řešení těchto instancí. Algoritmy kombinatorického vyhledávání dosahují této efektivity snížením efektivní velikosti vyhledávacího prostoru nebo využitím heuristiky. Některé algoritmy zaručeně najdou optimální řešení, zatímco jiné mohou vrátit pouze nejlepší řešení nalezené v části stavového prostoru, která byla prozkoumána.

Klasické kombinatorické vyhledávací problémy zahrnují řešení osm královen puzzle nebo vyhodnocování tahů ve hrách s velkým herní strom, jako reverzní nebo šachy.

Studie o teorie výpočetní složitosti pomáhá motivovat kombinatorické vyhledávání. Algoritmy kombinatorického vyhledávání se obvykle zabývají problémy, které jsou NP-tvrdé. O takových problémech se obecně nepředpokládá, že jsou efektivně řešitelné. Různé aproximace teorie složitosti však naznačují, že některé instance (např. „Malé“ instance) těchto problémů lze efektivně vyřešit. Je tomu skutečně tak a takové případy mají často důležité praktické důsledky.

Příklady

Mezi běžné algoritmy pro řešení problémů kombinatorického vyhledávání patří:

Dívat se dopředu

Lookahead je důležitou součástí kombinatorického vyhledávání, které zhruba určuje, jak hluboce graf prozkoumává se představující problém. Potřeba konkrétního omezení vzhledu vychází z velkých problémových grafů v mnoha aplikacích, například počítačové šachy a počítač Go. Naivní vyhledávání na šířku těchto grafů by rychle spotřebovalo veškerou paměť jakéhokoli moderního počítače. Nastavením konkrétního limitu lookahead lze čas algoritmu pečlivě řídit; je čas exponenciálně roste jak se zvyšuje limit vyhledávání

Sofistikovanější vyhledávací techniky, jako je prořezávání alfa-beta jsou schopni vyloučit z úvahy celé podstromy vyhledávacího stromu. Pokud jsou použity tyto techniky, lookahead není přesně definovaná veličina, ale místo toho buď maximální hledaná hloubka, nebo nějaký typ průměru.

Viz také

Reference