State Space Search
State space search är en grupp matematiska metoder utformade för att lösa artificiell intelligensproblem .
Sökmetoder för tillståndsrymden skannar sekventiellt konfigurationerna eller tillstånden för en uppgift för att hitta ett måltillstånd som har specificerade egenskaper eller som uppfyller något kriterium.
Antaganden
Tillståndsbeskrivningen innehåller all information som behövs för att förutsäga resultatet av en åtgärd och avgöra om det aktuella tillståndet är måltillståndet. Sökning av tillstånd och rymd baseras på flera antaganden [1] :
- en agent (termen "agent" betyder någon mekanism, enhet, agent som kan överföra det betraktade systemet med många tillstånd från ett tillstånd till ett annat tillstånd) har fullständig information om tillståndsutrymmet och kan avgöra vilket tillstånd systemet är i;
- agenten har tillgång till en uppsättning åtgärder som överför systemet till ett annat tillstånd, vars effekt bestäms;
- vissa stater har tilldelats statusen "målstater"; agentens uppgift är att nå ett av måltillstånden; när måltillståndet nås, kan agenten bestämma att det uppnådda tillståndet är måltillståndet;
- lösningen på sökproblemet är en sekvens av åtgärder (förändringar i systemets tillstånd) som gör att agenten kan flytta från det nuvarande eller initiala tillståndet till (ett av) måltillstånden.
Formell definition av problemet
Uppgiftskomponenter
I många uppgifter finns det en diskret uppsättning tillstånd där ett visst objekt eller system kan vara, med regler och villkor för övergången från ett tillstånd till ett annat (till exempel i spel). Sådana uppgifter kan formellt definieras med hjälp av fyra komponenter:
- Initialt tillstånd - det tillstånd i vilket systemet är i det initiala ögonblicket;
- Efterföljardefinitionsfunktionen är en beskrivning av möjliga övergångar från ett tillstånd till ett annat;
- Målkontroll - någon algoritm som låter dig avgöra om ett givet tillstånd är ett mål;
- En vägkostnadsfunktion är en funktion som tilldelar en kostnad till varje sekvens av tillståndsövergångar. I det enklaste fallet antas kostnaden för en övergångskedja vara lika med antalet övergångar i kedjan.
En alternativ definition av tillståndsrymdsökningsproblemet [1] inkluderar
- uppsättning tillstånd ;
- en distingerad delmängd av tillstånd, kallade initiala tillstånd ;
- för varje tillstånd, en uppsättning åtgärder tillgängliga för agenten i detta tillstånd;
- en åtgärdsfunktion som, för ett givet tillstånd och en åtgärd tillgänglig i det tillståndet, returnerar ett nytt tillstånd;
- uppsättning måltillstånd , ofta definierade av den booleska funktionen goal(s) , som utvärderas till sant när s är måltillståndet,
- kriterium som avgör kvaliteten på en acceptabel lösning . Detta kan innefatta begränsningar av antalet åtgärder i lösningen, den totala kostnaden för lösningen, kravet på att lösningen ska vara optimal vad gäller antalet eller totala kostnaden för åtgärder.
State space graph
De flesta algoritmiska formuleringar av grafsökning använder begreppet en explicit graf . En graf kan representeras som en närliggande matris eller en närliggande lista .
I tillståndsrymdsökningsalgoritmer används konceptet med en implicit graf . Skillnaden mellan en implicit graf och en explicit given graf är att kanterna på grafen inte explicit lagras i minnet, utan genereras "on-the-fly" ( engelska on-the-fly ) i enlighet med övergångsreglerna mellan stater. Definitionen av en tillståndsrymdgraf inkluderar en startpunkt , en uppsättning målpunktspunkter och en procedur för utvikning av vertex [2] .
Lösning på problemet
Lösningen på problemet är vägen från initialtillståndet till måltillståndet.
Den optimala lösningen är den lösning som har den lägsta kostnaden av alla andra lösningar.
Utvärdering av sökalgoritmen
Kvaliteten på algoritmen utvärderas med hjälp av fyra huvudindikatorer:
- Fullständighet - egenskapen hos algoritmen att alltid hitta en lösning om den finns;
- Optimalitet är egenskapen hos en algoritm att alltid hitta lösningen med lägsta kostnad;
- Tidskomplexitet - uppskattning av algoritmens gångtid;
- Utrymmeskomplexitet är en uppskattning av mängden minne som krävs av en algoritm.
State-space sökmetoder
Sökmetoder för statligt utrymme är indelade i informerade och oinformerade .
Oinformerade metoder ( blinda sökmetoder , brute force-metoder ) använder ingen information om en viss uppgift, annat än information om hur man skiljer måltillståndet från något annat.
Algoritmerna för denna grupp genererar sekventiellt alla möjliga tillstånd som kan nås från det initiala tillståndet tills måltillståndet (lösningen) hittas. Skillnaderna mellan metoderna för oinformerad sökning kommer ner till den ordning i vilken staterna slås upp.
Informerade sökmetoder ( heuristiska metoder ) drar fördel av ytterligare information om en viss uppgift. Ytterligare information ( heuristik ) gör att du kan minska uppräkningen genom att eliminera uppenbart föga lovande alternativ. Detta tillvägagångssätt snabbar på algoritmen jämfört med uttömmande sökning . En nackdel med heuristiska algoritmer kan vara att det inte finns någon garanti för att rätt eller bästa möjliga lösning väljs.
Se även
Anteckningar
- ↑ 1 2 David Poole och Alan Mackworth. 3.2 Tillståndsutrymmen . Artificiell intelligens - grunderna för beräkningsagenter . Hämtad 5 december 2015. Arkiverad från originalet 25 november 2015.
- ↑ Edelkamp Stefan, Schrödl Stefan. Heuristisk sökning: teori och tillämpningar. - Morgan Kaufmann Publishers , 2012. - 712 sid. — ISBN 978-0-12-372512-7 .
Litteratur
- Russell Stewart, Norvig Peter. Artificiell intelligens: ett modernt tillvägagångssätt = Artificial Intelligence: A Modern Approach. - 2:a uppl. - M. : Williams, 2006. - 1408 sid. — ISBN 5-8459-0887-6 .