Az informatikában a B* (ejtsd: "Bee Star" ) egy gráfkereső algoritmus , amely a legjobb első egyezésű keresést használja , és megtalálja a legolcsóbb utat egy adott kezdőcsomóponttól bármely célcsomópontig (egy vagy több lehetséges célpont közül) . Hans Berliner adta ki először 1979-ben, és az A* keresési algoritmushoz kapcsolódik .
Az algoritmus megőrzi az intervallumokat a fa csomópontjaihoz, ellentétben az egyértékű becslésekkel. Ezután a fa levélcsomópontjain addig lehet keresni, amíg az egyik legfelső szintű csomópont egy egyértelműen a legjobb intervallumot nem kapja .
A B*-fa levélcsomópontjai olyan pontszámokat kapnak, amelyek intervallumok, nem pedig egyedi számok. Feltételezzük, hogy az intervallum tartalmazza ennek a csomópontnak a valódi értékét. Ha a levélcsomópontokhoz kapcsolódó összes intervallum kielégíti ezt a tulajdonságot, akkor B* határozza meg a célállapothoz vezető optimális utat.
Az intervallumok mentéséhez egy fában az ős felső határát a leszármazottak maximális felső határára kell beállítani. Az ős alsó határa egyenlő a leszármazottak alsó határának maximumával. Vegye figyelembe, hogy ezeket a korlátokat különböző gyerekek biztosíthatják.
A B* szisztematikusan kiterjeszti a csomópontokat, hogy létrehozzon egy felosztást , amely akkor következik be, ha a gyökér közvetlen leszármazottjának alsó korlátja nem kisebb, mint a gyökér bármely más közvetlen leszármazottjának felső korlátja. A fa, amely a gyökérben hasadást hoz létre, bizonyítékot szolgáltat arra, hogy a legjobb gyerek legalább olyan jó, mint bármely más gyerek.
A gyakorlatban előfordulhat, hogy az összetett keresések nem fejeződnek be a gyakorlati erőforrások korlátai között. Így az algoritmust általában mesterséges befejezési kritériumokkal, például idő- vagy memóriakorlátokkal egészítik ki. Egy mesterséges határ elérésekor heurisztikus döntést kell hozni arról, hogy melyik lépést kell megtenni. Általában a fa kiterjedt bizonyítékokkal szolgál, például gyökércsomópont-intervallumokkal.
A B* az első legjobb keresési folyamat , ami azt jelenti, hogy nagyon hatékonyan járja át a fát, sokszor lemegy, hogy megtalálja a tágítandó levelet. Ez a rész leírja, hogyan válasszon ki bővítendő csomópontot. ( Megjegyzés : Az, hogy egy fa memóriarezidens-e, a megvalósítás általános hatékonyságától függ, beleértve azt is, hogy hogyan lehet leképezni és/vagy manipulálni valós vagy virtuális memórián keresztül .)
A fa gyökerében az algoritmus két stratégia egyikét alkalmazza: a legjobbat bizonyítani , a többit megcáfolni . A legjobb bizonyítás stratégiában az algoritmus kiválasztja a legmagasabb felső korláthoz tartozó csomópontot. Remélhetőleg ennek a csomópontnak a kiterjesztése magasabbra emeli az alsó határt, mint bármely másik csomópont felső határát.
A cáfoló pihenőstratégia a második legmagasabb felső korláttal rendelkező gyökér gyermekét választja ki. Remélhetőleg ennek a csomópontnak a kiterjesztésével a felső korlát olyan értékre csökkenthető, amely kisebb, mint a legjobb gyermek alsó határa.
StratégiaválasztásMegjegyzendő, hogy a többi megcáfolásának stratégiája értelmetlen mindaddig, amíg a legmagasabb felső korláttal rendelkező leszármazott csomópont alsó határa nem lesz a legmagasabb az összes alsó határ között.
Az algoritmus eredeti leírásában nem volt további útmutatás arra vonatkozóan, hogy melyik stratégiát válasszuk. Van néhány ésszerű alternatíva, például a választék bővítése egy kisebb fával.
Stratégiaválasztás nem gyökér csomópontokonMiután kiválasztottuk a gyökér gyermekét (a bebizonyítani a legjobbnak vagy a cáfolni a maradék módszert ), az algoritmus leereszkedik a végső csomópontra, és ismételten kiválasztja a legmagasabb felső korláttal rendelkező gyermeket.
Egy levélcsomópont elérésekor az algoritmus létrehozza az összes következő csomópontot, és a pontszám függvény segítségével intervallumokat rendel hozzájuk. Ezután biztonsági mentést kell készítenie az összes csomópont intervallumáról a biztonsági mentési művelet segítségével.
Ha lehetséges az átültetés, akkor biztonsági mentési műveletre lehet szükség azon csomópontok értékeinek megváltoztatásához, amelyek nem voltak a kiválasztási útvonalon. Ebben az esetben az algoritmusnak mutatókra van szüksége a leszármazottaktól az összes ősig, hogy a változásokat tovább tudják vinni. Vegye figyelembe, hogy a terjedés leállhat, ha a biztonsági mentési művelet nem módosítja a csomóponthoz tartozó intervallumot.
Ha az intervallumok helytelenek (abban az értelemben, hogy a csomópont játékelméleti értéke nem szerepel az intervallumban), akkor előfordulhat, hogy B* nem tudja meghatározni a helyes utat. A gyakorlatban azonban az algoritmus meglehetősen robusztus a hibákra.
A Maven programban van egy újítás, amely javítja a B* megbízhatóságát, ha értékelési hibák lehetségesek. Ha a keresés felosztás miatt leáll, a Maven az összes kiértékelési intervallum enyhe kiterjesztése után újraindítja a keresést. Ez a házirend fokozatosan bővíti a fát, végül töröl minden hibát.
A B* algoritmust két játékos determinisztikus, nulla összegű játékaira alkalmazzuk. Valójában az egyetlen változás a legjobbnak az ebben a csomópontban mozgó oldalhoz viszonyított értelmezése. Így a maximumot kell felvennie, ha az oldala mozog, és a minimumot, ha az ellenfél mozog. Hasonlóképpen minden intervallumot ábrázolhat az áthelyezendő oldal szempontjából, majd a biztonsági mentési művelet során megfordíthatja az értékeket.
Andrew Palai B* -t alkalmazott a sakkra . A végpontpontok hozzárendelése nulla eltolási keresés végrehajtásával történt. Nincs jelentés arról, hogy ez a rendszer milyen jól teljesített az ugyanazon a hardveren futó alfa-béta metsző keresőmotorokhoz képest.
A Maven program a B* keresést alkalmazta a végjátékra . A végpontpontszámokat heurisztikus ütemezési rendszer segítségével rendelték hozzá.
A B* keresőalgoritmust használtuk az optimális stratégia kiszámítására kombinatorikus játékok halmazának összegjátékában.
| Grafikon keresési algoritmusok | ||
|---|---|---|
| Tájékozatlan módszerek | ||
| Tájékozott módszerek | ||
| Parancsikonok | ||
| Minimálisan átívelő fa | ||
| Egyéb | ||