Tietoinen hakumenetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 29. kesäkuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Tietoinen haku (myös heuristinen haku , eng.  informed search, heuristinen haku ) on tila-avaruuden ratkaisujen etsimisstrategia , jossa käytetään tiettyyn tehtävään liittyvää tietoa. Tietoon perustuvat menetelmät tarjoavat yleensä tehokkaampia hakuja kuin epätietoiset menetelmät .

Tietyn tehtävän tiedot on muotoiltu heuristiseksi funktioksi . Heuristinen toiminto jokaisessa haun vaiheessa arvioi vaihtoehdot lisätietojen perusteella päättääkseen, mihin suuntaan hakua jatketaan [1] .

Heuristiset funktiot

Tila-avaruushaun yhteydessä heuristinen funktio h ( n ) määritellään iteraatiopuun solmuissa seuraavasti :  

h ( n ) = kustannusarvio halvimmasta polusta solmusta n kohdesolmuun.

Jos n  on kohdesolmu, niin h ( n ) = 0.

Käyttöön otettava solmu valitaan arviointitoiminnon perusteella 

f ( n ) = solmun n kautta kulkevan halvimman ratkaisupolun kustannusarvio , f ( n ) = g ( n ) + h ( n ),

jossa funktio g ( n ) määrittää lähtösolmusta solmuun n jo kuljetun polun hinnan .

Jos heuristinen funktio h ( n ) ei koskaan yliarvioi tavoitteen saavuttamisen todellisia vähimmäiskustannuksia (eli se on pienempi arvio todellisista kustannuksista), niin tällaista funktiota kutsutaan hyväksytyksi . 

Jos heuristinen funktio h ( n ) täyttää ehdon

h ( a ) ≤ kustannus ( a , b ) + h ( b ),

missä b on a :  n jälkeläinen , niin tällaista funktiota kutsutaan peräkkäiseksi ( englanniksi  konsistentti ).

Jos f ( n ) = g ( n ) + h ( n ) on arviointifunktio, h ( n ) on seuraajafunktio, niin funktio f ( n ) on monotonisesti ei-pienevä millä tahansa tutkittavalla polulla. Siksi peräkkäisiä funktioita kutsutaan myös monotonisiksi ( eng.  monotoniksi ).

Kaikki seuraavat toiminnot ovat hyväksyttäviä, mutta kaikki hyväksyttävät toiminnot eivät ole seuraajia.

Jos h 1 ( n ), h 2 ( n ) ovat kelvollisia heuristisia funktioita ja mille tahansa solmulle n epäyhtälö h 1 ( n ) ≥ h 2 ( n ) on tosi, niin h 1 on tietoisempi heuristinen tai hallitsee h :ta 2 .

Jos ongelmalla on hyväksyttävät heuristiikka h 1 ja h 2 , niin heuristinen h ( n ) = max( h 1 , h 2 ) on hyväksyttävä ja hallitsee jokaista alkuperäistä heuristiikkaa [1] [2] .

Heurististen funktioiden vertailu

Kun verrataan sallittuja heuristiikkaa, tietoisuuden aste ja laskennan tilallinen ja ajallinen monimutkaisuus ovat tärkeitä. Tietoisempi heuristiikka voi vähentää käytettyjen solmujen määrää, vaikka sen tekeminen saattaakin olla aika, joka kuluu kunkin solmun heuristiikan laskemiseen.

Tehokas haaroituskerroin on laskentapuun solmujen  seuraajien keskimääräinen lukumäärä heurististen karsintamenetelmien soveltamisen jälkeen [1] [2] . Tehokkaan haarautumiskertoimen perusteella voidaan arvioida käytetyn heuristisen funktion laatu.

Ihanteellinen heuristinen funktio (kuten hakutaulukko ) palauttaa aina tarkat arvot lyhimmän ratkaisun pituudelle, joten laskentapuu sisältää vain optimaaliset ratkaisut. Ihanteellisen heuristisen funktion tehollinen haarautumiskerroin on lähellä yhtä [1] .

Esimerkkejä hakutehtävistä

Malleina hakualgoritmien ja heurististen funktioiden testaamiseen käytetään usein permutaatiopulmia  - viisitoista 3 × 3 [3] [4] , 4 × 4 [5] [6] [7] , 5 × 5 [8] [9] [ 10 ] , 6×6 [11] , Rubikin kuutio [9] [12] , Hanoin torni neljällä sauvalla [11] [13] .

"Fifteen" -pulmapelissä voidaan soveltaa Manhattanin etäisyyteen perustuvaa h m -heuristiikkaa . Tarkemmin sanottuna kullekin laatalle lasketaan Manhattanin etäisyys sen nykyisen sijainnin ja alkuperäisen sijainnin välillä; saadut arvot lasketaan yhteen.

Voidaan osoittaa, että tämä heuristiikka on hyväksyttävä ja peräkkäinen: sen arvo ei voi muuttua enempää kuin ±1 yhdellä liikkeellä.

Heurististen funktioiden rakentaminen

Rento tehtävä

"Fifteen"-pulman ratkaisemiseen käytetty heuristinen funktio h m on alempi arvio optimaalisen ratkaisun pituudesta. Lisäksi h m ( n ) on optimaalisen ratkaisun tarkka pituus palapelin yksinkertaistettuun versioon , jossa laatat voidaan siirtää paikoilleen. Alkuperäisessä pulmapelissä on rajoitus "yhdessä solussa ei saa olla kahta tai useampaa ruutua", mikä ei ole yksinkertaistetussa versiossa. Ongelmaa , jossa on vähemmän rajoituksia mahdollisille toimille, kutsutaan rentoutuneeksi ongelmaksi  ; relaksoidun ongelman ratkaisun hinta on pätevä heuristiikka alkuperäiselle ongelmalle [1] , koska mikä tahansa ratkaisu alkuperäiseen ongelmaan on myös ratkaisu relaksoituun ongelmaan.

Alatehtävä

Hyväksyttävä heuristiikka voi perustua alkuperäisen ongelman aliongelman ratkaisemisen kustannuksiin . Mikä tahansa ratkaisu pääongelmaan on samanaikaisesti ratkaisu jokaiseen sen osatehtävään [1] .  

"Viititoista" pulman ratkaisemisen ongelman osatehtävä voi olla laattojen 1, 2, 3 ja 4 siirtäminen paikoilleen. Tämän aliongelman ratkaisun hinta on pätevä heuristiikka alkuperäiselle ongelmalle.

Mallitietokannat

Kuviotietokannat [ 1] ovat eräänlainen  kelvollinen heuristiikka, joka perustuu ajatukseen tallentaa ratkaisukustannusten tarkka arvo jokaiselle mahdolliselle aliongelman esiintymälle [1] [6] [12] .

Esimerkki "Fifteen"-palapelin mallista näkyy oikealla olevassa kuvassa: alitehtävän määritelmä sisältää ensimmäisessä sarakkeessa ja ensimmäisessä rivissä olevien seitsemän pelimerkin paikat. Tämän mallin kokoonpanojen määrä on . Jokaisen kokoonpanon osalta tietokanta sisältää vähimmäismäärän siirtoja, jotka vaaditaan tämän kokoonpanon muuttamiseksi kuvassa esitetyn alitehtävän kohdekonfiguraatioksi. Tietokanta on rakennettu käänteisen leveysensin hakumenetelmällä [2] [6] .

Hakualgoritmit

Hae ensimmäisen parhaan haun perusteella

Paras ensin -haku on lähestymistapa, jossa käyttöön otettava solmu valitaan arviointifunktion f ( n ) perusteella .  Alimman pistemäärän saanut solmu valitaan käyttöönottoa varten.

Hae A*

A*-haku  on tunnetuin ensimmäisen parhaan haun tyyppi. Se käyttää arviota f ( n ) halvimman ratkaisupolun kustannuksista solmun n kautta :

f ( n ) = g ( n ) + h ( n ), missä g ( n ) on polun hinta aloitussolmusta solmuun n , h ( n ) on arvio solmusta n tavoitteeseen kulkevan polun hinnasta.

Jos h ( n ) ei koskaan yliarvioi tavoitteen saavuttamisen kustannuksia (eli on edullinen), niin A*-haku on optimaalinen.

IDA*

Algoritmi A* iteratiivisella syvennyksellä A* ( IDA* ) on iteratiivisen syventämisen idean sovellus heuristisen haun yhteydessä.

Epätietoinen iteratiivinen syvennysalgoritmi pysäyttää laajennuksen, kun hakusyvyys d ylittää nykyisen syvyysrajan l . Tietoinen IDA*-algoritmi pysäyttää käyttöönoton, kun nykyisen solmun n läpi kulkevan polun kustannusarvio f ( n ) ylittää nykyisen polun kustannusrajan .

IDA*-algoritmille on ominaista minimaalinen muistin ylimäärä verrattuna A*:han ja suhteellisen pieni (jos heuristiikan valinta onnistuu) käyttöön otettujen solmujen määrä IDDFS:ään verrattuna.

Pseudokoodi

[neljätoista]

solmu nykyinen solmu g kustannus ratkaisun aloittamiseen juuri _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ tarkista funktion seuraajat ( solmu ) solmun käyttöönottotoiminto menettely ida_star ( root , cost (), is_goal (), h ()) sidottu  := h ( juuri ) silmukka t  := haku ( juuri , 0, sidottu ) if t = LÖYDYT sitten palauttaa LÖYTYJEN jos t = ∞ sitten palauttaa NOT_FOUND sidottu  := t end loop end -menettely funktiohaku ( solmu , g , sidottu ) f :  = g + h ( solmu ) jos f > sidottu sitten palauttaa f jos on_tavoite ( solmu ) sitten palauttaa FOUND min :  = ∞ seuraajille ( solmu ) tee t :  = haku succ , g + kustannus ( solmu , succ ), sidottu ) jos t = LÖYTYNÄ niin palauttaa LÖYTYJEN jos t < min sitten min  := t end for return min loppufunktio

MA*

SMA*

SMA  *

RBFS

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 4 5 6 7 8 Stuart Russell, Peter Norvig. Hyväksyttyjen heurististen funktioiden kokoaminen // Tekoäly: moderni lähestymistapa = Artificial Intelligence: A Modern Approach. - 2. painos - M. : Williams, 2006. - S. 170 - 173. - 1408 s. — ISBN 5-8459-0887-6 .
  2. ↑ 1 2 3 Stefan Edelkamp, ​​​​Stefan Schrödl. Heuristinen haku: teoria ja sovellukset. - Morgan Kaufmann Publishers , 2012. - 712 s. — ISBN 978-0-12-372512-7 .
  3. ↑ Alexander Reinfeld. Kahdeksan palapelin täydellinen ratkaisu ja IDA:n* solmutilauksen edut. – 1993.
  4. ↑ Daniel R. Kunkle. 8 palapelin ratkaiseminen vähimmäisliikemäärällä: A*-algoritmin sovellus. – 2001.
  5. ↑ Richard E. Korf. Syvyys-ensin iteratiivinen-syventäminen: Optimaalinen hyväksyttävä puuhaku. – 1985.
  6. ↑ 1 2 3 4 Joseph C. Culberson, Jonathan Schaeffer. Kuviotietokannat. – 1998.
  7. ↑ Richard E. Korf, Peter Schultze. Suuren mittakaavan rinnakkaisleveys - ensimmäinen haku. – 2005.
  8. ↑ Richard E. Korf, Larry A. Taylor. Parhaiden ratkaisujen löytäminen Twenty Four -palapeliin . – 1996.
  9. ↑ 1 2 Richard E. Korf. Viimeaikainen edistyminen hyväksyttyjen heurististen funktioiden suunnittelussa ja analysoinnissa. – 2000.
  10. ↑ Richard E. Korf, Ariel Felner. Disjoint Pattern Database -heuristiikka . – 2002.
  11. ↑ 1 2 Ariel Felner, Richard E. Korf, Sarit Hanan. Additive Pattern Database -heuristiikka . – 2004.
  12. ↑ 1 2 Richard E. Korf. Optimaalisten ratkaisujen löytäminen Rubikin kuutioon kuviotietokantojen avulla. – 1997.
  13. ↑ Richard E. Korf, Ariel Felner. Viimeaikainen kehitys heuristisessa haussa: Hanoin nelitappitornien tapaustutkimus. – 2007.
  14. ↑ Perustuu luentomuistiinpanoihin: IDA* Arkistoitu 22. kesäkuuta 2012 Wayback Machinessa

Kirjallisuus

  • Stefan Edelkamp, ​​Stefan Schrödl. Heuristinen haku: teoria ja sovellukset. - Morgan Kaufmann Publishers , 2012. - 712 s. — ISBN 978-0-12-372512-7 .
  • Stuart Russell, Peter Norvig. Hyväksyttyjen heurististen funktioiden kokoaminen // Tekoäly: moderni lähestymistapa = Artificial Intelligence: A Modern Approach. - 2. painos - M. : Williams, 2006. - S. 170 - 173. - 1408 s. — ISBN 5-8459-0887-6 .

Linkit

 Kaavion hakualgoritmit
Tietämättömät menetelmät
Tietoon perustuvat menetelmät
Pikanäppäimet
Vähintään ulottuva puu
muu