École Nationale Supérieure de
Techniques Avancées

Il s'agit de la dernière version de ce document.

Résumé

La programmation dynamique est une méthode de résolution des problèmes d’optimisation sous forme d’une prise de décisions séquentielles. Un algorithme de programmation dynamique construit un graphe, que l’on nomme diagramme binaire de décisions (BDD), qui représente l’ensemble des solutions possibles pour un problème et des valeurs du problème donnés, en regroupant toutes les décisions qui ont été prises au fil des itérations. Résoudre ce problème d’optimisation devient donc équivalent à résoudre un problème de plus court chemin dans un graphe. On constate cependant que l’utilisation de cette méthode pour des instances de grandes tailles ou des problèmes plus complexes donne rapidement lieu à des BDDs de très grande taille (croissance exponentielle). L’objectif du stage est donc de mettre en place un processus de réduction des BDDs, pour parvenir à un graphe d’une taille exploitable et qui soit exactement équivalent au graphe initial.

Versions disponibles de ce document

• Réduction de diagrammes binaires de décision (deposited 01 sept. 2023 14:26) [Actuellement Affiché]