V informatice je B* (vyslovováno „Bee Star“ ) algoritmus pro vyhledávání grafů využívající vyhledávání podle nejlepší první shody , který najde nejlevnější cestu z daného počátečního uzlu do libovolného cílového uzlu (z jednoho nebo více možných cílů) . Poprvé publikoval Hans Berliner v roce 1979 a souvisí s vyhledávacím algoritmem A* .
Algoritmus zachovává intervaly pro uzly stromu , na rozdíl od jednohodnotových odhadů. Listové uzly stromu pak lze prohledávat, dokud jeden z uzlů nejvyšší úrovně nebude mít interval, který je jednoznačně nejlepší .
Listové uzly B*-stromu dostávají skóre, která jsou spíše intervaly než jednotlivá čísla. Předpokládá se, že interval obsahuje skutečnou hodnotu tohoto uzlu. Pokud všechny intervaly připojené k listovým uzlům splňují tuto vlastnost, pak B* určí optimální cestu k cílovému stavu.
Pro zálohování intervalů ve stromu je horní mez předka nastavena na maximální horní mez potomků. Spodní mez předka je nastavena rovna maximu dolní meze potomků. Všimněte si, že tyto hranice mohou poskytnout různé děti.
B* rozšiřuje uzly systematicky za účelem vytvoření rozdělení , ke kterému dochází, když spodní mez přímého potomka kořene není menší než horní mez jakéhokoli jiného přímého potomka kořene. Strom, který vytváří rozkol u kořene, obsahuje důkaz, že nejlepší dítě je přinejmenším tak dobré jako jakékoli jiné dítě.
V praxi nemusí být komplexní vyhledávání dokončeno v rámci praktických omezení zdrojů. Algoritmus je tedy obvykle rozšířen o umělá ukončovací kritéria, jako jsou časová nebo paměťová omezení. Když je dosaženo umělého limitu, je třeba provést heuristický úsudek o tom, jaký tah provést. Strom obvykle poskytuje rozsáhlé důkazy, jako jsou intervaly kořenových uzlů.
B* je proces vyhledávání s první nejlepší shodou , což znamená, že je velmi efektivní při procházení stromem a mnohokrát sestupuje dolů, aby našel list, který se má roztáhnout. Tato část popisuje, jak vybrat uzel pro rozbalení. ( Poznámka : Zda je strom rezidentní v paměti, závisí na celkové efektivitě implementace, včetně toho, jak může být mapován a/nebo manipulován prostřednictvím skutečné nebo virtuální paměti .)
U kořene stromu algoritmus aplikuje jednu ze dvou strategií: dokázat nejlepší a vyvrátit zbytek . Ve strategii prokázat nejlepší algoritmus vybere uzel spojený s nejvyšší horní hranicí. Doufáme, že rozšíření tohoto uzlu zvedne jeho spodní hranici výše než horní mez jakéhokoli jiného uzlu.
Strategie vyvrácení zbytku vybere potomka kořene, který má druhou nejvyšší horní hranici. Doufáme, že rozšířením tohoto uzlu lze snížit horní mez na hodnotu, která je menší než dolní mez nejlepšího potomka.
Volba strategieJe třeba poznamenat, že strategie vyvracení zbytku postrádá smysl, dokud se spodní hranice potomkového uzlu s nejvyšší horní hranicí nestane nejvyšší ze všech dolních hranic.
V původním popisu algoritmu nebyl žádný další návod, jakou strategii zvolit. Existuje několik rozumných alternativ, například rozšíření výběru o menší strom.
Volba strategie na non-root uzlechJakmile je vybrán potomek kořene (pomocí metody dokázat nejlepší nebo vyvrátit zbytek ), algoritmus sestoupí do konečného uzlu a opakovaně vybere potomka, který má nejvyšší horní hranici.
Když je dosaženo listového uzlu, algoritmus vygeneruje všechny následující uzly a přiřadí jim intervaly pomocí funkce skóre. Poté musíte zálohovat intervaly všech uzlů pomocí operace zálohování.
Když jsou možné transpozice, může být vyžadována operace zálohování ke změně hodnot uzlů, které neležely v cestě výběru. V tomto případě algoritmus potřebuje ukazatele od potomků na všechny předky, aby se změny mohly šířit. Všimněte si, že šíření se může zastavit, pokud operace zálohování nezmění interval spojený s uzlem.
Pokud jsou intervaly nesprávné (v tom smyslu, že herně-teoretická hodnota uzlu není obsažena v intervalu), pak B* nemusí být schopen určit správnou cestu. V praxi je však algoritmus poměrně odolný vůči chybám.
V programu Maven je inovace , která zlepšuje spolehlivost B* , když jsou možné chyby hodnocení. Pokud se vyhledávání zastaví kvůli rozdělení, Maven po mírném rozšíření všech intervalů hodnocení znovu spustí vyhledávání. Tato zásada postupně rozšiřuje strom a nakonec vymaže všechny chyby.
Algoritmus B* je aplikován na deterministické hry s nulovým součtem pro dva hráče. Ve skutečnosti je jedinou změnou interpretace toho nejlepšího ve vztahu ke straně pohybující se v tomto uzlu. Měli byste tedy vzít maximum, pokud se vaše strana pohybuje, a minimum, pokud se pohybuje soupeř. Podobně můžete reprezentovat všechny intervaly z hlediska strany, která se má přesunout, a poté invertovat hodnoty během operace zálohování.
Andrew Palai aplikoval B* na šachy . Skóre koncových bodů bylo přiřazeno provedením hledání s nulovým posunem. Neexistuje žádná zpráva o tom, jak dobře si tento systém vedl ve srovnání s alfa-beta prořezávacími vyhledávači běžícími na stejném hardwaru.
Program Maven aplikoval na koncovou hru vyhledávání B* . Skóre koncových bodů bylo přiřazeno pomocí systému heuristického plánování.
Vyhledávací algoritmus B* byl použit pro výpočet optimální strategie ve hře součtů souboru kombinatorických her.
| Algoritmy vyhledávání grafů | ||
|---|---|---|
| Neinformované metody | ||
| Informované metody | ||
| Zkratky | ||
| Minimální kostra | ||
| jiný | ||