B*

Ovo je članak o grafovskom algoritmu. Za varijantu B-stabla pogledajte B*-stablo.

U informatici, B* (izgovara se „B zvezda“) je najbolji-prvi grafni algoritam pretrage koji pronalazi put iz početnog čvora do ciljanog čvora (od jednog ili više mogućih ciljeva). Prva publikacija Hansa Berlinera iz 1979. godine, odnosi se na pretragu A* algoritmom.

Pregled

Algoritam čuva intervale čvorova drveta u odnosu na vrednost tačke. Zatim, lista čvorova drveta se može pretraživati sve dok jedan od čvorova pri vrhu ima interval koji je jasno "najbolji".

Detalji

Pročena intervala evaluacije

Lista čvorova B*-stabla omogućuje procenu intervala pojedinačnih brojeva. Interval sadrži pravu vrednost tog čvora. Ako svi intervali u listi zadovolje ovaj uslov, onda će B* identifikovati optimalan put do cilja.

Proces izrade

Da bismo napravili rezervnu kopiju intervala u okviru stabla, roditelj je gornja granica postavljena na maksimalnu gornju granicu dece. Roditeljska donja granica postavljena je na maksimalnu donju granicu dece. Različita deca možda zadovoljavaju ove granice.

Završetak pretrage

B* sistemski širi čvorove u cilju stvaranja "odvajanja", i to se dešava kada donje granice direktnog deteta korena su barem toliko velike kao gornja granica bilo kog drugog direktnog deteta korena. Drvo koje pravi odvajanje u osnovi sadrži dokaz da je najbolje dete barem toliko dobro kao svako drugo dete.

U praksi, složene pretrage ne mogu biti prekinute unutar granica. Dakle, algoritam je obično pojačan kriterijumom ograničenja memorije i vremena. Kada udari veštačko ograničenje, onda po heuristici morate izabrati njihovo kretanje. Normalno, drvo će se snadbevati sa velikim dokazima, kao i intervalima od korena čvorova.

Proširenost

B* je prvi najbolji proces, što znači da je celo drvo sačuvano u memoriji, a više se puta pravi i lista za proširenje. Ovaj odeljak opisuje kako da izaberete čvor za proširenje. U korenu stabla, algoritam primenjuje jednu od dve strategije, pod nazivom najbolje-dokazuje i kako-primeniti. U dokazu najbolje strategije, algoritam bira čvor povezan sa najvišom gornjom granicom. Čvor se podiže do gornje granice. Opovrgnutom strategijom bira se dete koren koji ima drugu najvišu gornju granicu. Proširenjem čvora bi mogla da se smanji granica za manje od donje granice od najbolje dece.

Strategija izbora

Primenom opovrgnute strategije se dolazi do donje granice čvora deteta koji ima najvišu gornju granicu među svim nižim granicama. Originalni algoritam ne daje dodatne smernice za strategiju izbora. Postoji nekoliko razumnih alternativa, kao što je proširenje izbora koje ima manje drvo.

Strategija izbora na nekorenskim čvorovima

Čim je izabran koren deteta (korišćenjem najboljeg dokaza ili opovrgnutom strategijom) onda se algoritam spušta na list i tako više puta bira dete koje ima najveću gornju granicu. Kada se dostigne čvor, algoritam generiše sve čvorove naslednika i dodeljuje im razmake za korišćenje funkcije evaluacije. Tada intervali svih čvorova moraju biti sačuvani pomoću operacije pravljenja rezervne kopije. Kada se omogući transpozicija, onda bi rezervne opracije trebalo da promene vrednosti čvorova koji ne leže na putu izbora. U ovom slučaju, algoritam treba pokazivač od dece ka svim roditeljima, tako da se promene mogu propagirati. Kada širenje prestane, operacija ne menja interval čvora.

Robusnost

Ako su intervali netačni (u smislu da teorijska vrednost intervala nije sadržana u intervalu), tada B* neće identifikovati ispravnu putanju. Međutim, algoritam je prilično robusan u praksi.

Maven (Scrabble) program ima novinu koja poboljšava robusnost B* kada procene da su moguće greške. Ako se pretraga prekine zbog odvajanja, onda Maven restartuje traganje širenja svih evaluacija malog iznosa. Ova politika postepeno širi drvo, eventualnim brisanjem svih grešaka.

Proširenje na igru sa dva igrača

B* algoritam se primenjuje na dva igrača determinističkih nultih iznosa igara. U stvari, jedina promena je da protumači "najbolje" u odnosu na stranu kojom ide u tom čvoru. Tako će uzeti maksimum, ako se Vaša strana kreće, a minimum za suprotno kretanje. Ekvivalentno, možete predstaviti sve intervale iz perspektive kretanja sa strane, a zatim negiranje vrednosti tokom kopije operacije.

Primene

Endru Palai primenjuje B* u šahu. Krajnje tačke procene su dodeljene od obavljenog nultog pokreta pretrage. Nema izveštaja o tome koliko se ovaj sistem dobro izvršava u odnosu na alfa-beta orezivanje pretrage koje rade na istom hardveru. Maven program primenjuje B* pretragu na završnicama. Krajnja tačka procene je dodeljena koristeći heuristički sistem planiranja. Ovaj program je uspeo, uspostavljanjem zlatnog standarda za analizu završetka igara. B* algoritam za pretragu se koristi za izračunavanje optimalne strategije.

Vidi još

Literatura

Berliner, Hans (1979). „The B* Tree Search Algorithm. A Best-First Proof Procedure.”. Artificial Intelligence. 12 (1): 23—40. doi:10.1016/0004-3702(79)90003-1.
Russell, S. J.; Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall. стр. 188. ISBN 978-0-13-790395-5.
Sheppard, Brian (2002). „World-championship-caliber Scrabble.”. Artificial Intelligence. 134 (1-2): 241—275. doi:10.1016/S0004-3702(01)00166-7.