Jag behöver ett exempel för hur man beräknar penetration och förgreningsfaktor för sökträdet i heuristisk sökning i tillståndsutrymme. Definitionerna är följande. Penetrans $ P $ definieras av
$ \ qquad \ displaystyle P = \ frac {L} {T} $
och förgreningsfaktor $ B $ definieras av
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
där $ L $ är längden på sökvägen från roten till lösningen och $ T $ det totala antalet utökade noder.
Svar
Tänk på följande sökträd. Din heuristiska sökalgoritm startar sökningen i rotnoden. Outvidgade noder är markerade med grå.
Av någon anledning styrs heuristiken mot det vänstra underträdet, när målnoden i själva verket ligger i det högsta underträdet, markerat med grönt.
Noder som har har expanderats är markerade med rött. Efter att den tilltalande vänstra subträdet visade sig vara en återvändsgränd, styrs nu heuristiken lyckligtvis direkt mot målet. Från situationen i föregående figur kommer vi att utvidga totalt tre nya noder innan vi når målet.
Från figuren ovan är längden på vägen till målet $ 3 $. Det finns $ 17 $ utökade noder. Därför är penetrans är $ 3/17 \ ungefär 0,43 $.
förgreningsfaktor är det maximala antalet efterföljare för vilken nod som helst. Till exempel är förgreningsfaktorn för ett binärt träd $ 2 $ eftersom varje nod har högst två barn. Likaså är förgreningsfaktorn $ 3 $ i ovanstående sökträd.
Vad du verkar vara intresserad av är inte förgreningsfaktorn, utan effektiv förgreningsfaktor $ B ^ * $ vilket är ett sätt för att karakterisera kvaliteten på en heuristik. Om det totala antalet utökade noder är $ T $ och längden på vägen till målet är $ L $ (detta är mer allmänt känt en s djup ), då är $ B ^ * $ den förgreningsfaktor som ett enhetligt djupträd $ L $ skulle ha för att innehålla $ T + 1 $ noder. Därför
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Om du plug-in värdena vi fick i sökningen, det vill säga $ T = 17 $ och $ L = 3 $, får du $ B ^ * \ ca 2.165 $. Detta är exakt samma värde som du får från att använda din ekvation; det är bara en annan representation för samma sak.
Den effektiva förgreningsfaktorn kan variera mellan olika fall, men är något konstant för tillräckligt hårda problem. En väldesignad heuristik skulle ha ett värde på $ B ^ * $ nära $ 1 $, vilket gör det möjligt att lösa ganska stora problem rimligt billigt.
Kommentarer
- Lösa formeln för $ B $, du få $ B \ ca 2.165 $. Jag undrar vad tolkningen av det värdet är. Det ' ligger nära den genomsnittliga förgreningsfaktorn för alla inre noder, men inte samma.
- @MAcad I själva verket är det du inte är intresserad av förgreningsfaktorn, utan den effektiva förgreningsfaktorn som är borta för att karakterisera en heuristik. I ' kommer att uppdatera mitt svar.
- @Juho Jag tror att om jag använder förgreningsfaktorformel kommer jag att testa många siffror i LHS och beräkna det och kontrollera lika med RHS som följande: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 inte lika T = 17 så vi måste testa B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 resultat nära T så att vi kan testa B = 2.1 och så vidare tills vi når resultatet T !!!! Jag tror att den här formeln kan använda så här :))))