Explosion combinatoire
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).
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).
