Explosion combinatoire
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (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...) est celui de la fonction d'Ackermann.

L'explosion (Une explosion est la transformation rapide d'une matière en une autre matière ayant un volume plus grand, généralement sous forme de gaz. Plus cette...) combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.) peut être jugulée efficacement dans quelques cas par des limitations de bon sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution...) 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 (Inventée par le professeur Richard Bellman, la programmation dynamique permet de résoudre au moyen d'un ordinateur tout problème d'optimisation dont la fonction objectif se décrit comme la somme de fonctions monotones non-décroissantes...) 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 (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) leurs résultats pour éviter ces recalculs.

Voir aussi : Séparation et évaluation (Un algorithme par séparation et évaluation, également appelé selon le terme anglo-saxon branch and bound, est une méthode générique de résolution de problèmes d'optimisation, et plus particulièrement...).

Page générée en 0.052 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique