##  [Factor de Ramificación](/es/node/60898) 

 Definición

El número medio o máximo de nodos hijos expandidos desde un nodo de búsqueda durante búsqueda de pruebas o modelos; medido por paso de decisión o como base de ramificación del árbol de búsqueda.

 

 

 

 

 

 





## Principio

Principio

El Factor De Ramificación determina la tasa de crecimiento exponencial de un árbol de búsqueda: si cada nodo genera b hijos, el tamaño crece aproximadamente como b^d para profundidad d, por lo que reducir b es crítico para la eficiencia.

 

 

 

 

 





## Demostración

Demostración

Una búsqueda estilo DPLL que asigna una variable a verdadero o falso tiene un factor de ramificación de hasta 2 por decisión; una heurística que produce a menudo propagaciones unitarias reduce el factor medio por debajo de 2.

 

 

 

 

## Aplicación incorrecta

Aplicación incorrecta

Tratar el factor de ramificación como una constante intrínseca a la instancia e independiente del algoritmo o heurística elegido ignora que la ramificación depende fuertemente del orden de variables, propagación y poda.

 

 

 

 

 





## Consecuencia

Consecuencia

Un factor medio de ramificación menor reduce drásticamente el esfuerzo de búsqueda y puede convertir búsquedas exponenciales en instancias prácticamente resolubles al reducir la base efectiva de la exponenciación.

 

 

 

 

## Inversión

Inversión

Un alto factor de ramificación (muchos hijos por nodo) denota búsqueda amplia en lugar de profunda; algunos algoritmos sacrifican menor profundidad por mayor ramificación con diferentes compensaciones de complejidad.

 

 

 

 

 





## Límite

Límite

Se aplica a procesos de búsqueda ramificantes; excluye medidas para sistemas de inferencia no ramificantes (canales de transformación puramente lineales) y depende del algoritmo, no solo de la instancia.

 

 

 

 

 





## Tensión semántica

Tensión semántica

Tensión con el Tamaño Del Conjunto Backdoor y la Anchura De Cláusula: un backdoor pequeño puede forzar bajo ramificado tras asignaciones, mientras que cláusulas anchas pueden aumentar la ramificación salvo que la propagación lo impida.

 

 

 

 

 





## Síntesis

Síntesis

El Factor De Ramificación es la medida local de fan-out de los procedimientos de búsqueda que, junto con la profundidad, controla la explosión combinatoria de nodos; depende del algoritmo y de la instancia y es central para predicciones de tiempo de ejecución.