En informática , estructuras de datos en forma de árbol y teoría de juegos , el factor de ramificación es el número de hijos en cada nodo , el grado de salida . Si este valor no es uniforme, se puede calcular un factor de ramificación promedio .
Por ejemplo, en ajedrez , si se considera que un "nodo" es una posición legal, se ha dicho que el factor de ramificación promedio es de aproximadamente 35, [1] [2] y un análisis estadístico de más de 2,5 millones de partidas reveló un promedio de 31. [3] Esto significa que, en promedio, un jugador tiene alrededor de 31 a 35 movimientos legales a su disposición en cada turno. En comparación, el factor de ramificación promedio para el juego Go es 250. [1]
Los factores de ramificación más altos hacen que los algoritmos que siguen cada rama en cada nodo, como las búsquedas exhaustivas de fuerza bruta , sean computacionalmente más costosos debido al número exponencialmente creciente de nodos, lo que lleva a una explosión combinatoria .
Por ejemplo, si el factor de ramificación es 10, entonces habrá 10 nodos un nivel por debajo de la posición actual, 10 2 (o 100) nodos dos niveles por debajo, 10 3 (o 1.000) nodos tres niveles por debajo, y así sucesivamente. Cuanto mayor sea el factor de ramificación, más rápido se producirá esta "explosión". El factor de ramificación se puede reducir mediante un algoritmo de poda .
El factor de ramificación promedio se puede calcular rápidamente como el número de nodos que no son raíz (el tamaño del árbol, menos uno; o el número de aristas) dividido por el número de nodos que no son hojas (el número de nodos con hijos).
La velocidad a la que aumentan las posibles posiciones está directamente relacionada con el "factor de ramificación" de un juego, o el número promedio de movimientos disponibles en un turno determinado. El factor de ramificación del ajedrez es 35. El del Go es 250. Los juegos con altos factores de ramificación hacen que los algoritmos de búsqueda clásicos como minimax sean extremadamente costosos.