Hledání stavového prostoru - State space search

Hledání stavového prostoru je proces používaný v oblasti počítačová věda, počítaje v to umělá inteligence (AI), ve kterém za sebou konfigurace nebo státy instance jsou zvažovány, s úmyslem najít a stav cíle s požadovanou vlastností.

Problémy jsou často modelovány jako a státní prostor, a soubor z státy že problém může být v. Soubor stavů tvoří a graf kde jsou dva státy spojeny, pokud existuje úkon které lze provést k transformaci prvního stavu do druhého.

Hledání stavového prostoru se často liší od tradičního počítačová věda Vyhledávání metody, protože stavový prostor je implicitní: typický stavový prostorový graf je příliš velký na to, aby se generoval a ukládal Paměť. Místo toho se uzly generují tak, jak jsou prozkoumávány, a poté se obvykle zahodí. Řešení a kombinatorické vyhledávání instance se může skládat ze samotného stavu cíle nebo z cesty z některých počáteční stav do stavu cíle.

Zastoupení

Při hledání stavového prostoru je stavový prostor formálně reprezentován jako n-tice ${ displaystyle S: langle S, A, Akce (akce), Výsledek (s, a), Náklady (s, a) rangle}$, ve kterém:

• ${ displaystyle S}$ je soubor všech možných stavů;
• ${ displaystyle A}$ je sada možných akcí, která nesouvisí s konkrétním stavem, ale týká se celého stavového prostoru;
• ${ displaystyle Akce}}$ je funkce, která určuje, kterou akci je možné provést v určitém stavu;
• ${ displaystyle Výsledek (s, a)}$ je funkce, která vrací stav dosažený při provádění akce ${ displaystyle a}$ ve stavu ${ displaystyle s}$
• ${ displaystyle náklady (s, a)}$ jsou náklady na provedení akce ${ displaystyle a}$ ve stavu ${ displaystyle s}$. V mnoha stavových prostorech je konstanta, ale obecně to není pravda.

Příklady algoritmů prohledávání stavového prostoru

Neinformované vyhledávání

Podle Poole a Mackwortha jsou následující neinformovaný metody prohledávání stavového prostoru, což znamená, že nemají žádné předchozí informace o poloze cíle.^[1]

• Tradiční vyhledávání do hloubky
• Šířka první vyhledávání
• Iterativní prohlubování
• Hledání s nejnižší cenou za první

Heuristické vyhledávání

Některé algoritmy berou v úvahu informace o umístění uzlu cíle ve formě a heuristická funkce^[2]. Poole a Mackworth uvádějí následující příklady jako informované vyhledávací algoritmy:

• Heuristické hloubkové vyhledávání
• Greedy best-first search
• Hledání

Viz také

• Státní prostor
• Plánování státního prostoru

Reference

• Stuart J. Russell a Peter Norvig (1995). Umělá inteligence: moderní přístup. Prentice Hall.

Tento umělá inteligence související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.