Explosion combinatoire
Un article de Wikipédia, l'encyclopédie libre.
On nomme explosion combinatoire en recherche opérationnelle, et en particulier dans le domaine de la programmation dynamique, 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.
Un exemple parlant d'explosion combinatoire est celui de la fonction d'Ackermann.
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 monotones croissantes).
Un procédé utilisé conjointement consiste, dans le cas où des calculs identiques et longs risquent d'être répétés souvent, de mettre en mémoire leurs résultats pour éviter ces recalculs.
Voir aussi : Séparation et évaluation.
