En informática , estructuras de datos de árbol y teoría de juegos , el factor de ramificación es el número de hijos en cada nodo , el grado externo . Si este valor no es uniforme, se puede calcular un factor de ramificación promedio .
Por ejemplo, en ajedrez , si un "nodo" se considera una posición legal, se dice que el factor de ramificación promedio es 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 entre 31 y 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 1000) 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 hoja (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 factores de ramificación altos hacen que los algoritmos de búsqueda clásicos como minimax sean extremadamente costosos.