Factor de ramificación

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Un Árbol rojo-negro con factor de ramificación 2.

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

Por ejemplo, en ajedrez, si se considera un "nodo" como una posición legal, el factor de ramificación medio es aproximadamente 35.[1]​ Esto significa que, de media, un jugador puede realizar alrededor de 35 movimientos legales 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, 102 (ó 100) nodos dos niveles por debajo, 103 (ó 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.

Referencias[editar]

  1. François Dominic Laramée. «Chess Programming Part IV: Basic Search». GameDev.net. Archivado desde el original el 14 de mayo de 2007. Consultado el 2007.