Inom datavetenskap är B* (uttalas "Bee Star" ) en grafsökningsalgoritm som använder bästa första matchningssökning som hittar den billigaste vägen från en given startnod till valfri destinationsnod (av en eller flera möjliga destinationer) . Den publicerades först av Hans Berliner 1979 och är relaterad till A*-sökalgoritmen .
Algoritmen bevarar intervall för trädnoder , i motsats till enstaka uppskattningar. Trädets lövnoder kan sedan sökas tills en av toppnoderna har ett intervall som är klart bäst .
Bladnoderna i B*-trädet ges poäng som är intervall snarare än individuella nummer. Intervallet antas innehålla det sanna värdet för denna nod. Om alla intervall kopplade till lövnoder uppfyller denna egenskap, kommer B* att bestämma den optimala vägen till måltillståndet.
För att säkerhetskopiera intervall i ett träd sätts den övre gränsen för förfadern till den maximala övre gränsen för ättlingarna. Den nedre gränsen för förfadern sätts lika med maxgränsen för den nedre gränsen för ättlingarna. Observera att dessa gränser kan tillhandahållas av olika barn.
B* expanderar noderna systematiskt för att skapa en split , som uppstår när den nedre gränsen för rotens direkta ättling inte är mindre än den övre gränsen för någon annan direkt ättling till roten. Trädet som skapar en klyvning vid roten innehåller beviset på att det bästa barnet är minst lika bra som alla andra barn.
I praktiken kanske komplexa sökningar inte slutförs inom praktiska resursbegränsningar. Algoritmen utökas därför vanligtvis med artificiella avslutningskriterier såsom tids- eller minnesbegränsningar. När en artificiell gräns nås måste en heuristisk bedömning göras om vilket drag som ska tas. Vanligtvis ger trädet omfattande bevis, såsom rotnodintervall.
B* är en första-bästa-matchning sökprocess , vilket innebär att den är mycket effektiv när det gäller att korsa trädet, gå ner många gånger för att hitta bladet att expandera. Det här avsnittet beskriver hur du väljer en nod att expandera. ( Obs : Huruvida ett träd är minnesrelaterat beror på implementeringens övergripande effektivitet, inklusive hur det kan mappas och/eller manipuleras genom verkligt eller virtuellt minne .)
Vid roten av trädet tillämpar algoritmen en av två strategier: bevisa det bästa och motbevisa resten . I den bevisa bästa strategin väljer algoritmen den nod som är associerad med den högsta övre gränsen. Förhoppningen är att expandering av denna nod kommer att höja dess nedre gräns högre än någon annan nods övre gräns.
Strategin mot vila väljer barnet till roten som har den näst högsta övre gränsen. Förhoppningen är att man genom att utöka denna nod kan minska den övre gränsen till ett värde som är mindre än den nedre gränsen för det bästa barnet.
Val av strategiDet bör noteras att strategin att motbevisa resten är meningslös tills den nedre gränsen för den nedstigande noden med den högsta övre gränsen blir den högsta bland alla de nedre gränserna.
I den ursprungliga beskrivningen av algoritmen fanns det ingen ytterligare vägledning om vilken strategi man skulle välja. Det finns några rimliga alternativ, som att utöka utbudet med ett mindre träd.
Val av strategi på icke-rotnoderNär ett underordnat av roten har valts (med hjälp av bevisa bäst eller motbevisa vilometoden ), går algoritmen ner till den sista noden, och väljer upprepade gånger 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 poängfunktionen. Sedan måste du säkerhetskopiera intervallen för alla noder med hjälp av säkerhetskopieringen.
När transpositioner är möjliga kan en säkerhetskopieringsoperation krävas för att ändra värdena för noder som inte låg i urvalsvägen. I det här fallet behöver algoritmen pekare från ättlingar till alla förfäder så att ändringarna kan spridas. Observera att spridningen kan stoppas om säkerhetskopieringen inte ändrar intervallet som är associerat med noden.
Om intervallen är felaktiga (i den meningen att nodens spelteoretiska värde inte ingår i intervallet), så kanske B* inte kan bestämma den korrekta vägen. Men i praktiken är algoritmen ganska robust mot fel.
Det finns en innovation i Maven- programmet som förbättrar tillförlitligheten för B* när utvärderingsfel är möjliga. Om sökningen avbryts på grund av en split, startar Maven om sökningen efter en liten utökning av alla utvärderingsintervall. Denna policy utökar gradvis trädet och raderar så småningom alla fel.
Algoritm B* tillämpas på deterministiska nollsummespel för två spelare. Faktum är att den enda förändringen är tolkningen av det bästa i förhållande till sidan som rör sig i denna nod. Således bör du ta det maximala om din sida rör sig och det minsta om motståndaren rör sig. På samma sätt kan du representera alla intervall i form av sidan som ska flyttas och sedan invertera värdena under backupoperationen.
Andrew Palai tillämpade B* på schack . Slutpunktspoäng tilldelades genom att utföra en nollförskjutningssökning. Det finns ingen rapport om hur bra detta system presterade jämfört med alfa-beta-beskärningssökmotorer som körs på samma hårdvara.
Maven -programmet tillämpade B* -uppslagningen på slutspelet . Slutpunktspoäng tilldelades med hjälp av ett heuristiskt schemaläggningssystem.
Sökalgoritmen B* användes för att beräkna den optimala strategin i summaspelet för en uppsättning kombinatoriska spel.
| Algoritmer för grafsökning | ||
|---|---|---|
| Oinformerade metoder | ||
| Informerade metoder | ||
| Genvägar | ||
| Minsta spännträd | ||
| Övrig | ||