Le nombre moyen ou maximal d'enfants développés à partir d'un nœud de recherche lors d'une recherche de preuve ou de modèle ; mesuré par étape de décision ou comme base de branchement globale de l'arbre de recherche.

Principe

Le Facteur De Ramification détermine le taux de croissance exponentielle d'un arbre de recherche : si chaque nœud engendre b enfants, la taille de l'arbre croît approximativement comme b^d pour une profondeur d, réduire b est donc critique pour l'efficacité.

Démonstration

Une recherche de type DPLL qui assigne une variable vrai ou faux a un facteur de ramification jusqu'à 2 par décision ; un heuristique produisant souvent des propagrations unitaires réduit efficacement le facteur de ramification moyen en dessous de 2.

Mauvaise application

Traiter le facteur de ramification comme une constante intrinsèque à l'instance, indépendante de l'algorithme ou de l'heuristique choisis, ignore que le branchement dépend fortement de l'ordre des variables, de la propagation et des politiques d'élagage.

Conséquence

Un facteur de ramification moyen plus faible réduit considérablement l'effort de recherche et peut transformer des recherches exponentielles en instances pratiquement résolubles en abaissant la base effective de l'exponentielle.

Inversion

Un facteur de ramification élevé (beaucoup d'enfants par nœud) désigne une recherche large plutôt que profonde ; certains algorithmes échangent un branchement plus large contre des profondeurs plus faibles avec des compromis de complexité différents.

Limite

S'applique aux processus de recherche par branchement ; exclut les mesures pour les systèmes d'inférence non ramifiés (pipelines de transformations purement linéaires) et dépend de l'algorithme, pas seulement de l'instance.

Tension sémantique

Tension avec la Taille De L'Ensemble Backdoor et la Largeur De Clause : un petit backdoor peut induire un faible branchement après assignations, tandis que des clauses larges peuvent augmenter le branchement sauf si la propagation l'empêche.

Synthèse

Le Facteur De Ramification est la mesure locale de la fan-out des procédures de recherche qui, conjointement avec la profondeur de recherche, contrôle l'explosion combinatoire des nœuds ; il dépend de l'algorithme et de l'instance et est central aux prévisions de temps d'exécution.