B* algoritmus
Az informatikában a B* (B csillagnak ejtve) egyike a best-first gráfkereső algoritmusoknak, amely megtalálja a legkisebb költségű utat az adott kezdő csúcsból bármelyik célcsúcsba (egy vagy több lehetséges célból kiválasztva azt). Ezt a módszert először Hans Berliner publikálta 1979-ben. A B* algoritmus kapcsolódik az A* algoritmushoz.
Összefoglalás[szerkesztés]
Az egyetlen becsült értéket használó algoritmusokkal szemben a B* algoritmusa intervallumokat tárol a fa csomópontjai számára. Ezáltal a fa levél csomópontjai kereshetőek egészen addig, amíg az egyik felsőbb szintű csomópont nem rendelkezik az egyértelműen „legjobb” intervallummal.
Részletek[szerkesztés]
Inkább intervallumértékelések, mint becslések[szerkesztés]
A B*-fa levél csomópontjai nem egyetlen számként, hanem intervallumként kerülnek kiértékelésre. Az intervallumnak tartalmaznia kell a csomópont valódi értékét. Ha minden a levél csomóponthoz kapcsolódó intervallum megfelel ennek a kritériumnak, akkor a B* meghatározza az optimális utat a célállapothoz.
Biztonsági mentési folyamat[szerkesztés]
Hogy biztonsági másolatot készíthessünk a fában található intervallumokról, az ős/szülő felső korlátját a gyermekek maximális felső korlátjára kell állítani. Az ős/szülő alsó korlátját pedig a gyerekek alsó korlátjának a maximumára kell állítani. Figyelembe kell venni, hogy ezeket a korlátokat különböző gyermekek szolgáltathatják.
A keresés megszüntetése[szerkesztés]
A B* szisztematikusan kiterjeszti a csomópontokat annak érdekében, hogy szétválaszthassa azokat, abban az esetben, ha a gyökér valamelyik közvetlen gyermekének az alsó határa legalább olyan nagy, mint a gyökér bármelyik másik közvetlen gyermekének a felső határa. Az a fa, amelyik elválasztást csinál a gyökérnél, bizonyítékul szolgál arra, hogy a legjobb gyerek legalább olyan jó, mint bármelyik másik.
A gyakorlatban azonban az összetett keresések nem feltétlen fognak a gyakorlati erőforrások határain belül véget érni. Tehát az algoritmus általában rendelkezik valamilyen beépített korláttal (ez lehet például idő- vagy memórialimit), amelyet ha elér, akkor mindenképpen leáll. Amikor az algoritmus elér egy ilyen mesterséges korlátot, heurisztikus döntést kell hoznia, hogy melyik lépést választja. Alapesetben a fa kiterjedt bizonyítékokkal bizonyítékokkal szolgál, mint például a gyökér csomópont intervallumai.
Kiterjesztés[szerkesztés]
A fabejárásra a B* a leghatékonyabb eljárás. Fokozatosan halad egyre lentebb, hogy találjon olyan levelet, amit ki tud terjeszteni. Ebben a szakaszban arról lesz szó, hogyan kell kiválasztani a kiterjesztendő csomópontot. (Megjegyzés: a végrehajtás hatékonysága, valamint hogy feltérképezhető és/vagy kezelhető valós vagy virtuális memória segítségével, független attól, hogy a fa memóriarezidens vagy sem.)
A fa gyökerénél az algoritmus a prove-best vagy a disprove-rest stratégiát alkalmazza. A prove-best stratégiánál az algoritmus azt a csúcsot választja ki, amelyiknek a legmagasabb a felső korlátja, abban a reményben, hogy annak a kiterjesztésével a csúcs alsó korlátja magasabb lesz az összes többi csomópont felső korlátjánál.
A disprove-rest stratégia a gyökér azon gyerekét választja ki, amelyik a második legnagyobb felső korláttal rendelkezik, abban a reményben, hogy azt kiterjesztve a felső korlátját képes lesz kisebbé redukálni a legjobb gyerek alsó korlátjánál.
Stratégia kiválasztása[szerkesztés]
Azt is figyelembe kell venni, hogy a disprove-rest stratégia alkalmazása értelmetlen, amíg a legalacsonyabb korláttal rendelkező gyerek csomópontjának a felső korlátja magasabb, mint a többi alsó korlátja.
Az eredeti algoritmusleírásban nem szerepel további instrukció azt illetően, hogy melyik stratégiát válasszuk. Számos észszerű alternatíva létezik, mint például kisebb méretű fa kiválasztása és annak kiterjesztése.
Stratégia kiválasztása a nemgyökér csomópontokon[szerkesztés]
Amint a gyökér egyik gyereke kiválasztásra került (a prove-best vagy a disprove-rest stratégia segítségével), az algoritmus kiválasztja a következő legmagasabb korláttal rendelkező gyereket.
Amikor az algoritmus elér egy levél csomópontot, legenerálja az utód csomópontokat, és az értékelési funkció segítségével hozzájuk rendeli az intervallumokat. Ezek után az összes csomópont intervallumáról biztonsági mentést kell készíteni.
Áthelyezés esetén a biztonsági mentési folyamatnak lehet, hogy meg kell változtatnia azon csomópontok értékeit, amelyek nem a kiválasztott útvonalon fekszenek. Ebben az esetben az algoritmusnak szüksége van mutatókra a gyermekektől az összes szülőig, hogy a megváltoztatott értékek is öröklődjenek, mentésre kerüljenek. Azonban azt is figyelembe kell venni, hogy a terjesztés leállhat, ha a biztonsági mentési művelet nem változtatja meg a csomóponthoz társított intervallumot.
Robusztusság[szerkesztés]
Ha az intervallumok nem helyesek (abban az értelemben, hogy a csomópontok játékteoretikus értékét nem tartalmazza az intervallum), akkor a B* nem biztos, hogy meg tudja találni a megfelelő útvonalat. Azonban az algoritmus a gyakorlatban meglehetősen robusztus.
A Maven (Scrabble) programnak van egy fejlesztése, amely javítja a B* robusztusságát a felmerülő értékelési hibákkal szemben. Amikor a keresés leáll az elválasztás miatt, akkor a Maven újraindítja a keresést, miután kibővítette az intervallumokat. Ez az eljárás a fa fokozatos kibővítésével végül törli az összes hibát.
Bővítés kétjátékos játékokra[szerkesztés]
A B* algoritmus alkalmazható a kétjátékos determinisztikus nulla összegű játékokra is. Valójában az egyetlen változás az, hogy a „legjobbat” a csomópontban a mozgó oldal szempontjából határozzuk meg. Szóval, akkor kapjuk meg a maximum értéket, hogyha a mi oldalunk van mozgásban, és a minimumot, ha az ellenfélé. Ezzel együtt meghatározhatjuk az összes intervallumot a mozgatandó oldal perspektívájából, és a mentési folyamat során érvényteleníthetjük azokat.
Alkalmazások[szerkesztés]
Andrew Palay alkalmazta a B*-ot először a sakkban úgy, hogy null-move kereséseket rendelt a végpontok kiértékeléséhez. Arról nincsenek adatok, hogy ez mennyire működik jól az alfa-béta vágásos keresést alkalmazó rendszerekhez képest.
A Maven (Scrabble) program a végjátékokra alkalmazza a B* keresést, a végpontok kiértékeléséhez pedig egy heurisztikus tervező rendszert rendelt.
A B* keresőalgoritmust arra használják, hogy meghatározzák az optimális stratégiát a különböző kombinatorikus játékok menetében.
Irodalom[szerkesztés]
- Berliner (1979). „The B* Tree Search Algorithm. A Best-First Proof Procedure.”. Artificial Intelligence 12 (1), 23–40. o. [2017. szeptember 27-i dátummal az eredetiből archiválva]. DOI:10.1016/0004-3702(79)90003-1. (Hozzáférés: 2020. május 23.)
- Russell, S. J.. Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall, 188. o. (2003). ISBN 0-13-790395-2 Russell, S. J.. Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall, 188. o. (2003). ISBN 0-13-790395-2 Russell, S. J.. Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall, 188. o. (2003). ISBN 0-13-790395-2
- Sheppard (2002). „World-championship-caliber Scrabble.”. Artificial Intelligence 134 (1-2), 241–275. o. DOI:10.1016/S0004-3702(01)00166-7.
Fordítás[szerkesztés]
Ez a szócikk részben vagy egészben a B* című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.