Une croissance rapide (souvent superpolynomiale) du nombre d'états candidats, d'affectations ou de configurations qu'il faut considérer lors du raisonnement automatisé, de la recherche ou de la construction de modèles.

Principe

Le branching combinatoire multiplie les possibilités ; sans contraintes, élagage ou exploitation de la structure, le nombre de candidats croît exponentiellement ou davantage avec la taille du problème.

Démonstration

Une formule SAT avec n variables booléennes non contraintes donne jusqu'à 2^n assignations à considérer ; ajouter des choix non contraints dans un problème de planification multiplie de même l'arbre de recherche et rend les méthodes exhaustives impossibles.

Mauvaise application

Appliquer une recherche exhaustive sans information ou un branchement naïf à des problèmes à structure combinatoire (par exemple énumérer à l'aveugle toutes les permutations pour un ordonnancement) garantit des temps d'exécution et une consommation de ressources impraticables.

Conséquence

La reconnaissance de l'explosion de l'espace de recherche motive des heuristiques, bris de symétrie, propagation de contraintes, décomposition ou algorithmes d'approximation qui réduisent le branching effectif et restaurent la faisabilité pour des instances pratiques.

Inversion

Réduction de l'espace de recherche — introduction de contraintes, abstractions ou factorisations qui diminuent l'ensemble de candidats et permettent une recherche efficace.

Limite

S'applique aux tâches de recherche et de raisonnement combinatoire où le nombre de candidats croît selon des combinatoires ; n'inclut pas la complexité purement arithmétique inhérente à des calculs en forme fermée sans branching.

Tension sémantique

Tension avec l'explosion des ressources : l'explosion décrit la croissance combinatoire des candidats, tandis que l'explosion des ressources met l'accent sur les conséquences (temps, mémoire) ; les stratégies d'atténuation peuvent cibler l'un ou l'autre aspect.

Synthèse

L'explosion de l'espace de recherche est la croissance combinatoire des possibilités en raisonnement automatisé qui rend l'énumération naïve infaisable ; la gestion pratique requiert l'exploitation de la structure (contraintes, heuristiques, décomposition) pour réduire le branching et concentrer la recherche.