Varenne, Matthieu (2023) Réduction de diagrammes binaires de décision PRE - Research Project, ENSTA.
This is the latest version of this item.
![[img]](/style/images/fileicons/application_pdf.png)
| PDF 830Kb |
Abstract
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
