Na árvore de pesquisa abaixo, existem 11 nós, 5 dos quais são folhas. Existem 10 ramos.
O fator médio de ramificação é dado por 10/6 ou 10/11?
As folhas são incluídas no cálculo? Intuitivamente, eu acho que não, já que estamos interessados em nós com ramificações. No entanto, uma definição dada a mim pelo meu professor foi “O número médio de ramos de todos os nós da árvore”, o que implicaria que as folhas estão incluídas.
Comentários
- Ótima pergunta. Eu ' tomei a liberdade de adicionar a tag " ai-basics ". Bem-vindo ao Stack: AI!
Resposta
Eu diria que as folhas per se contam também, mas apenas se forem folhas reais, como, por exemplo, posições de xeque-mate no xadrez.
Tal nó não tem filhos e nenhum cálculo adicional é necessário. Ao contrário de nós que ainda não foram expandidos.
Observe que sempre contar as folhas provavelmente leva a (n-1)/n para cada n -nó te!
Resposta
Da Wikipedia:
Em computação, estruturas de dados em árvore e teoria dos jogos, o fator de ramificação é o número de filhos em cada nó , o outdegree . Se este valor não for uniforme, um fator de ramificação médio pode ser calculado.
Outdegree significado – No caso de gráficos direcionados, número de arestas entrando um nó é conhecido como grau de entrada do nó correspondente e o número de arestas saindo de um nó é conhecido como grau de saída do nó correspondente.
Você esqueceu o outdegree parte. Em IA nós g geralmente desenha gráficos direcionados de um estado para outro, e outdegree é o número de caminhos que saem de um determinado nó. Em sua direção de gráfico não é fornecida. Além disso, seu gráfico não é simétrico, mas você ainda pode descobrir o fator de ramificação (com um pouco de dificuldade) de gráficos direcionados não simétricos conforme fornecido aqui . Então, tecnicamente, sua conclusão está correta sobre os nós folha não sendo contados (assumindo que eles sejam o último estado do qual nenhum outro estado pode ser alcançado – beco sem saída). Espero que isso ajude!