In de zoekboom hieronder zijn er 11 knooppunten, waarvan 5 bladeren. Er zijn 10 takken.
Wordt de gemiddelde vertakkingsfactor gegeven door 10/6, of 10/11?
Worden bladeren meegenomen in de berekening? Intuïtief denk ik van niet, aangezien we geïnteresseerd zijn in knooppunten met vertakkingen. Een definitie die mijn professor mij gaf was echter “Het gemiddelde aantal takken van alle knooppunten in de boom”, wat zou impliceren dat bladeren zijn inbegrepen.
Reacties
- Geweldige vraag. Ik ' heb de vrijheid genomen om de tag " ai-basics " toe te voegen. Welkom bij Stack: AI!
Answer
Ik “zou zeggen dat de bladeren per se tellen ook mee, maar alleen als het echte bladeren zijn, zoals bijvoorbeeld schaakmatposities bij schaken.
Zon knoop heeft echt geen kinderen en er is geen verdere berekening nodig. In tegenstelling tot knooppunten die “nog niet zijn uitgebreid.
Merk op dat het altijd aantoonbaar tellen van de bladeren leidt tot (n-1)/n voor elk n -knooppunt u!
Antwoord
Van Wikipedia:
Bij computers, boomgegevensstructuren en speltheorie is de vertakkingsfactor het aantal kinderen bij elk knooppunt , de outdegree . Als deze waarde niet uniform is, kan een gemiddelde vertakkingsfactor worden berekend.
Outdegree betekenis – In het geval van gerichte grafieken, het aantal randen dat een knoop staat bekend als in-graad van het corresponderende knooppunt en het aantal randen dat uit een knooppunt komt, staat bekend als out-graad van het corresponderende knooppunt.
Je bent de outdegree deel. In AI gaan we teken in het algemeen gerichte grafieken van de ene staat naar de andere, en outdegree is het aantal paden dat een bepaald knooppunt verlaat. In uw grafiek is de richting niet aangegeven. Ook is uw grafiek niet symmetrisch, maar u kunt nog steeds de vertakkingsfactor (met enige moeite) van niet-symmetrische gerichte grafieken vinden, zoals hier wordt gegeven. Dus technisch gezien is uw conclusie correct dat bladknooppunten niet worden geteld (ervan uitgaande dat ze de laatste staat zijn van waaruit geen andere staat kan worden bereikt – doodlopende weg). Ik hoop dat dit helpt!