A*

Hae A * (lausutaan "A tähti" tai "A tähti", englanniksi  A star ) - tietojenkäsittelytieteessä ja matematiikassa hakualgoritmi ensimmäisen parhaan vastaavuuden löytämiseksi kaaviossa , joka löytää reitin halvimmalla hinnalla yhdestä kärjestä ( ensimmäinen) toiselle (kohde, lopullinen).

Huippupisteiden kulkemisjärjestys määräytyy etäisyyden + kustannusheuristisen funktion avulla (yleisesti merkitty f(x) ). Tämä funktio on kahden muun summa: kustannusfunktio, joka syntyy tarkasteltavan kärjen ( x ) saavuttamisesta alkuperäisestä (yleensä merkitty g(x) ja voi olla joko heuristinen tai ei) ja etäisyyden heuristisen arvioinnin funktio. tarkasteltavasta kärjestä viimeiseen (merkitty h (x) ).

Funktion h(x) on oltava kelvollinen heuristinen arvio , eli se ei saa yliarvioida etäisyyksiä kohdepisteeseen. Esimerkiksi reititysongelmassa h(x) voisi olla etäisyys kohteeseen suoraviivaisesti, koska se on fyysisesti pienin mahdollinen etäisyys kahden pisteen välillä.

Tämän algoritmin kuvasivat ensimmäisen kerran vuonna 1968 Peter Hart , Nils Nilsson ja Bertram Raphael . Se oli lähinnä Dijkstran vuonna 1959 luodun algoritmin laajennus . Uusi algoritmi saavutti paremman suorituskyvyn (ajassa) heuristiikkaa käyttämällä. Heidän työssään sitä kutsutaan "algoritmiksi A". Mutta koska se laskee parhaan reitin tietylle heuristiikalle, se on nimetty A*.

Yleistys sille on kaksisuuntainen heuristinen hakualgoritmi .

Historia

Vuonna 1964 Nils Nilsson keksi heuristisen lähestymistavan nopeuttaakseen Dijkstran algoritmia . Tämän algoritmin nimi oli A1 . Vuonna 1967 Bertram Raphael teki merkittäviä parannuksia tähän algoritmiin, mutta hän ei saavuttanut optimaalisuutta. Hän antoi tälle algoritmille nimen A2 . Sitten vuonna 1968 Peter E. Hart esitti argumentteja, jotka väittivät, että A2 oli optimaalinen käytettäessä peräkkäistä heuristiikkaa vain pienin muutoksin. Hänen todistuksensa algoritmista sisälsi myös osan, joka osoitti, että uusi algoritmi A2 oli mahdollisesti paras algoritmi olosuhteisiin nähden. Niinpä hän merkitsi uuden algoritmin syntaksissa tähdellä, se alkaa A: lla ja sisältää kaikki mahdolliset versionumerot.

Algoritmin kuvaus

A* iteroi kaikkia polkuja, jotka johtavat alkupisteestä loppupisteeseen, kunnes se löytää pienimmän. Kuten kaikki tietoiset hakualgoritmit , se tarkastelee ensin reitit, jotka "näyttävät" johtavan tavoitteeseen. Se eroaa ahneesta algoritmista , joka on myös ensimmäisen parhaan osuman hakualgoritmi, siinä, että se ottaa kärkeä valittaessa huomioon muun muassa koko siihen kuljetun polun. Komponentti g(x)  on polun hinta alkupisteestä, ei edellisestä, kuten ahneessa algoritmissa.

Työn alussa käydään läpi alkuperäisen viereiset solmut; valitaan se, jolla on pienin arvo f(x) , jonka jälkeen tätä solmua laajennetaan. Jokaisessa vaiheessa algoritmi toimii joukolla polkuja lähtöpisteestä kaikkiin vielä tutkimattomiin graafin (lehti) kärkipisteisiin - tiettyjen ratkaisujen joukkoon -, joka asetetaan prioriteettijonoon . Polun prioriteetti määräytyy arvolla f(x) = g(x) + h(x) . Algoritmi jatkaa työtään, kunnes kohdepisteen arvo f(x) on pienempi kuin mikä tahansa jonon arvo tai kunnes koko puu on skannattu. Ratkaisujoukosta valitaan edullisin ratkaisu.

Mitä pienempi heuristinen h(x) , sitä korkeampi prioriteetti on, joten puiden lajittelua voidaan käyttää jonon toteuttamiseen .

Katselupisteiden joukko on tallennettu closedhakemistoon ja huomioitavat polut ovat prioriteettijonossa open. Polun prioriteetti lasketaan käyttämällä f(x) -funktiota prioriteettijonon toteutuksen sisällä.

Pseudokoodi:

funktio A* ( aloitus, tavoite, f ) % joukko pisteitä jo ohitettu var suljettu : = tyhjä joukko % joukko tiettyjä ratkaisuja var open := make_queue ( f ) enqueue ( avoin , polku ( alku )) auki ollessa ei ole tyhjä var p := remove_first ( avaa ) var x := p : n viimeinen solmu jos x suljettu _ jatkaa jos x = tavoite paluu p lisää ( suljettu , x ) % lisää vierekkäisiä pisteitä foreach y seuraajissa ( x ) _ enqueue ( open , add_to_path ( p , y )) palautus epäonnistui

Jo ohitettujen kärkien joukko voidaan jättää pois (tässä tapauksessa algoritmi muuttuu päätöspuuhakuksi), jos ratkaisun tiedetään olevan olemassa tai se successorsvoi katkaista syklejä .

Esimerkki

Esimerkki A*-algoritmista toiminnassa, jossa solmut ovat teiden yhdistämiä kaupunkeja ja H(x) on lyhin etäisyys kohdepisteeseen:

Avain: vihreä - aloitus, sininen - kohde, oranssi - vierailtu solmut.

Ominaisuudet

Kuten Breadth First Search , A* on täydellinen siinä mielessä, että se löytää aina ratkaisun, jos sellainen on olemassa.

Jos heuristinen funktio h on sallittu, eli se ei koskaan yliarvioi todellista tavoitteen saavuttamisen minimikustannusta, niin A* on itsessään sallittu (tai optimaalinen ), myös sillä edellytyksellä, että emme katkaise kuljettuja kärkipisteitä. Jos teemme näin, niin algoritmin optimaalisuuden kannalta vaaditaan, että h(x) on myös monotoninen tai peräkkäinen heuristiikka. Monotonisuusominaisuus tarkoittaa, että jos on polkuja A-B-C ja A-C (ei välttämättä läpi B ), niin polun A - C kustannusestimaatin tulee olla pienempi tai yhtä suuri kuin polkujen A-B ja B-C estimaattien summa . (Monotonisuus tunnetaan myös kolmion epäyhtälönä : kolmion yksi sivu ei voi olla pidempi kuin kahden muun sivun summa.) Matemaattisesti kaikilla poluilla x y (jossa y on x :  n lapsi ) on:

A* on myös optimaalisesti tehokas tietylle heuristiselle h :lle . Tämä tarkoittaa, että mikä tahansa muu algoritmi tutkii vähintään yhtä monta solmua kuin A* (ellei ole olemassa useita tiettyjä ratkaisuja, joilla on sama heuristinen täsmälleen optimaalisen polun hinta).

Vaikka A* on optimaalinen "satunnaisesti" annetuille kaavioille, ei ole takeita siitä, että se tekisi parempaa työtä kuin yksinkertaisemmat mutta toimialuetietoisemmat algoritmit. Esimerkiksi tietyssä labyrintissa saatat joutua ensin menemään uloskäynnin suuntaan ja vasta sitten kääntymään takaisin . Tässä tapauksessa niiden huippujen kysely, jotka ovat lähempänä lähtöä (suorassa linjassa), on ajanhukkaa.

Erikoistilaisuudet

Yleisesti ottaen syvyys - ensimmäinen haku ja leveys ensin -haku ovat kaksi A*-algoritmin erikoistapausta. Otetaan syvyysensimmäistä hakua varten globaali muuttujalaskuri C ja alustetaan se jollain suurella arvolla. Joka kerta kun laajennamme kärkeä, annamme laskurin arvon viereisille pisteille vähentäen sitä yhdellä jokaisen määrityksen jälkeen. Eli mitä aikaisemmin kärkipiste avataan, sitä suuremman h(x) :n arvon se saa, mikä tarkoittaa, että sitä tarkastellaan viimeisenä. Jos laitamme h(x) = 0 kaikille pisteille, niin saadaan toinen erikoistapaus - Dijkstran algoritmi .

Toteutustiedot

On olemassa useita toteutusominaisuuksia ja tekniikoita, jotka voivat vaikuttaa merkittävästi algoritmin tehokkuuteen. Ensimmäinen asia, johon ei ole haittaa kiinnittää huomiota, on se, kuinka prioriteettijono käsittelee kärkien välisiä yhteyksiä. Jos siihen lisätään pisteitä siten, että jono toimii LIFO -periaatteen mukaan, niin saman arvosanan omaavien kärkien tapauksessa A* "menee" syvyyteen. Jos kuitenkin pisteitä lisättäessä toteutetaan FIFO -periaate , niin samoilla estimaateilla oleville pisteille algoritmi päinvastoin toteuttaa leveyshaun. Joissakin tapauksissa tämä seikka voi vaikuttaa merkittävästi suorituskykyyn .

Jos työn lopussa algoritmilta vaaditaan reitti, tallennetaan yleensä linkki pääsolmuun jokaisen kärjen mukana. Näiden linkkien avulla voit rekonstruoida optimaalisen reitin. Jos näin on, niin on tärkeää, että sama kärkipiste ei esiinny kahdesti jonossa (samalla kun sillä on oma reitti ja oma kustannusarvio). Yleensä tämän ongelman ratkaisemiseksi he tarkistavat kärkeä lisättäessä, onko jonossa sitä koskeva merkintä. Jos on, tietue päivitetään niin, että se vastaa näiden kahden vähimmäiskustannuksia. Lajittelupuun kärjen löytäminen useilla vakioalgoritmeilla vie O(n) aikaa. Jos parannat puuta hash-taulukolla , voit lyhentää tätä aikaa.

Miksi A* on kelvollinen ja optimaalinen

Algoritmi A* on sekä hyväksyttävä että kulkee minimimäärän kärkejä, koska se toimii "optimistisen" arvion kanssa kärjen läpi kulkevasta polusta. Optimistinen siinä mielessä, että jos se kulkee tämän kärjen läpi, algoritmilla "on mahdollisuus", että tuloksen todellinen hinta on yhtä suuri kuin tämä arvio, mutta ei pienempi. Mutta koska A* on tietoinen algoritmi, tällainen yhtäläisyys voi hyvinkin olla mahdollinen.

Kun A* suorittaa haun, se on määritelmän mukaan löytänyt polun, jonka todellinen hinta on pienempi kuin minkä tahansa avoimen solmun läpi kulkevan polun arvioitu hinta. Mutta koska nämä arviot ovat optimistisia, vastaavat solmut voidaan epäilemättä hylätä. Toisin sanoen A* ei koskaan menetä mahdollisuutta minimoida polun pituus ja on siksi laillinen.

Oletetaan nyt, että jokin algoritmi B palautti tuloksena polun, jonka pituus on suurempi kuin jonkin kärjen läpi kulkevan polun kustannusarvio. Heuristisen tiedon perusteella algoritmin B tapauksessa ei voida sulkea pois sitä mahdollisuutta, että tällä polulla oli lyhyempi todellinen pituus kuin tuloksella. Vastaavasti, vaikka algoritmi B on katsonut vähemmän pisteitä kuin A*, se ei ole kelvollinen. Joten A* kulkee vähiten graafin kärkipisteitä kelvollisista algoritmeista käyttäen samaa tarkkaa (tai vähemmän tarkkaa) heuristia.

Vaikeusaste

A*-algoritmin aikamonimutkaisuus riippuu heuristiikasta. Pahimmassa tapauksessa algoritmin tutkimien kärkien määrä kasvaa eksponentiaalisesti verrattuna optimaalisen polun pituuteen, mutta monimutkaisuus muuttuu polynomiseksi , kun heuristinen ehto täyttää seuraavan ehdon:

;

missä h* on optimaalinen heuristinen, eli tarkka arvio etäisyydestä x:stä kohteeseen. Toisin sanoen virheen h(x) ei pitäisi kasvaa nopeammin kuin optimaalisen heuristiikan logaritmi .

Mutta vielä suurempi ongelma kuin aika monimutkaisuus on algoritmin kuluttamat muistiresurssit . Pahimmassa tapauksessa sen on muistettava eksponentiaalinen määrä solmuja. Tämän torjumiseksi algoritmista on ehdotettu useita muunnelmia, kuten A*-algoritmi iteratiivisella syvennyksellä (iteratiivinen syvennys A*, IDA*), A* muistirajoitteisella A*, MA*, yksinkertaistettu MA* (yksinkertaistettu MA ) *, SMA*) ja rekursiivinen paras ensin -haku (RBFS).

Kirjallisuus

  • Laurier J.-L. Tekoälyjärjestelmät / Per. alkaen fr. ja toim. V. L. Stefanyuk. - M .: Mir, 1991. - S. 238-244. - 20 000 kappaletta. kopio.  — ISBN 5-03-001408-X .
  • Russell S.J., Norvig, P. Tekoäly: moderni lähestymistapa = Artificial Intelligence: A Modern Approach / Per. englannista. ja toim. K. A. Ptitsyna. - 2. painos - M. : Williams, 2006. - S. 157-162. - 3000 kappaletta. kopio.  — ISBN 5-8459-0887-6 .
  • Nilson N. Tekoäly: Methods for Finding Solutions = Ongelmanratkaisumenetelmät tekoälyssä / Per. englannista. V. L. Stefanyuk; toim. S. V. Fomina. - M . : Mir, 1973. - S. 70 - 80.
  • Dechter, R., Pearl, J. Generalized best-first -hakustrategiat ja A*:n optimaalisuus  // Journal of the ACM. - 1985. - T. 32 , nro 3 . - S. 505 - 536 .
  • Hart PE, Nilsson, NJ, Raphael, B. Muodollinen perusta vähimmäiskustannuspolkujen heuristiselle määrittämiselle // IEEE Transactions on Systems Science and Cybernetics SSC4. - 1968. - Nro 2 . - S. 100 - 107 .
  • Hart PE, Nilsson, NJ, Raphael, B. Korjaus "Muodollinen perusta vähimmäiskustannuspolkujen heuristiselle määrittämiselle" // SIGART-uutiskirje. - 1972. - T. 37 . - S. 28 - 29 .
  • Pearl J. Heuristics: Älykkäät hakustrategiat tietokoneongelmien ratkaisemiseen. - Addison-Wesley, 1984. - ISBN 0-201-05594-5 .

Linkit

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