Mitä eroja on A *: n ja ahneiden parhaan etsinnän välillä?

Molemmat algoritmit kuuluvat ”paras ensimmäinen haku” -luokkaan. algoritmit, jotka ovat algoritmeja, jotka voivat käyttää sekä toistaiseksi hankittua tietoa etsittäessä hakutilaa, merkitään $ g (n) $ , ja heuristinen funktio, jota merkitään $ h (n) $ , joka arvioi etäisyyden tavoitesolmuun jokaiselle solmulle $ n $ hakutilassa (usein esitetty kaaviona).

Kukin näistä hakualgoritmeista määrittelee ”arviointitoiminnon” kullekin kaavion (tai hakutilan) solmulle $ n $ , jota merkitään $ f (n) $ . Tätä arviointitoimintoa käytetään määrittämään, mikä solmu haun aikana ensin ”laajennetaan”, eli mikä solmu poistetaan ensin ”reunasta” (tai ”rajalta”, tai ”raja”) , jotta ”kävisi” sen lasten luona. Yleensä kategorian ”parhaat ensin” algoritmien ero on arviointitoiminnon $ f (n) $ määritelmässä.

ahne BFS-algoritmi tapauksessa arviointitoiminto on $ f (n) = h (n) $ , eli ahne BFS-algoritmi laajentaa ensin solmua, jonka arvioitu etäisyys tavoitteeseen on pienin. Joten ahne BFS ei käytä ”aikaisempaa tietoa”, ts. $ g (n) $ . Tästä syystä sen merkitys on ”ahne”. Ahne BST-algoritmi on yleensä ole täydellinen , eli on aina olemassa vaara, että siirrytään polkuun, joka ei tuoda tavoitteeseen. Ahneessa BFS-algoritmissa kaikki reunan (tai reunan tai reunan) solmut pidetään muistissa, ja jo laajennettuja solmuja ei tarvitse tallentaa muistiin, ja ne voidaan siksi hylätä. Ahne BFS ei yleensä ole myöskään ei optimaalinen , eli löydetty polku ei välttämättä ole optimaalinen. Yleensä ajan monimutkaisuus on $ \ mathcal {O} (b ^ m) $ , missä $ b $ on (suurin) haarautumistekijä ja $ m $ on hakupuun suurin syvyys. Avaruuden monimutkaisuus on verrannollinen reunan solmujen määrään ja löydetyn polun pituuteen.

A * algoritmi , arviointitoiminto on $ f (n) = g (n) + h (n) $ , missä $ h $ on hyväksyttävä heuristinen funktio . ”Tähti”, jota usein merkitään tähdellä, *, viittaa siihen, että A * käyttää hyväksyttävää heuristista funktiota, mikä tarkoittaa olennaisesti sitä, että A * on optimaalinen , eli se löytää aina optimaalisen polun aloitussolmun ja maalisolmun välillä. A * on myös täydellinen (ellei hakutilassa ole loputtomasti tutkittavia solmuja). Ajan monimutkaisuus on $ \ mathcal {O} (b ^ m) $ . A *: n on kuitenkin pidettävä kaikki solmut muistissa etsinnän aikana, ei vain reunalla olevat, koska A * suorittaa lähinnä ”tyhjentävän haun” (joka on ”informoitu”, siinä mielessä, että se käyttää heuristista toimintoa ).

Yhteenvetona voidaan todeta, että ahne BFS ei ole täydellinen, ei optimaalinen, sen ajan monimutkaisuus on $ \ mathcal {O} (b ^ m) $ ja avaruuden monimutkaisuus, joka voi olla polynomi. A * on täydellinen, optimaalinen, ja sen ajan ja tilan monimutkaisuus on $ \ mathcal {O} (b ^ m) $ . Joten yleensä A * käyttää enemmän muistia kuin ahne BFS. A: sta tulee epäkäytännöllinen, kun hakutila on valtava. A * takaa kuitenkin myös, että löydetty polku aloitussolmun ja maalisolmun välillä on optimaalinen ja että algoritmi lopulta päättyy. Ahne BFS puolestaan käyttää vähemmän muistia, mutta ei tarjoa A *: n optimaalisuutta ja täydellisyyttä. Joten mikä algoritmi on ”paras”, riippuu kontekstista, mutta molemmat ovat ”parhaita” ensimmäisiä hakuja.

Huomaa: käytännössä et saa käyttää mitään näistä algoritmeista: voit esimerkiksi käytä sen sijaan IDA * .

Kommentit

• Kommentit eivät ole tarkoitettu laajennettu keskustelu; tämä keskustelu on siirretty chatiin .

Kirjan tekoäly mukaan: Moderni lähestymistapa (3. painos), erityisesti Stuart Russel ja Peter Norvig, kohta 3.5.1 Ahne paras-ensimmäinen haku (s. 92)

Ahne paras ensin -haku yrittää laajentaa tavoitetta lähinnä olevaa solmua sillä perusteella, että tämä todennäköisesti johtaa ratkaisuun nopeasti. Siten se arvioi solmut käyttämällä vain heuristista toimintoa; eli $ f (n) = h (n) $ .

Tässä Samassa osassa kirjoittajat esittävät esimerkin, joka osoittaa, että ahne parhaan etsinnän haku ei ole optimaalinen eikä täydellinen.

Kohdassa 3.5.2 A * haku: Minimoimalla saman kirjan arvioidut kokonaiskustannukset (s. 93), siinä todetaan

A * haku arvioi solmut yhdistämällä $ g (n) $ , solmun saavuttamisen kustannukset ja $ h (n) $ , solmusta tavoitteeseen pääsyn hinta $$ f (n) = g (n) + h (n). $$

Koska $ g (n) $ antaa polun kustannukset alkusolmusta solmuun $ n $ ja $ h (n) $ on $ n $ tavoitteeseen, meillä on $ f (n) $ = halvimman ratkaisun arvioidut kustannukset $ n $ kautta.

Siten jos yritämme löytää halvimman ratkaisun, järkevä asia kokeilla ensin on solmu, jolla on pienin arvo $ g (n) + h (n) $ . Osoittautuu, että tämä strategia on muutakin kuin kohtuullinen: edellyttäen, että heuristinen funktio $ h (n) $ täyttää tietyt ehdot, A * -haku on sekä täydellinen että optimaalinen. Algoritmi on identtinen yhtenäishintahaun kanssa, paitsi että A * käyttää $ g + h $ $ g $

Sanoitasi ei ole täysin väärin, mutta A * -algoritmista tulee optimaalinen ja täydellinen, jos heuristinen funktio h on hyväksyttävä, mikä tarkoittaa, että tämä funktio ei koskaan yliarvioi tavoitteen saavuttamisen kustannuksia. Tällöin A * -algoritmi on paljon parempi kuin ahne hakualgoritmi.

Kommentit

• rakas, voitko tarkentaa vastaustasi. Anteeksi sanoa, mutta en saanut kantaa.
• @IramShah – TemmanRafk puhuu todisteesta, että A * on sekä optimaalinen että täydellinen. Tällöin kolmion eriarvoisuuden vuoksi osoitetaan, että heuristiikka, joka arvioi jäljellä olevan etäisyyden tavoitteeseen, ei ole yliarvioitu. Jos haluat nähdä täydellisemmän selityksen, katso fi.wikipedia.org/wiki/Adiable_heuri stic