State space (datavetenskap)

"State space" omdirigerar hit. För annan användning, se State space (disambiguation) .

Vacuum World, ett problem med kortaste vägen med ett ändligt tillståndsutrymme

Inom datavetenskap är ett tillståndsutrymme ett diskret utrymme som representerar uppsättningen av alla möjliga konfigurationer av ett "system". Det är en användbar abstraktion för resonemang om beteendet hos ett givet system och används flitigt inom områdena artificiell intelligens och spelteori .

Till exempel har leksaksproblemet Vacuum World ett diskret ändligt tillståndsutrymme där det finns en begränsad uppsättning konfigurationer som vakuum och smuts kan vara i. Ett "räknare"-system, där tillstånd är de naturliga talen som börjar på 1 och inkrementeras med tiden har ett oändligt diskret tillståndsrum. Vinkelpositionen för en odämpad pendel är ett kontinuerligt (och därför oändligt) tillståndsrum.

Definition

Tillståndsrum är användbara inom datavetenskap som en enkel modell av maskiner. Formellt kan ett tillståndsutrymme definieras som en tuppel [ N , A , S , G ] där:

• N är en uppsättning tillstånd
• A är en uppsättning bågar som förbinder tillstånden
• S är en icke-tom delmängd av N som innehåller starttillstånd
• G är en icke-tom delmängd av N som innehåller måltillstånden.

Egenskaper

	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

Ett giltigt tillstånd i tillståndsutrymmet för pusslet med åtta drottningar

Ett tillståndsutrymme har några gemensamma egenskaper:

• komplexitet, där förgreningsfaktor är viktig
• rummets struktur, se även grafteori :
  • bågars riktning
  • träd
  • rotad graf

Vacuum World har till exempel en förgreningsfaktor på 4, eftersom dammsugaren kan hamna i 1 av 4 intilliggande rutor efter att ha flyttat (förutsatt att den inte kan stanna i samma ruta eller röra sig diagonalt). Bågarna i Vacuum World är dubbelriktade, eftersom vilken ruta som helst kan nås från vilken intilliggande ruta som helst, och tillståndsutrymmet är inte ett träd eftersom det är möjligt att gå in i en slinga genom att flytta mellan vilka 4 angränsande rutor som helst.

Tillståndsrum kan vara antingen oändliga eller ändliga, och diskreta eller kontinuerliga.

Storlek

Storleken på tillståndsutrymmet för ett givet system är antalet möjliga konfigurationer av utrymmet.

Ändlig

kombinatoriskt problem att beräkna storleken på tillståndsutrymmet. Till exempel, i pusslet åtta drottningar , kan tillståndsutrymmet beräknas genom att räkna alla möjliga sätt att placera 8 pjäser på ett 8x8 schackbräde. Detta är samma sak som att välja 8 positioner utan ersättning från en uppsättning av 64, eller

${\binom {64}{8}}=4,426,165,368$

Detta är betydligt fler än antalet lagliga konfigurationer av drottningarna, 92. I många spel är det effektiva tillståndsutrymmet litet jämfört med alla nåbara/lagliga stater. Den här egenskapen observeras också i schack , där det effektiva tillståndsutrymmet är den uppsättning positioner som kan nås med spellagliga drag. Detta är mycket mindre än den uppsättning positioner som kan uppnås genom att placera kombinationer av tillgängliga schackpjäser direkt på brädet.

Oändlig

Alla kontinuerliga tillståndsrum kan beskrivas med en motsvarande kontinuerlig funktion och är därför oändliga. Diskreta tillståndsutrymmen kan också ha ( uttalbart ) oändlig storlek, såsom tillståndsutrymmet för det tidsberoende "räknarsystemet", liknande systemet i köteorin som definierar antalet kunder på en rad, vilket skulle ha tillståndsutrymme {0 , 1, 2, 3, ...}.

Utforskning

Huvudartikel: statlig rymdsökning

Att utforska ett tillståndsrum är processen att räkna upp möjliga tillstånd på jakt efter ett måltillstånd. Tillståndsutrymmet i Pacman , till exempel, innehåller ett måltillstånd närhelst alla matpellets har ätits, och utforskas genom att flytta Pacman runt på brädet.

Sök stater

Ett söktillstånd är en komprimerad representation av en världsstat i ett tillståndsrum och används för utforskning. Söktillstånd används eftersom ett tillståndsutrymme ofta kodar mer information än vad som är nödvändigt för att utforska utrymmet. Att komprimera varje världsstat till endast information som behövs för utforskning förbättrar effektiviteten genom att minska antalet stater i sökningen. Till exempel innehåller ett tillstånd i Pacman-utrymmet information om riktningen Pacman är vänd (upp, ner, vänster eller höger). Eftersom det inte kostar något att ändra riktning i Pacman, skulle söktillstånd för Pacman inte inkludera denna information och minska storleken på sökutrymmet med en faktor 4, en för varje riktning som Pacman kan vara vänd mot.

Metoder

Standardsökalgoritmer är effektiva för att utforska diskreta tillståndsutrymmen. Följande algoritmer uppvisar både fullständighet och optimalitet vid sökning av ett tillståndsutrymme.

• Utöka första sökningen
• En sökning
• Enhetlig kostnadssökning

Dessa metoder sträcker sig inte naturligt till att utforska kontinuerliga tillståndsrum. Att utforska ett kontinuerligt tillståndsrum i jakt på ett givet måltillstånd är likvärdigt med att optimera en godtycklig kontinuerlig funktion som inte alltid är möjlig, se matematisk optimering .

Se även

• Fasutrymme för information om fastillstånd (som kontinuerligt tillståndsrum) i fysik och matematik.
• Sannolikhetsutrymme för information om tillståndsutrymme i sannolikhet.
• Spelkomplexitetsteori , som bygger på tillståndsutrymmet för spelresultat
• Kognitiv modell#Dynamiska system för information om tillståndsrum med en dynamisk systemmodell för kognition.
• Statlig rymdplanering
• Stat (datavetenskap)
• Artificiell intelligens
• Dynamiska system
• Ordlista över artificiell intelligens
• Maskininlärning
• Matematisk optimering
• Multi-agent system
• Spel teori
• Kombinatorik