Б*

Ово је чланак о графовском алгоритму. За варијанту Б-стабла погледајте Б*-стабло.

У информатици, Б* (изговара се „Б звезда“) је најбољи-први графни алгоритам претраге који проналази пут из почетног чвора до циљаног чвора (од једног или више могућих циљева). Прва публикација Ханса Берлинера из 1979. године, односи се на претрагу А* алгоритмом.

Преглед

Алгоритам чува интервале чворова дрвета у односу на вредност тачке. Затим, листа чворова дрвета се може претраживати све док један од чворова при врху има интервал који је јасно "најбољи".

Детаљи

Прочена интервала евалуације

Листа чворова Б*-стабла омогућује процену интервала појединачних бројева. Интервал садржи праву вредност тог чвора. Ако сви интервали у листи задовоље овај услов, онда ће Б* идентификовати оптималан пут до циља.

Процес израде

Да бисмо направили резервну копију интервала у оквиру стабла, родитељ је горња граница постављена на максималну горњу границу деце. Родитељска доња граница постављена је на максималну доњу границу деце. Различита деца можда задовољавају ове границе.

Завршетак претраге

Б* системски шири чворове у циљу стварања "одвајања", и то се дешава када доње границе директног детета корена су барем толико велике као горња граница било ког другог директног детета корена. Дрво које прави одвајање у основи садржи доказ да је најбоље дете барем толико добро као свако друго дете.

У пракси, сложене претраге не могу бити прекинуте унутар граница. Дакле, алгоритам је обично појачан критеријумом ограничења меморије и времена. Када удари вештачко ограничење, онда по хеуристици морате изабрати њихово кретање. Нормално, дрво ће се снадбевати са великим доказима, као и интервалима од корена чворова.

Проширеност

Б* је први најбољи процес, што значи да је цело дрво сачувано у меморији, а више се пута прави и листа за проширење. Овај одељак описује како да изаберете чвор за проширење. У корену стабла, алгоритам примењује једну од две стратегије, под називом најбоље-доказује и како-применити. У доказу најбоље стратегије, алгоритам бира чвор повезан са највишом горњом границом. Чвор се подиже до горње границе. Оповргнутом стратегијом бира се дете корен који има другу највишу горњу границу. Проширењем чвора би могла да се смањи граница за мање од доње границе од најбоље деце.

Стратегија избора

Применом оповргнуте стратегије се долази до доње границе чвора детета који има највишу горњу границу међу свим нижим границама. Оригинални алгоритам не даје додатне смернице за стратегију избора. Постоји неколико разумних алтернатива, као што је проширење избора које има мање дрво.

Стратегија избора на некоренским чворовима

Чим је изабран корен детета (коришћењем најбољег доказа или оповргнутом стратегијом) онда се алгоритам спушта на лист и тако више пута бира дете које има највећу горњу границу. Када се достигне чвор, алгоритам генерише све чворове наследника и додељује им размаке за коришћење функције евалуације. Тада интервали свих чворова морају бити сачувани помоћу операције прављења резервне копије. Када се омогући транспозиција, онда би резервне опрације требало да промене вредности чворова који не леже на путу избора. У овом случају, алгоритам треба показивач од деце ка свим родитељима, тако да се промене могу пропагирати. Када ширење престане, операција не мења интервал чвора.

Робусност

Ако су интервали нетачни (у смислу да теоријска вредност интервала није садржана у интервалу), тада Б* неће идентификовати исправну путању. Међутим, алгоритам је прилично робусан у пракси.

Мавен (Сцраббле) програм има новину која побољшава робусност Б* када процене да су могуће грешке. Ако се претрага прекине због одвајања, онда Мавен рестартује трагање ширења свих евалуација малог износа. Ова политика постепено шири дрво, евентуалним брисањем свих грешака.

Проширење на игру са два играча

Б* алгоритам се примењује на два играча детерминистичких нултих износа игара. У ствари, једина промена је да протумачи "најбоље" у односу на страну којом иде у том чвору. Тако ће узети максимум, ако се Ваша страна креће, а минимум за супротно кретање. Еквивалентно, можете представити све интервале из перспективе кретања са стране, а затим негирање вредности током копије операције.

Примене

Ендру Палаи примењује Б* у шаху. Крајње тачке процене су додељене од обављеног нултог покрета претраге. Нема извештаја о томе колико се овај систем добро извршава у односу на алфа-бета орезивање претраге које раде на истом хардверу. Мавен програм примењује Б* претрагу на завршницама. Крајња тачка процене је додељена користећи хеуристички систем планирања. Овај програм је успео, успостављањем златног стандарда за анализу завршетка игара. Б* алгоритам за претрагу се користи за израчунавање оптималне стратегије.

Види још

Литература

Берлинер, Ханс (1979). „Тхе Б* Трее Сеарцх Алгоритхм. А Бест-Фирст Прооф Процедуре.”. Артифициал Интеллигенце. 12 (1): 23—40. дои:10.1016/0004-3702(79)90003-1.
Русселл, С. Ј.; Норвиг, П. (2003). Артифициал Интеллигенце: А Модерн Аппроацх. Уппер Саддле Ривер, Н.Ј.: Прентице Халл. стр. 188. ИСБН 978-0-13-790395-5.
Схеппард, Бриан (2002). „Wорлд-цхампионсхип-цалибер Сцраббле.”. Артифициал Интеллигенце. 134 (1-2): 241—275. дои:10.1016/С0004-3702(01)00166-7.