En el árbol de búsqueda de abajo, hay 11 nodos, 5 de los cuales son hojas. Hay 10 ramas.
¿El factor de ramificación promedio está dado por 10/6 o 10/11?
¿Se incluyen las hojas en el cálculo? Intuitivamente, creo que no, ya que estamos interesados en nodos con ramas. Sin embargo, una definición que me dio mi profesor fue «El número promedio de ramas de todos los nodos del árbol», lo que implicaría que las hojas están incluidas.
Comentarios
- Gran pregunta. ' me he tomado la libertad de agregar la etiqueta " ai-basics ". ¡Bienvenido a Stack: AI!
Responder
Yo diría que las hojas per se cuenta también, pero sólo si son hojas reales, como por ejemplo, posiciones de jaque mate en el ajedrez.
Tal nodo realmente no tiene hijos y no se necesitan más cálculos. A diferencia de los nodos que aún no se expandieron.
Tenga en cuenta que siempre contar las hojas demostrablemente conduce a (n-1)/n por cada n -nodo you!
Respuesta
De Wikipedia:
En informática, estructuras de datos de árboles y teoría de juegos, el factor de ramificación es el número de hijos en cada nodo , el outdegree . Si este valor no es uniforme, se puede calcular un factor de ramificación promedio.
Grado superior significado: en el caso de gráficos dirigidos, el número de bordes que entran un nodo se conoce como grado de entrada del nodo correspondiente y la cantidad de bordes que salen de un nodo se conoce como grado de salida del nodo correspondiente.
Olvidó el outdegree part. En AI usamos Generalmente dibuja gráficos dirigidos de un estado a otro, y outdegree es el número de rutas que salen de un nodo en particular. En su gráfico no se da la dirección. Además, su gráfico no es simétrico, pero aún puede averiguar el factor de ramificación (con un poco de dificultad) de los gráficos dirigidos no simétricos como se indica aquí . Entonces, técnicamente, su conclusión es correcta acerca de que los nodos hoja no se cuentan (asumiendo que son el último estado desde el cual no se puede alcanzar ningún otro estado: callejón sin salida). ¡Espero que esto ayude!