Factor de ramificación

De Wikipedia, la enciclopedia libre
Saltar a: navegación, 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 algos hacen que evalúan todas las ramas en todos los nodos, como búsqueda por fuerza bruta, son más costosos computacionalmente 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 de 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 algorítmos de poda.

Referencias[editar]

  1. François Dominic Laramée. «Chess Programming Part IV: Basic Search». GameDev.net.