Dans larborescence de recherche ci-dessous, il y a 11 nœuds, dont 5 sont des feuilles. Il y a 10 branches.
Le facteur de branchement moyen est-il donné par 10/6 ou 10/11?
Les feuilles sont-elles incluses dans le calcul? Intuitivement, je ne pense pas, car nous nous intéressons aux nœuds avec des branches. Cependant, une définition que ma donnée mon professeur était « Le nombre moyen de branches de tous les nœuds de larbre », ce qui impliquerait que les feuilles soient incluses.
Commentaires
- Excellente question. Jai ' pris la liberté dajouter la balise " ai-basics ". Bienvenue dans Stack: AI!
Réponse
Je dirais que les feuilles en soi compte aussi, mais seulement sils « sont de vraies feuilles, comme par exemple les positions déchec et mat aux échecs.
Un tel nœud na vraiment pas denfants et aucun calcul supplémentaire nest nécessaire. Contrairement aux nœuds qui « nont pas encore été développés.
Notez que toujours compter les feuilles prouvé conduit à (n-1)/n pour chaque n -node thee!
Réponse
De Wikipedia:
En informatique, en arborescence et en théorie des jeux, le facteur de branchement est le nombre denfants à chaque nœud , le outdegree . Si cette valeur nest pas uniforme, un facteur de branchement moyen peut être calculé.
Outdegree signification – Dans le cas de graphes orientés, nombre darêtes entrant dans un nœud est appelé en-degré du nœud correspondant et le nombre darêtes sortant dun nœud est appelé en-degré du nœud correspondant.
Vous avez oublié le outdegree part. En IA, nous g dessine généralement des graphes dirigés dun état à un autre, et outdegree est le nombre de chemins quittant un nœud particulier. Dans votre graphique, la direction nest pas donnée. De plus, votre graphe nest pas symétrique, mais vous pouvez toujours trouver le facteur de branchement (avec un peu de difficulté) des graphes orientés non symétriques comme indiqué ici . Donc, techniquement, votre conclusion est correcte sur le fait que les nœuds feuilles ne sont pas comptés (en supposant quils sont le dernier état à partir duquel aucun autre état ne peut être atteint – impasse). Jespère que cela vous aidera!