Le nombre total de nœuds générés dans un arbre de recherche ou de démonstration lors d'une procédure de recherche automatique de preuves ; chaque nœud représente un sous-objectif, une affectation partielle, une formule intermédiaire ou un état d'inférence distinct.

Principe

Mesure la ramification et la duplication combinatoires du processus de recherche : une taille plus grande reflète en général plus de branches, de retours en arrière ou de réexploration d'états similaires.

Démonstration

Dans un solveur SAT par retour arrière, la taille de l'arbre de recherche compte chaque nœud de décision et chaque nœud de propagation impliquée rencontré lors de l'exploration des affectations partielles jusqu'à la découverte d'une assignation satisfaisante ou d'une réfutation.

Mauvaise application

Prendre la taille de l'arbre comme un proxy direct du temps d'exécution sans tenir compte du coût par nœud, du parallélisme ou de la mémoïsation (compression en DAG) peut fausser l'évaluation algorithmique.

Conséquence

Mesurée correctement, la taille de l'arbre fournit une borne supérieure sur le nombre d'étapes d'inférence ou de visites de nœuds ; une taille exponentielle implique un temps d'exécution potentiellement exponentiel en recherche séquentielle.

Inversion

Au lieu de compter les nœuds, on peut compter uniquement les états distincts après canonicalisation fondée sur les valeurs (taille du DAG), ce qui réduit les comptes en fusionnant les sous-problèmes identiques et inverse l'axe de mesure de l'exploration vers la réutilisation.

Limite

S'applique aux traces d'exploration en forme d'arbre ; exclut les coûts internes à un nœud (par exemple une propagation de contraintes coûteuse), ne reflète pas la réutilisation en DAG sauf si les nœuds sont fusionnés, et dépend de la granularité choisie pour définir un nœud.

Tension sémantique

Entre en tension avec des mesures comme la longueur de preuve et l'espace de preuve : la taille de l'arbre met l'accent sur la structure de ramification et la duplication, tandis que la longueur compte les inférences séquentielles et l'espace le besoin mémoire.

Synthèse

La taille de l'arbre de recherche est un comptage combinatoire quantifiant l'ampleur de la ramification et de la réexploration redondante ; combinée au coût par nœud et à l'analyse de réutilisation, elle prédit la difficulté pratique et oriente les heuristiques visant à réduire la ramification ou à permettre la fusion.