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