Hae ensimmäisen parhaan osuman perusteella
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. tammikuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .Paras ensin -haku on hakualgoritmi , joka tutkii kaaviota laajentamalla tietyn säännön mukaisesti valittuja lupaavimpia solmuja.
Judea Pearl kuvasi parhaan ensimmäisen haun ottamalla solmupisteeksi jonkin "arvioinnin heuristisen funktion arvon, joka yleensä riippua luonteestavoi [1] [2]
Jotkut kirjoittajat ovat käyttäneet paras ensin -hakua erityisesti kuvaamaan hakuja heuristiikalla, joka mittaa läheisyyttä kohdetilaan, joten polut, joilla on paras heuristinen pistemäärä, otetaan huomioon ensin. Tätä hakutyyppiä kutsutaan ahneeksi paras ensin -hauksi . [2]
Nykyisen parhaan ehdokkaan tehokas valinta haun jatkamiseksi voidaan toteuttaa prioriteettijonon avulla .
A* (A-tähti) -hakualgoritmi on esimerkki optimaalisesta paras ensin -hausta. Paras ensin -algoritmia käytetään usein polunhakuun kombinatorisessa haussa.
Algoritmi
OPEN = [Alkutila] kunnes OPEN on tyhjä toistaa: 1. Poista paras solmu OPENista, kutsutaan sitä N:ksi. 2. Jos N on kohdetila, jäljitä polku takaisin aloitussolmuun (N:n vanhempien merkintöjen kautta) ja palauta polku. 3. Luo luettelo solmun N jälkeläisistä. 4. Arvioi jokainen lapsi, lisää se OPEN-kohtaan ja merkitse N sen vanhemmaksi. suorittaa loppuunTässä versiossa algoritmi ei ole täydellinen , koska sen avulla ei aina ole mahdollista löytää polkua kahden solmun välillä, vaikka yksi olisikin. Esimerkiksi algoritmi "jumiutuu" silmukkaan, jos se osuu umpikujaan - solmuun, jonka lapsi on sen vanhempi. Algoritmi palaa ylätasoonsa, lisää lapsen tynkäsolmun luetteloon OPENja navigoi siihen uudelleen ja niin edelleen.
Seuraava versio laajentaa algoritmia käyttämällä lisäluetteloa CLOSE, joka sisältää kaikki arvioidut solmut, joita ei tarkisteta. Tämä välttää minkä tahansa solmun uudelleenarvioinnin eikä luo äärettömiä silmukoita.
AUKI = [alkutila] SULJE=[] kunnes OPEN on tyhjä toistaa: 1. Poista paras solmu OPENista, kutsutaan sitä N:ksi, lisää se CLOSE-kohtaan. 2. Jos N on kohdetila, jäljitä polku takaisin aloitussolmuun (N:n vanhempien merkintöjen kautta) ja palauta polku. 3. Luo luettelo solmun N jälkeläisistä. 4. Toista jokaiselle lapselle: a. Jos lapsi ei ole SULJE-luettelossa: Arvioi se, lisää se OPEN-kohtaan ja merkitse N sen yläpuolelle. b. Muussa tapauksessa: jos tämä uusi polku on parempi kuin edellinen, muuta merkintä ylätason tiedoksi. suorittaa loppuunTämän pseudokoodin kuvaama algoritmi molemmissa versioissa yksinkertaisesti päättyy, kun polkua ei löydy. Käytännön toteutukset voivat vaatia erityistä käsittelyä tässä tilanteessa.
The Greedy Best-First Search
Ahneen algoritmin käyttö laajentaa vanhempien ensimmäistä lasta. Lasten luomisen jälkeen [3] :
- Jos lapsen heuristinen pistemäärä on parempi kuin vanhemman, lapsi asetetaan jonon etupuolelle (vanhemmat taas heti perässä) ja silmukka käynnistyy uudelleen.
- Muussa tapauksessa lapsi joutuu jonoon (sen heuristisen hinnan määräämään paikkaan). Loput vanhemman perilliset (jos niitä on) arvioidaan.
Muistiinpanot
- ↑ Pearl J. Heuristics: Älykkäät hakustrategiat tietokoneongelmien ratkaisemiseen. - Addison-Wesley, 1984. - S. 48.
- ↑ 1 2 Russell SJ, Norvig P. Tekoäly: moderni lähestymistapa . – 2. - Upper Saddle River, New Jersey: Prentice Hall, 2003. - s. 94-95 (viite 3). — 1132 s. — ISBN 0-13-790395-2 . .
- ↑ Greedy Best-First Search, kun EHC epäonnistuu Arkistoitu 11. kesäkuuta 2010 Wayback Machinessa , Carnegie Mellonissa.
Linkit
- Wikikirjat: Tekoäly: Paras ensimmäinen haku
| Kaavion hakualgoritmit | ||
|---|---|---|
| Tietämättömät menetelmät | ||
| Tietoon perustuvat menetelmät | ||
| Pikanäppäimet | ||
| Vähintään ulottuva puu | ||
| Muut | ||