Jeg trenger et eksempel for hvordan man beregner penetrasjon og forgreningsfaktor for søketreet i i heuristisk søk etter stat. Definisjonene er som følger. Gjennomtrengning $ P $ er definert av
$ \ qquad \ displaystyle P = \ frac {L} {T} $
og forgreningsfaktor $ B $ er definert av
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
hvor $ L $ er lengden på banen fra roten til løsningen og $ T $ det totale antallet noder som er utvidet.
Svar
Vurder følgende søketre. Den heuristiske søkealgoritmen din starter søket ved rotnoden. Uutvidede noder er markert med grå.
Av en eller annen grunn blir heuristikken guidet mot det venstre undertræret, når målnoden faktisk er i det høyre undertrådet, merket med grønt.
Noder som har blitt utvidet er merket rødt. Etter at det tiltalende venstre mest subtreet viste seg å være en blindvei, blir heuristikken nå heldigvis guidet direkte mot målet. Fra situasjonen til forrige figur vil vi utvide totalt tre nye noder før vi kommer til målet.
Fra figuren over er stien til målet $ 3 $. Det er $ 17 $ utvidede noder. Derfor er penetrasjon er $ 3/17 \ ca. 0,43 $.
forgreningsfaktor er det maksimale antallet av etterfølgere av hvilken som helst node. For eksempel er forgreningsfaktoren til et binært tre $ 2 $ siden hver node maksimalt har to barn. På samme måte er forgreningsfaktoren i $ 3 $ i det ovennevnte søketreet. du ser ut til å være interessert i er ikke forgreningsfaktoren, men effektiv forgreningsfaktor $ B ^ * $ som er en måte for å karakterisere kvaliteten på en heuristikk. Hvis det totale antallet utvidede noder er $ T $, og lengden på banen til målet er $ L $ (dette er mer kjent som en s dybde ), så er $ B ^ * $ forgreningsfaktoren som et ensartet dybdetre $ L $ ville ha for å inneholde $ T + 1 $ noder. Derfor,
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Hvis du plugger inn verdiene vi fikk i søk, det vil si $ T = 17 $ og $ L = 3 $, får du $ B ^ * \ ca 2.165 $. Dette er nøyaktig den samme verdien du får fra å bruke ligningen din; det er bare en annen representasjon for den samme tingen.
Den effektive forgreningsfaktoren kan variere mellom tilfeller, men er noe konstant for vanskelige problemer. En veldesignet heuristikk vil ha en verdi på $ B ^ * $ nær $ 1 $, slik at ganske store problemer kan løses rimelig billig.
Kommentarer
- Løs formelen for $ B $, du få $ B \ ca 2.165 $. Jeg lurer på hva tolkningen av denne verdien er. Det ' er nær den gjennomsnittlige forgreningsfaktoren for alle indre noder, men ikke den samme.
- @MAcad Det du er interessert i er faktisk ikke forgreningsfaktoren, men den effektive forgreningsfaktoren som er borte for å karakterisere kvaliteten på en heuristikk. I ' Jeg oppdaterer svaret mitt.
- @Juho Jeg tror at hvis jeg bruker formel forgreningsfaktor, vil jeg teste mange tall i LHS og beregne det og sjekke lik RHS som følgende: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 ikke lik T = 17, så vi må teste B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 resultat i nærheten av T slik at vi kan teste B = 2.1 og så videre til vi når resultatet T !!!! Jeg tror denne formelen kan bruke slik :))))