Potřebuji příklad, jak vypočítat penetranci a větvící faktor vyhledávacího stromu v heuristickém hledání stavového prostoru. Definice jsou následující. Penetrance $ P $ je definován
$ \ qquad \ displaystyle P = \ frac {L} {T} $
a větvící faktor $ B $ je definováno jako
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
kde $ L $ je délka cesty od kořene k řešení a $ T $ celkový počet rozšířených uzlů.
Odpověď
Zvažte následující vyhledávací strom. Váš heuristický vyhledávací algoritmus zahájí vyhledávání v kořenovém uzlu. Neexpandované uzly jsou označeny šedě.
Heuristika je z nějakého důvodu vedena k podstromu nejvíce vlevo, když je cílový uzel ve skutečnosti v podstromu nejvíce vpravo, označeném zeleně.
Uzly, které mají byly rozbaleny, jsou označeny červeně. Poté, co se atraktivní podstrom nejvíce vlevo ukázal být slepou uličkou, je nyní heuristika naštěstí vedena přímo k cíli. Ze situace z předchozího obrázku „před dosažením cíle rozšíříme celkem tři nové uzly.
Z výše uvedeného obrázku je délka cesty k cíli 3 $. Existuje 17 $ $ rozšířených uzlů. Proto je penetrance je $ 3/17 \ přibližně 0,43 $.
faktor větvení je maximální počet nástupců libovolného uzlu. Například faktor větvení binárního stromu je $ 2 $, protože každý uzel má nejvýše dvě podřízené položky. Podobně ve výše uvedeném vyhledávacím stromu je faktor větvení $ 3 $.
Co Zdá se, že vás zajímá faktor větvení, ale efektivní faktor větvení $ B ^ * $, což je způsob charakterizovat kvalitu heuristiky. Pokud je celkový počet rozšířených uzlů $ T $ a délka cesty k cíli je $ L $ (toto je běžněji známé s depth ), pak $ B ^ * $ je větvící faktor, který by měl jednotný strom hloubky $ L $, aby obsahoval $ T + 1 $ uzly. Proto
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Pokud Pokud zapojíte hodnoty, které jsme získali ve vyhledávání, tj. $ T = 17 $ a $ L = 3 $, získáte $ B ^ * \ přibližně 2,165 $. Jedná se o přesně stejnou hodnotu, jakou získáte použitím rovnice; je to jen pouhá jiná reprezentace stejné věci.
Efektivní větvící faktor se může v různých případech lišit, ale je dostatečně konstantní pro dostatečně těžké problémy. Dobře navržená heuristika by měla hodnotu $ B ^ * $ blízko $ 1 $, což umožňuje rozumně levně vyřešit poměrně velké problémy.
Komentáře
- Řešení vzorce pro $ B $, vy získejte $ B \ přibližně 2,165 $. Zajímalo by mě, jaká je interpretace této hodnoty. Je to ' blízké průměrnému větvícímu faktoru všech vnitřních uzlů, ale není to stejné.
- @MAcad Ve skutečnosti vás nezajímá faktor větvení, ale efektivní faktor větvení, který charakterizuje kvalitu heuristiky. I ' Aktualizuji svoji odpověď.
- @Juho Myslím, že pokud použiji vzorec větvícího faktoru, otestuji mnoho čísel v LHS a vypočítám je a porovnám s RHS jako následující: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 nerovná se T = 17, takže musíme otestovat B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 výsledek blízko od T, takže můžeme testovat B = 2,1 a tak dále, dokud nedosáhneme výsledku T !!!! Myslím, že tento vzorec lze použít takto :))))