Explosion combinatoire
De nos jours, Explosion combinatoire est un sujet d'une grande importance dans la société actuelle. De nombreux aspects tournent autour de Explosion combinatoire, de son impact sur l'économie à son influence sur la culture et la politique. Depuis l’Antiquité, Explosion combinatoire a fait l’objet de débats et d’études, et a généré un grand nombre de théories et d’approches qui ont tenté de comprendre son importance et sa nature. Dans cet article, nous plongerons dans le monde de Explosion combinatoire, en explorant ses différentes facettes et en analysant son rôle dans la société contemporaine.
Pour les articles homonymes, voir combinatoire (homonymie).
Cet article est une ébauche concernant l’informatique théorique.
L'explosion combinatoire en recherche opérationnelle, et en particulier dans le domaine de la programmation dynamique, est le fait qu'un petit changement du nombre de données à considérer dans un problème par ailleurs trivial peut suffire à rendre sa solution très difficile, voire impossible dans certains cas avec les ordinateurs actuels.
Des exemples parlant d'explosion combinatoire sont ceux de la fonction d'Ackermann ou du problème du voyageur de commerce.
L'explosion combinatoire peut être jugulée efficacement dans quelques cas par des limitations de bon sens dans les valeurs (relatives ou absolues) des variables à considérer, ou par des considérations plus générales sur les fonctions en question (la programmation dynamique met à profit par exemple le cas où les fonctions sont de type croissantes).
Outre ces considérations théoriques, un procédé plus informatique consiste, dans le cas où des calculs identiques et longs risquent d'être répétés souvent, de mettre en mémoire les résultats intermédiaires pour éviter ces recalculs, mais aussi de veiller à ne pas faire des calculs qui ne servent à rien (évaluation paresseuse).
