Státní prostor - State space
![]() | Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace.Únor 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |

A státní prostor je sada všech možných konfigurací systému.[1] Je to užitečná abstrakce pro úvahy o chování daného systému a je široce používána v oblastech umělá inteligence a herní teorie.
Například problém s hračkou Vakuový svět má diskrétní konečný stavový prostor, ve kterém existuje omezená sada konfigurací, ve kterých může být vakuum a špína. Systém „čítače“, kde státy jsou přirozená čísla počínaje 1 a jsou časem zvyšovány[2] má nekonečný diskrétní stavový prostor. Úhlová poloha netlumeného kyvadlo[3] je spojitý (a tedy nekonečný) stavový prostor.
Definice
V teorii dynamické systémy, diskrétní systém definovaný funkcí ƒ, stavový prostor systému lze modelovat podle pokynů graf kde každý možný stav dynamického systému je reprezentován vrcholem a existuje směrovaná hrana z A na b kdyby a jen kdyby ƒ(A) = b.[4] Toto se nazývá a stavový diagram.
Pro spojitý dynamický systém definovaný funkcí ƒ, stavový prostor systému je obraz z ƒ.
Stavové prostory jsou užitečné v počítačová věda jako jednoduchý model strojů. Formálně lze stavový prostor definovat jako a n-tice [N, A, S, G] kde:
- N je soubor států
- A je sada oblouků spojujících státy
- S je neprázdné podmnožina z N který obsahuje počáteční stavy
- G je neprázdná podmnožina N který obsahuje cíle.
Vlastnosti
A | b | C | d | E | F | G | h | ||
8 | ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() | 8 | |||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
A | b | C | d | E | F | G | h |
Stavový prostor má některé společné vlastnosti:
- složitost, kde větvící faktor je důležité
- struktura prostoru, viz také teorie grafů:
- směrovost oblouků
- strom
- zakořeněný graf
Například vakuový svět má větvící faktor 4, protože vysavač může po přesunutí skončit na 1 ze 4 sousedních čtverců (za předpokladu, že nemůže zůstat na stejném čtverci ani se nemůže pohybovat úhlopříčně). Oblouky vakuového světa jsou obousměrné, protože na libovolný čtverec lze dosáhnout z libovolného sousedního čtverce a stavový prostor není strom, protože je možné vstoupit do smyčky pohybem mezi libovolnými 4 sousedními čtverci.
Stavové prostory mohou být nekonečné nebo konečné a diskrétní nebo spojité.
Velikost
Velikost stavového prostoru pro daný systém je počet možných konfigurací prostoru.[3]
Konečný
Pokud je velikost stavového prostoru konečná, výpočet velikosti stavového prostoru je a kombinační problém.[5] Například v Osm královen puzzle, stavový prostor lze vypočítat započítáním všech možných způsobů, jak umístit 8 figurek na šachovnici 8x8. To je stejné jako výběr 8 pozic bez náhrady ze sady 64, nebo
To je podstatně více než počet legálních konfigurací královen, 92. V mnoha hrách je efektivní stavový prostor malý ve srovnání se všemi dosažitelnými / legálními státy. Tato vlastnost je také pozorována v Šachy, kde efektivním stavovým prostorem je sada pozic, kterých lze dosáhnout pomocí legálních tahů. To je mnohem menší než sada pozic, kterých lze dosáhnout umístěním kombinací dostupných šachových figurek přímo na hrací plochu.
Nekonečný
Všechny spojité stavové prostory lze popsat odpovídajícím způsobem spojitá funkce a jsou tedy nekoneční.[3] Diskrétní stavové prostory mohou mít také (spočetně ) nekonečná velikost, jako je stavový prostor časově závislého systému „počítadla“,[2] podobný systému v teorie front definování počtu zákazníků na lince, která by měla stavový prostor {0, 1, 2, 3, ...}.
Průzkum
Zkoumání stavového prostoru je proces výčtu možných stavů při hledání stavu cíle. Stavový prostor Pacman například obsahuje stav cíle, kdykoli byly snědeny všechny potravinové pelety, a je zkoumán pohybem Pacmana po hrací ploše.[6]
Hledat státy
Stav hledání je komprimovaná reprezentace stavu světa ve stavovém prostoru a používá se k průzkumu. Stavy hledání se používají, protože stavový prostor často kóduje více informací, než je nutné k prozkoumání prostoru. Komprese každého státu světa pouze na informace potřebné k průzkumu zvyšuje efektivitu snížením počtu států při hledání.[6] Například stav v prostoru Pacman zahrnuje informace o směru, kterým Pacman směřuje (nahoru, dolů, doleva nebo doprava). Vzhledem k tomu, že změna směru v Pacmanovi nic nestojí, stavy hledání pro Pacman by tyto informace nezahrnovaly a zmenšily velikost vyhledávacího prostoru o faktor 4, jeden pro každý směr, kterému by Pacman mohl čelit.
Metody
Standardní vyhledávací algoritmy jsou účinné při zkoumání diskrétních stavových prostorů. Následující algoritmy vykazují obojí úplnost a optimálnost při hledání stavového prostoru.[6][7]
Tyto metody se přirozeně nevztahují na zkoumání souvislých stavových prostorů. Zkoumání spojitého stavového prostoru při hledání daného stavu cíle je ekvivalentní optimalizaci libovolného spojitá funkce což není vždy možné, viz matematická optimalizace.
Viz také
- Reprezentace stavového prostoru pro informace o spojitém stavovém prostoru v řídicí technice.
- Stavový prostor (fyzika) pro informace o spojitém stavovém prostoru ve fyzice.
- Fázový prostor informace o fázovém stavu (jako spojitý stavový prostor) ve fyzice a matematice.
- Pravděpodobný prostor pro informace o stavovém prostoru v pravděpodobnosti.
- Složitost hry teorie, která se opírá o stavový prostor výsledků hry
- Kognitivní model # Dynamické systémy pro informace o stavovém prostoru s modelem poznávání dynamických systémů.
- Plánování státního prostoru
- Stát (informatika)
- Umělá inteligence
- Dynamické systémy
- Glosář umělé inteligence
- Strojové učení
- Matematická optimalizace
- Multiagentní systém
- Herní teorie
- Kombinatorika
Reference
- ^ Nykamp, Duane. "Definice stavového prostoru". Matematické přehledy. Citováno 17. listopadu 2019.
- ^ A b Papernick, Norman. „Nekonečné státy a přechody nekonečných států“. Univerzita Carnegie Mellon. Citováno 12. listopadu 2019.
- ^ A b C Nykamp, Duane. „Myšlenka dynamického systému“. Matematické přehledy. Citováno 12. listopadu 2019.
- ^ Laubenbacher, R. Pareigis, B. (2001). „Rovnocenné vztahy na konečných dynamických systémech“ (PDF). Pokroky v aplikované matematice. 26 (3): 237–251. doi:10.1006 / aama.2000.0717.
- ^ Zhang, Weixong (1999). Prohledávání stavového prostoru: algoritmy, složitost, rozšíření a aplikace. Springer. ISBN 978-0-387-98832-0.
- ^ A b C Abbeel, Pieter. „Přednáška 2: Neinformované vyhledávání“. UC Berkeley CS188 Úvod do AI. Citováno 30. října 2019.
- ^ Abbeel, Pieter. „Přednáška 3: Informované vyhledávání“. UC Berkeley CS188 Úvod do AI. Citováno 12. listopadu 2019.