Factor de ramificación

En el ámbito de la computación, árboles (Estructura de datos) y teoría de juegos, se denomina factor de ramificación al número de nodos hijos en cada nodo. Si este valor no es uniforme, se puede calcular el factor de ramificación medio.

Un Árbol rojo-negro con factor de ramificación 2.

Por ejemplo, en ajedrez, si se considera un "nodo" como una posición válida, el factor de ramificación medio es aproximadamente 35.[1] Esto significa que, de media, un jugador puede realizar alrededor de 35 movimientos válidos en cada turno.

Factores de ramificación altos hacen que los algoritmos que evalúan todas las ramas de todos los nodos, como los de búsqueda por fuerza bruta, sean más costosos computacionalmente hablando por el crecimiento exponencial del número de nodos, dando lugar a una explosión combinatoria.

Por ejemplo, si el factor de ramificación es 10, habrá 10 nodos en el siguiente nivel a la posición actual, 10² (ó 100) nodos dos niveles por debajo, 10³ (ó 1.000) nodos tres niveles por debajo, y así sucesivamente. Cuanto mayor es el factor de ramificación, más rápidamente ocurre esta "explosión". El factor de ramificación puede ser reducido mediante algoritmos de poda.