Varenne, Matthieu (2023) Réduction de diagrammes binaires de décision PRE - Research Project, ENSTA.

This is the latest version of this item.



Dynamic programming is a method of solving optimization problems by making sequential decisions. A dynamic programming algorithm constructs a graph, known as a binary decision diagram (BDD), which represents all possible solutions for a given problem and problem values, grouping together all the decisions that have been made over the course of iterations. Solving this optimization problem thus becomes equivalent to solving a shortest-path problem in a graph. We note, however, that using this method for large instances or more complex problems quickly results in very large BDDs (exponential growth). The aim of the internship is therefore to set up a process for reducing the BDDs to a manageable size, exactly equivalent to the initial graph.

Item Type:Thesis (PRE - Research Project)
Uncontrolled Keywords:Dynamic Programming , Binary Decision Diagrams (BDD)
Subjects:Mathematics and Applications
ID Code:9709
Deposited By:Matthieu VARENNE
Deposited On:01 sept. 2023 14:26
Dernière modification:01 sept. 2023 14:26

Available Versions of this Item

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

Repository Staff Only: item control page