Refining Partial Invalidations for Indexed Algebraic Dynamic Programming

Autor:	Christopher Bacher, Günther R. Raidl
Rok vydání:	2017
Předmět:	Dynamic programming Speedup Theoretical computer science General purpose Computer science Refining Memoization Face (geometry) Algebraic number Logic programming
Zdroj:	Lecture Notes in Computer Science ISBN: 9783319729251 MOD
DOI:	10.1007/978-3-319-72926-8_47
Popis:	We consider dynamic programs modelled in a variant of the Algebraic Dynamic Programming (ADP) framework which allows us to develop general purpose solvers for Dynamic Programming problems. In such dynamic programs the information accumulated in memoization tables is usually lost if the input data of the problem instance changes. We analyze those changes and how they affect the information stored for subproblems of a dynamic program. We then present the theory for a new algorithm for partial invalidation and incremental evaluation of ADPs based on a previous simpler algorithm. The new algorithm should reduce the amount of discarded information in Dynamic Programming tables and to speed up the reevaluation of dynamic programs in the face of changing inputs. In future work we will integrate the algorithms into a framework currently under development to conduct thorough experiments on their practical efficieny.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::17d57375b574038eb758cd24ad8a1770 https://doi.org/10.1007/978-3-319-72926-8_47 Zobrazit plný text záznamu