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

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

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

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

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

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

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 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

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.