Tietojenkäsittelytieteessä B* (lausutaan "Bee Star" ) on kaaviohakualgoritmi , joka käyttää parhaan ensimmäisen haun hakua , joka löytää edullisimman polun tietystä aloitussolmusta mihin tahansa kohdesolmuun (yhdestä tai useammasta mahdollisesta kohteesta ) . Hans Berliner julkaisi ensimmäisen kerran vuonna 1979, ja se liittyy A*-hakualgoritmiin .
Algoritmi säilyttää puun solmujen aikavälit toisin kuin yksiarvoisissa arvioissa. Puun lehtisolmuja voidaan sitten etsiä, kunnes jollakin ylimmän tason solmulla on väli, joka on selvästi paras .
B*-puun lehtisolmuille annetaan pisteet, jotka ovat pikemminkin intervalleja kuin yksittäisiä lukuja. Välin oletetaan sisältävän tämän solmun todellisen arvon. Jos kaikki lehtien solmuihin liitetyt intervallit täyttävät tämän ominaisuuden, B* määrittää optimaalisen polun kohdetilaan.
Puun aikavälien varmuuskopioimiseksi esivanhemman ylärajaksi asetetaan jälkeläisten enimmäisyläraja. Esivanhemman alaraja asetetaan yhtä suureksi kuin jälkeläisten alaraja. Huomaa, että nämä rajat voivat tarjota eri lapset.
B* laajentaa solmut systemaattisesti luodakseen jaon , joka tapahtuu, kun juuren suoran jälkeläisen alaraja ei ole pienempi kuin minkä tahansa muun suoran jälkeläisen yläraja. Puu, joka luo halkeaman juureen, sisältää todisteen siitä, että paras lapsi on vähintään yhtä hyvä kuin muut lapset.
Käytännössä monimutkaiset haut eivät välttämättä valmistu käytännön resurssirajoitusten puitteissa. Siten algoritmia täydennetään yleensä keinotekoisilla lopetuskriteereillä, kuten aika- tai muistirajoitteilla. Kun keinotekoinen raja saavutetaan, on tehtävä heuristinen arvio siitä, kumpaan siirtoon ryhdytään. Yleensä puu tarjoaa laajaa näyttöä, kuten juurisolmuvälit.
B* on ensiksi paras hakuprosessi , mikä tarkoittaa, että se on erittäin tehokas puun poikki, laskeutuu monta kertaa alas löytääkseen laajentuvan lehden. Tässä osiossa kuvataan, kuinka valita laajennettava solmu. ( Huomautus : Se, onko puu muistissa, riippuu toteutuksen yleisestä tehokkuudesta, mukaan lukien siitä, kuinka se voidaan kartoittaa ja/tai muokata todellisen tai virtuaalisen muistin kautta .)
Puun juuressa algoritmi soveltaa toista kahdesta strategiasta: todista paras ja kumoa loput . Todista parhaaksi -strategiassa algoritmi valitsee korkeimpaan ylärajaan liittyvän solmun. Tämän solmun laajentamisen toivotaan nostavan sen alarajaa korkeammalle kuin minkään muun solmun yläraja.
Kiistämislepostrategia valitsee juuren alitason, jolla on toiseksi korkein yläraja . Toivotaan, että tätä solmua laajentamalla yläraja voidaan pienentää arvoon, joka on pienempi kuin parhaan lapsen alaraja.
Strategian valintaOn huomattava, että lopun kumoamisstrategia on merkityksetön, kunnes korkeimman ylärajan omaavan jälkeläissolmun alaraja tulee korkeimmaksi kaikkien alarajojen joukossa.
Algoritmin alkuperäisessä kuvauksessa ei ollut lisäohjeita siitä, mikä strategia valita. On olemassa joitain järkeviä vaihtoehtoja, kuten valikoiman laajentaminen pienemmällä puulla.
Strategian valinta ei-juurisolmuissaKun juuren lapsi on valittu (käyttäen testaa parhaaksi tai kiistä loput -menetelmää ), algoritmi laskeutuu lopulliseen solmuun ja valitsee toistuvasti lapsen, jolla on korkein yläraja.
Kun lehtisolmu saavutetaan, algoritmi luo kaikki seuraavat solmut ja määrittää niille välit pisteytysfunktiolla. Sitten sinun on varmuuskopioitava kaikkien solmujen aikavälit varmuuskopiointitoiminnolla.
Kun transponoinnit ovat mahdollisia, varmuuskopiointi saattaa olla tarpeen sellaisten solmujen arvojen muuttamiseksi, jotka eivät olleet valintapolulla. Tässä tapauksessa algoritmi tarvitsee osoittimia jälkeläisiltä kaikille esivanhemmille, jotta muutokset voidaan levittää. Huomaa, että eteneminen voi pysähtyä, jos varmuuskopiointi ei muuta solmuun liittyvää aikaväliä.
Jos intervallit ovat vääriä (sillä mielessä, että solmun peliteoreettinen arvo ei sisälly intervalliin), B* ei ehkä pysty määrittämään oikeaa polkua. Käytännössä algoritmi on kuitenkin varsin kestävä virheiden suhteen.
Maven -ohjelmassa on innovaatio, joka parantaa B* :n luotettavuutta, kun arviointivirheet ovat mahdollisia. Jos haku pysähtyy jaon vuoksi, Maven aloittaa haun uudelleen, kun kaikkia arviointivälejä on hieman laajennettu. Tämä käytäntö laajentaa asteittain puuta ja lopulta poistaa kaikki virheet.
Algoritmia B* sovelletaan kahden pelaajan deterministisiin nollasummapeleihin. Itse asiassa ainoa muutos on parhaan tulkinta suhteessa tässä solmussa liikkuvaan sivuun. Siksi sinun tulee ottaa maksimi, jos puolesi liikkuu, ja minimi, jos vastustaja liikkuu. Vastaavasti voit esittää kaikki intervallit siirrettävän puolen perusteella ja kääntää arvot käänteisiksi varmuuskopioinnin aikana.
Andrew Palai käytti B* :ta shakissa . Päätepistepisteet määritettiin suorittamalla nollasiirtymähaku. Ei ole raporttia siitä, kuinka hyvin tämä järjestelmä toimi samalla laitteistolla toimiviin alfa-beta- hakukoneisiin verrattuna.
Maven - ohjelma sovelsi B* -hakua loppupeliin . Päätepistepisteet määritettiin käyttämällä heuristista ajoitusjärjestelmää.
Hakualgoritmia B* käytettiin laskemaan optimaalinen strategia kombinatoristen pelien summapelissä.
| Kaavion hakualgoritmit | ||
|---|---|---|
| Tietämättömät menetelmät | ||
| Tietoon perustuvat menetelmät | ||
| Pikanäppäimet | ||
| Vähintään ulottuva puu | ||
| Muut | ||