Ik heb een voorbeeld nodig voor het berekenen van penetrantie en vertakkingsfactor van de zoekboom in heuristisch zoeken in toestandsruimte. De definities zijn als volgt. Penetrantie $ P $ wordt gedefinieerd door
$ \ qquad \ displaystyle P = \ frac {L} {T} $
en vertakkingsfactor $ B $ wordt gedefinieerd door
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
waar $ L $ de lengte is van het pad van de root naar de oplossing en $ T $ het totale aantal uitgevouwen knooppunten.
Answer
Beschouw de volgende zoekboom. Uw heuristische zoekalgoritme begint de zoekactie bij het hoofdknooppunt. Niet-uitgevouwen knooppunten zijn grijs gemarkeerd.
Om de een of andere reden wordt de heuristiek naar de meest linkse substructuur geleid, terwijl in feite het doelknooppunt zich in de meest rechtse substructuur bevindt, gemarkeerd met groen.
Knooppunten met uitgevouwen zijn rood gemarkeerd. Nadat de aansprekende meest linkse substructuur een doodlopende weg bleek te zijn, wordt de heuristiek nu gelukkig direct naar het doel geleid. Uit de situatie van de vorige afbeelding, zullen we “in totaal drie nieuwe knooppunten uitbreiden voordat we bij het doel aankomen.
Uit de bovenstaande afbeelding is de lengte van het pad naar het doel $ 3 $. Er zijn $ 17 $ uitgebreide knooppunten. Daarom is de penetrantie is $ 3/17 \ ongeveer 0,43 $.
De vertakkingsfactor is het maximale aantal opvolgers van een willekeurig knooppunt. De vertakkingsfactor van een binaire boom is bijvoorbeeld $ 2 $, aangezien elk knooppunt maximaal twee kinderen heeft. Evenzo is in de bovenstaande zoekboom de vertakkingsfactor $ 3 $.
Wat je lijkt geïnteresseerd te zijn, is niet de vertakkingsfactor, maar de effectieve vertakkingsfactor $ B ^ * $ wat een manier is om de kwaliteit van een heuristiek te karakteriseren. Als het totale aantal uitgevouwen knooppunten $ T $ is, en de lengte van het pad naar het doel $ L $ is (dit is beter bekend als een s depth ), dan is $ B ^ * $ de vertakkingsfactor die een uniforme boom met diepte $ L $ zou hebben om $ T + 1 $ nodes te bevatten. Daarom,
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Als je plugt de waarden in die we bij het zoeken hebben verkregen, dat wil zeggen $ T = 17 $ en $ L = 3 $, je krijgt $ B ^ * \ ongeveer 2.165 $. Dit is precies dezelfde waarde die u krijgt als u uw vergelijking gebruikt; het is gewoon een andere representatie voor hetzelfde.
De effectieve vertakkingsfactor kan per instantie verschillen, maar is enigszins constant voor problemen die al moeilijk genoeg zijn. Een goed ontworpen heuristiek heeft een waarde van $ B ^ * $ bijna $ 1 $, waardoor redelijk grote problemen redelijk goedkoop kunnen worden opgelost.
Opmerkingen
- Als u de formule voor $ B $ oplost, krijg $ B \ ongeveer 2.165 $. Ik vraag me af wat de interpretatie van die waarde is. Het ' benadert de gemiddelde vertakkingsfactor van alle binnenste knooppunten, maar niet hetzelfde.
- @MAcad In feite, waar je in geïnteresseerd bent, is niet de vertakkingsfactor, maar de effectieve vertakkingsfactor die weg is om de kwaliteit van een heuristiek te karakteriseren. I ' ll update mijn antwoord.
- @Juho Ik denk dat als ik de vertakkingsfactorformule gebruik, ik veel getallen in de LHS zal testen en deze zal berekenen en gelijk zal controleren met RHS als volgt: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 niet gelijk aan T = 17, dus we moeten B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 testen resultaat dichtbij van T, zodat we B = 2.1 kunnen testen enzovoort totdat het resultaat T is bereikt !!!! Ik denk dat deze formule zo kan gebruiken :))))