Explosion combinatoire

Carte Commune · n° 369574

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...

Lire sur Wikipédia