B*

Inom datavetenskap är B* (uttalas "B-stjärna") en grafsökningsalgoritm för bästa först som hittar den lägsta kostnadsvägen från en given initial nod till valfri målnod (av ett eller flera möjliga mål) . Den publicerades först av Hans Berliner 1979 och är relaterad till A*-sökalgoritmen .

Sammanfattning

Algoritmen lagrar intervaller för noder i trädet i motsats till enstaka punktvärderade uppskattningar. Sedan kan lövnoder i trädet sökas tills en av toppnivånoderna har ett intervall som är klart "bäst".

Detaljer

Intervallutvärderingar snarare än uppskattningar

Bladnoder i ett B*-träd ges utvärderingar som är intervall snarare än enstaka tal. Intervallet är tänkt att innehålla det sanna värdet för den noden. Om alla intervall kopplade till lövnoder uppfyller denna egenskap, kommer B* att identifiera en optimal väg till måltillståndet.

Säkerhetskopieringsprocess

För att säkerhetskopiera intervallen i trädet sätts en förälders övre gräns till det maximala av de övre gränserna för barnen. En förälders nedre gräns är satt till maxgränsen för den nedre gränsen för barnen. Observera att olika barn kan ange dessa gränser.

Avbrytande av sökning

B* expanderar systematiskt noder för att skapa "separation", vilket uppstår när den nedre gränsen för ett direkt underordnat rot är minst lika stor som den övre gränsen för alla andra direkta underordnade av roten. Ett träd som skapar separation vid roten innehåller ett bevis på att det bästa barnet är minst lika bra som alla andra barn.

I praktiken kanske komplexa sökningar inte avslutas inom praktiska resursgränser. Så algoritmen utökas normalt med artificiella avslutningskriterier som tids- eller minnesgränser. När en artificiell gräns nås måste du göra en heuristisk bedömning om vilket drag du ska välja. Normalt skulle trädet förse dig med omfattande bevis, som intervallen för rotnoder.

Expansion

B* är en bäst-först-process, vilket innebär att det är mycket effektivt att korsa trädet, upprepade gånger ner för att hitta ett blad att expandera. Det här avsnittet beskriver hur du väljer den nod som ska expanderas. (Obs: Huruvida trädet är minnesresident eller inte, är en funktion av den övergripande implementeringseffektiviteten, inklusive hur det kan mappas och/eller hanteras via verkligt eller virtuellt minne.)

Vid roten av trädet tillämpar algoritmen en av två strategier, som kallas bevisa-bäst och motbevisa-vila. I bevisa-bäst-strategin väljer algoritmen den nod som är associerad med den högsta övre gränsen. Förhoppningen är att utvidgning av den noden kommer att höja dess nedre gräns högre än någon annan nods övre gräns.

Strategin motbevisa-vila väljer barnet av roten som har den näst högsta övre gränsen. Förhoppningen är att genom att expandera den noden kanske du kan minska den övre gränsen till mindre än den nedre gränsen för det bästa barnet.

Strategival

Observera att det är meningslöst att använda strategin motbevisa-vila tills den nedre gränsen för den underordnade noden som har den högsta övre gränsen är den högsta av alla nedre gränser.

Den ursprungliga algoritmbeskrivningen gav ingen ytterligare vägledning om vilken strategi som skulle väljas. Det finns flera rimliga alternativ, som att utöka valet som har det mindre trädet.

Strategival vid icke-rotnoder

När ett barn av roten har valts ut (med bevisa-bästa eller motbevisa-vila) går algoritmen ner till en lövnod genom att upprepade gånger välja det barn som har den högsta övre gränsen.

När en lövnod nås genererar algoritmen alla efterföljande noder och tilldelar dem intervaller med hjälp av utvärderingsfunktionen. Därefter måste intervallen för alla noder säkerhetskopieras med hjälp av backupoperationen.

När transpositioner är möjliga kan säkerhetskopieringsoperationen behöva ändra värdena för noder som inte låg på urvalsvägen. I det här fallet behöver algoritmen pekare från barn till alla föräldrar så att förändringar kan spridas. Observera att spridningen kan upphöra när en säkerhetskopieringsoperation inte ändrar intervallet som är associerat med en nod.

Robusthet

Om intervallen är felaktiga (i den meningen att nodens spelteoretiska värde inte finns inom intervallet), så kanske B* inte kan identifiera den korrekta vägen. Algoritmen är dock ganska robust mot fel i praktiken.

Maven (Scrabble) -programmet har en innovation som förbättrar robustheten hos B* när utvärderingsfel är möjliga. Om en sökning avslutas på grund av separation startar Maven om sökningen efter att ha utökat alla utvärderingsintervall med en liten mängd. Denna policy vidgar gradvis trädet och raderar så småningom alla fel.

Utökning till spel för två spelare

B*-algoritmen gäller för tvåspelares deterministiska nollsummespel. Faktum är att den enda förändringen är att tolka "bäst" med avseende på sidan som rör sig i den noden. Så du skulle ta maximalt om din sida rör sig, och minimum om motståndaren rör sig. På motsvarande sätt kan du representera alla intervall ur perspektivet av sidan som ska flyttas och sedan negera värdena under säkerhetskopieringen.

Ansökningar

Andrew Palay tillämpade B* på schack. Slutpunktsutvärderingar tilldelades genom att utföra noll-move-sökningar. Det finns ingen rapport om hur väl detta system presterade jämfört med alfa-beta beskärningssökmotorer som körs på samma hårdvara.

Maven (Scrabble) -programmet tillämpade B*-sökning på slutspel. Slutpunktsutvärderingar tilldelades med hjälp av ett heuristiskt planeringssystem.

B*-sökalgoritmen har använts för att beräkna optimal strategi i ett summaspel av en uppsättning kombinatoriska spel.

Se även

Förgrenad och bunden

Berliner, Hans (1979). "The B* Tree Search Algorithm. A Best-First Proof Procedure" (PDF) . Artificiell intelligens . 12 (1): 23–40. doi : 10.1016/0004-3702(79)90003-1 . Arkiverad från originalet 2017-09-27 . Hämtad 2018-04-29 .
Russell, SJ; Norvig, P. (2003). Artificiell intelligens: ett modernt tillvägagångssätt . Upper Saddle River, NJ: Prentice Hall. sid. 188. ISBN 0-13-790395-2 .
Sheppard, Brian (2002). "VM-kaliber Scrabble" . Artificiell intelligens . 134 (1–2): 241–275. doi : 10.1016/S0004-3702(01)00166-7 .