Statlig rymdsökning

State space search är en process som används inom datavetenskap , inklusive artificiell intelligens (AI), där successiva konfigurationer eller tillstånd av en instans beaktas, med avsikten att hitta ett måltillstånd med den önskade egenskapen.

Problem modelleras ofta som ett tillståndsrum , en uppsättning tillstånd som ett problem kan befinna sig i. Uppsättningen av tillstånd bildar en graf där två tillstånd kopplas samman om det finns en operation som kan utföras för att omvandla det första tillståndet till det andra.

Tillståndsrymdsökning skiljer sig ofta från traditionella datavetenskapliga sökmetoder eftersom tillståndsutrymmet är implicit : den typiska tillståndsrymdgrafen är alldeles för stor för att generera och lagra i minnet . Istället genereras noder när de utforskas och kasseras vanligtvis därefter. En lösning på en kombinatorisk sökinstans kan bestå av själva måltillståndet, eller av en väg från något initialtillstånd till måltillståndet.

Representation

I tillståndsrymdsökning representeras ett tillståndsutrymme formellt som en tuppel ${\displaystyle S:\langle S,A, Action(s),Result(s,a),Cost(s,a)\rangle } ,$ där:

• $S$ är mängden av alla möjliga tillstånd;
• $A$ är uppsättningen av möjliga åtgärder, inte relaterade till ett visst tillstånd utan avseende hela tillståndsutrymmet;
• $Action(s)$ är funktionen som fastställer vilken åtgärd som är möjlig att utföra i ett visst tillstånd;
• $Result(s,a)$ är funktionen som returnerar det tillstånd som uppnåtts när man utför åtgärd $a$ i tillstånd $s$
• $Cost(s,a)$ är kostnaden för att utföra en åtgärd $a$ i tillstånd $s$ . I många statliga utrymmen är en konstant, men detta är inte sant i allmänhet.

Exempel på sökalgoritmer för state-space

Oinformerad sökning

Enligt Poole och Mackworth är följande oinformerade sökmetoder för tillstånd och rymd, vilket betyder att de inte har någon tidigare information om målets plats.

• Traditionell djup-först-sökning
• Utöka första sökningen
• Iterativ fördjupning
• Lägsta kostnad-först sökning / Uniform-cost search (UCS)

Dessa metoder tar målets placering i form av en heuristisk funktion . Poole och Mackworth nämner följande exempel som informerade sökalgoritmer:

• Informerat/heuristiskt djup-först sökning
• Girig bäst-första sökning
• En sökning

Se även

• Tillståndsrums
• Statlig rymdplanering
• Branch and bound - en metod för att göra sökning i tillståndsutrymmen mer effektiv genom att beskära delmängder av den.

• Stuart J. Russell och Peter Norvig (1995). Artificiell intelligens: ett modernt tillvägagångssätt . Prentice Hall.