Jeg har brug for et eksempel på, hvordan man beregner penetrans og forgreningsfaktor for søgetræet i heuristisk søgning i state-space. Definitionerne er som følger. Penetrance $ P $ defineres af
$ \ qquad \ displaystyle P = \ frac {L} {T} $
og forgreningsfaktor $ B $ er defineret af
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
hvor $ L $ er længden af stien fra roden til løsningen og $ T $ det samlede antal udvidede noder.
Svar
Overvej følgende søgetræ. Din heuristiske søgealgoritme starter søgningen ved rodnoden. Uudvidede noder er markeret med grå.
Af en eller anden grund styres heuristikken mod det venstre venstre undertræ, når målknudepunktet faktisk er i det højre undertræ, markeret med grønt.
Noder, der har blevet udvidet er markeret med rødt. Efter at det tiltalende venstre mest subtree viste sig at være en blindgyde, bliver heuristikken nu heldigvis styret direkte mod målet. Fra situationen i det foregående tal udvider vi i alt tre nye noder, inden vi når målet.
Fra figuren ovenfor er stien til målet $ 3 $. Der er $ 17 $ udvidede noder. Derfor er gennemtrængning er $ 3/17 \ ca. 0,43 $.
forgreningsfaktor er det maksimale antal af efterfølgere til en hvilken som helst node. For eksempel er forgreningsfaktoren for et binært træ $ 2 $, da hver node højst har to børn. Ligeledes er forgreningsfaktoren i ovenstående søgetræ $ 3 $.
Hvad du synes at være interesseret i er ikke forgreningsfaktoren, men effektiv forgreningsfaktor $ B ^ * $ hvilket er en måde for at karakterisere kvaliteten af en heuristik. Hvis det samlede antal udvidede noder er $ T $, og længden af stien til målet er $ L $ (dette er mere almindeligt kendt som s dybde ), så er $ B ^ * $ den forgreningsfaktor, som et ensartet dybdetræ $ L $ ville have for at indeholde $ T + 1 $ noder. Derfor
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Hvis du plug-in de værdier, vi opnåede i søgningen, det vil sige $ T = 17 $ og $ L = 3 $, får du $ B ^ * \ ca. 2.165 $. Dette er nøjagtig den samme værdi, som du får ved at bruge din ligning; det er bare en anden repræsentation for den samme ting.
Den effektive forgreningsfaktor kan variere på tværs af tilfælde, men er noget konstant for vanskeligt nok problemer. En veldesignet heuristik ville have en værdi på $ B ^ * $ tæt på $ 1 $, så relativt store problemer kan løses rimeligt billigt.
Kommentarer
- Løsning af formlen for $ B $, du få $ B \ ca. 2.165 $. Jeg spekulerer på, hvad fortolkningen af denne værdi er. Det ' er tæt på den gennemsnitlige forgreningsfaktor for alle indre noder, men ikke den samme.
- @MAcad Faktisk er det, du er interesseret i, ikke forgreningsfaktoren, men den effektive forgreningsfaktor, som er væk for at karakterisere kvaliteten af en heuristisk. I ' opdaterer mit svar.
- @Juho Jeg tror, at hvis jeg bruger formel forgreningsfaktor, vil jeg teste mange tal i LHS og beregne det og kontrollere lig med RHS som følgende: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 ikke lig med T = 17, så vi skal teste B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 resultat nær fra T, så vi kan teste B = 2.1 og så videre, indtil vi når resultatet T !!!! Jeg tror, at denne formel kan bruge sådan :))))