Osavaltion avaruushaku
Tila-avaruushaku on joukko matemaattisia menetelmiä , jotka on suunniteltu ratkaisemaan tekoälyongelmia .
Tila-avaruuden hakumenetelmät skannaavat peräkkäin tehtävän konfiguraatioita tai tiloja löytääkseen kohdetilan , jolla on määritellyt ominaisuudet tai joka täyttää jonkin kriteerin.
Oletukset
Tilakuvaus sisältää kaikki tiedot, joita tarvitaan toimenpiteen tuloksen ennustamiseen ja sen määrittämiseen, onko nykyinen tila kohdetila. Tila-avaruushaku perustuu useisiin oletuksiin [1] :
- agentilla (termi "agentti" tarkoittaa jotakin mekanismia, laitetta, agenttia, joka voi siirtää tarkasteltavana olevan järjestelmän, jossa on useita tilaa, tilasta toiseen) omaa täydelliset tiedot tilaavaruudesta ja voi määrittää, missä tilassa järjestelmä on;
- agentilla on pääsy toimintosarjaan, joka siirtää järjestelmän toiseen tilaan, jonka vaikutus määritetään;
- joillekin valtioille on annettu "kohdevaltioiden" asema; agentin tehtävänä on saavuttaa jokin kohdetiloista; kun tavoitetila saavutetaan, agentti voi määrittää, että saavutettu tila on kohdetila;
- hakuongelman ratkaisu on toimintosarja (järjestelmän tilan muutokset), jotka mahdollistavat agentin siirtymisen nykyisestä tai alkutilasta (yhteen) kohdetiloihin.
Ongelman muodollinen määritelmä
Tehtävän osat
Monissa tehtävissä on diskreetti joukko tiloja, joissa tietty objekti tai järjestelmä voi olla, ja niillä on säännöt ja ehdot siirtymiselle tilasta toiseen (esimerkiksi peleissä). Tällaiset tehtävät voidaan määritellä muodollisesti käyttämällä neljää komponenttia:
- Alkutila - tila, jossa järjestelmä on alkuhetkellä;
- Seuraajamäärittelyfunktio on kuvaus mahdollisista siirtymistä tilasta toiseen;
- Tavoitteen tarkistus - jokin algoritmi, jonka avulla voit määrittää, onko tietty tila tavoite;
- Polkukustannusfunktio on funktio, joka määrittää kustakin tilasiirtymän sekvenssistä hinnan. Yksinkertaisimmassa tapauksessa siirtymäketjun kustannusten oletetaan olevan yhtä suuri kuin siirtymien lukumäärä ketjussa.
Vaihtoehtoinen määritelmä tila-avaruushakuongelmalle [1] sisältää
- joukko valtioita ;
- erottuva tilojen osajoukko, jota kutsutaan aloitustiloiksi ;
- jokaiselle tilalle joukko toimintoja, jotka ovat agentin käytettävissä tässä tilassa;
- toimintafunktio , joka tietylle tilalle ja siinä tilassa käytettävissä olevalle toiminnolle palauttaa uuden tilan;
- joukko tavoitetiloja , jotka usein määritellään loogisen funktion tavoite(t) avulla, joka arvo on tosi, kun s on tavoitetila,
- kriteeri, joka määrittää hyväksyttävän ratkaisun laadun . Tämä voi sisältää rajoituksia ratkaisun toimien lukumäärälle, ratkaisun kokonaiskustannuksille, vaatimus, että ratkaisu on optimaalinen toimien lukumäärän tai kokonaiskustannusten suhteen.
Tilaavaruuskaavio
Useimmat graafihaun algoritmiset formulaatiot käyttävät eksplisiittisen graafin käsitettä . Graafi voidaan esittää viereisyysmatriisina tai viereisyysluettelona .
Tila-avaruushakualgoritmeissa käytetään implisiittisen graafin käsitettä . Ero implisiittisen graafin ja eksplisiittisesti annetun graafin välillä on se, että graafin reunoja ei tallenneta eksplisiittisesti muistiin, vaan ne luodaan "lennossa" ( englanniksi on-the-fly ) siirtymäsääntöjen mukaisesti. osavaltioiden välillä. Tila-avaruusgraafin määritelmä sisältää alkupisteen , joukon kohdepisteitä ja kärjen avausproseduurin [2] .
Ongelman ratkaisu
Ongelman ratkaisu on polku alkutilasta kohdetilaan.
Optimaalinen ratkaisu on kaikista muista ratkaisuista edullisin ratkaisu.
Hakualgoritmin arviointi
Algoritmin laatua arvioidaan neljällä pääindikaattorilla:
- Täydellisyys - algoritmin ominaisuus löytää aina ratkaisu, jos se on olemassa;
- Optimaalisuus on algoritmin ominaisuus löytää aina ratkaisu halvimmalla hinnalla;
- Aika monimutkaisuus - algoritmin käyntiajan estimointi;
- Tilan monimutkaisuus on arvio algoritmin vaatimasta muistin määrästä.
Tila-avaruuden hakumenetelmät
Tila-avaruuden etsintämenetelmät jaetaan informoituihin ja epätietoisiin .
Epätietoiset menetelmät ( sokeat etsintämenetelmät , brute force -menetelmät ) eivät käytä mitään tietoa tietystä tehtävästä, paitsi tietoa siitä, kuinka kohdetila voidaan erottaa muista.
Tämän ryhmän algoritmit generoivat peräkkäin kaikki mahdolliset saavutettavat tilat alkutilasta, kunnes kohdetila (ratkaisu) löydetään. Tiedonhaun menetelmien väliset erot laskeutuvat siihen järjestykseen, jossa tilat etsitään.
Tietoon perustuvat hakumenetelmät ( heuristiset menetelmät ) hyödyntävät lisätietoa tietystä tehtävästä. Lisätietojen ( heuristiikka ) avulla voit vähentää luettelointia poistamalla ilmeisen lupaamattomat vaihtoehdot. Tämä lähestymistapa nopeuttaa algoritmia verrattuna kattavaan hakuun . Heurististen algoritmien haittana voi olla, että ei ole takeita siitä, että oikea tai paras mahdollinen ratkaisu valitaan.
Katso myös
Muistiinpanot
- ↑ 1 2 David Poole ja Alan Mackworth. 3.2 Tila-avaruudet . Tekoäly - laskennallisten agenttien perusteet . Haettu 5. joulukuuta 2015. Arkistoitu alkuperäisestä 25. marraskuuta 2015.
- ↑ Edelkamp Stefan, Schrödl Stefan. Heuristinen haku: teoria ja sovellukset. - Morgan Kaufmann Publishers , 2012. - 712 s. — ISBN 978-0-12-372512-7 .
Kirjallisuus
- Russell Stewart, Norvig Peter. Tekoäly : moderni lähestymistapa = tekoäly: moderni lähestymistapa. - 2. painos - M .: Williams, 2006. - 1408 s. — ISBN 5-8459-0887-6 .