State Space Search
State space search er en gruppe af matematiske metoder designet til at løse kunstig intelligens problemer .
State-space-søgningsmetoder scanner sekventielt en opgaves konfigurationer eller tilstande for at finde en måltilstand, der har specificerede karakteristika eller opfylder et eller andet kriterium.
Antagelser
Tilstandsbeskrivelsen indeholder al den information, der er nødvendig for at forudsige resultatet af en handling og bestemme, om den aktuelle tilstand er måltilstanden. State-space-søgning er baseret på flere antagelser [1] :
- en agent (udtrykket "agent" betyder en eller anden mekanisme, enhed, agent, der kan overføre det betragtede system med mange tilstande fra en tilstand til en anden tilstand) har fuldstændig information om tilstandsrummet og kan bestemme, hvilken tilstand systemet er i;
- agenten har adgang til et sæt handlinger, der overfører systemet til en anden tilstand, hvis virkning bestemmes;
- nogle stater er blevet tildelt status som "målstater"; agentens opgave er at nå en af måltilstandene; når måltilstanden er nået, kan agenten bestemme, at den nåede tilstand er måltilstanden;
- løsningen af søgeproblemet er en sekvens af handlinger (ændringer i systemets tilstand), som vil tillade agenten at flytte fra den nuværende eller oprindelige tilstand til (en af) måltilstandene.
Formel definition af problemet
Opgavekomponenter
I mange opgaver er der et diskret sæt af tilstande, hvor et bestemt objekt eller system kan være, med regler og betingelser for overgangen fra en tilstand til en anden (for eksempel i spil). Sådanne opgaver kan formelt defineres ved hjælp af fire komponenter:
- Indledende tilstand - den tilstand, hvori systemet er i det indledende øjeblik;
- Efterfølgerdefinitionsfunktionen er en beskrivelse af mulige overgange fra en tilstand til en anden;
- Målkontrol - en eller anden algoritme, der giver dig mulighed for at bestemme, om en given tilstand er et mål;
- En stiomkostningsfunktion er en funktion, der tildeler en omkostning til hver sekvens af tilstandsovergange. I det simpleste tilfælde antages omkostningerne ved en overgangskæde at være lig med antallet af overgange i kæden.
En alternativ definition af tilstands-rumsøgningsproblemet [1] omfatter
- sæt af stater ;
- en fornemt delmængde af tilstande, kaldet begyndelsestilstande ;
- for hver stat, et sæt handlinger, der er tilgængelige for agenten i denne tilstand;
- en handlingsfunktion, der for en given tilstand og en handling tilgængelig i denne tilstand returnerer en ny tilstand;
- sæt af måltilstande , ofte defineret af den boolske funktion mål(er) , som evalueres til sand, når s er måltilstanden,
- kriterium, der bestemmer kvaliteten af en acceptabel løsning . Dette kan omfatte begrænsninger på antallet af handlinger i løsningen, den samlede pris for løsningen, kravet om, at løsningen skal være optimal i forhold til antallet eller de samlede omkostninger ved handlinger.
State space graph
De fleste algoritmiske formuleringer af grafsøgning bruger begrebet en eksplicit graf . En graf kan repræsenteres som en tilgrænsende matrix eller en tilgrænsende liste .
I state-space søgealgoritmer bruges begrebet en implicit graf . Forskellen mellem en implicit graf og en eksplicit givet graf er, at grafens kanter ikke er eksplicit gemt i hukommelsen, men genereres "on-the-fly" ( engelsk on-the-fly ) i overensstemmelse med overgangsreglerne mellem stater. Definitionen af en tilstands-rum-graf inkluderer et startpunkt , et sæt målhjørner og en udfoldningsprocedure for vertex [2] .
Løsning af problemet
Løsningen af problemet er vejen fra starttilstanden til måltilstanden.
Den optimale løsning er den løsning, der har de laveste omkostninger blandt alle andre løsninger.
Evaluering af søgealgoritmen
Kvaliteten af algoritmen evalueres ved hjælp af fire hovedindikatorer:
- Fuldstændighed - algoritmens egenskab til altid at finde en løsning, hvis den eksisterer;
- Optimalitet er en algoritmes egenskab til altid at finde løsningen med de laveste omkostninger;
- Tidskompleksitet - estimering af algoritmens køretid;
- Rumkompleksitet er et skøn over mængden af hukommelse, der kræves af en algoritme.
State-space søgemetoder
Søgningsmetoder i stats-rum er opdelt i informerede og uinformerede .
Uinformerede metoder ( blinde søgemetoder , brute force-metoder ) bruger ingen information om en bestemt opgave udover information om, hvordan man skelner måltilstanden fra enhver anden.
Algoritmerne for denne gruppe genererer sekventielt alle mulige tilstande, der kan nås fra starttilstanden, indtil måltilstanden (løsningen) er fundet. Forskellene mellem metoderne til uinformeret søgning kommer ned til den rækkefølge, staterne slås op i.
Informerede søgemetoder ( heuristiske metoder ) udnytter yderligere information om en bestemt opgave. Yderligere information ( heuristik ) giver dig mulighed for at reducere opregningen ved at eliminere åbenlyst lovende muligheder. Denne tilgang fremskynder algoritmen sammenlignet med udtømmende søgning . En ulempe ved heuristiske algoritmer kan være, at der ikke er garanti for, at den korrekte eller bedst mulige løsning er valgt.
Se også
Noter
- ↑ 1 2 David Poole og Alan Mackworth. 3.2 Tilstandsrum . Kunstig intelligens - grundlaget for beregningsagenter . Hentet 5. december 2015. Arkiveret fra originalen 25. november 2015.
- ↑ Edelkamp Stefan, Schrödl Stefan. Heuristisk søgning: teori og anvendelser. - Morgan Kaufmann Publishers , 2012. - 712 s. — ISBN 978-0-12-372512-7 .
Litteratur
- Russell Stewart, Norvig Peter. Artificial Intelligence: A Modern Approach = Artificial Intelligence: A Modern Approach. - 2. udg. - M. : Williams, 2006. - 1408 s. — ISBN 5-8459-0887-6 .