Dynamic Programming as Graph Searching: An Algebraic Approach
Stefania Gnesi, Ugo Montanari, Alberto Martelli · Journal of the ACM · 1981
Finding the solution of a dynamic programming problem m the form of polyadlc funcUonal equatmns is shown to be equivalent to searching a mmmaal cost path in an AND/OR graph with monotone cost functions The proof is given in an algebraic framework and is based on a commutaUvity result between solutton and mterpretauon of a symbohc system This approach Is simdar to the one used by some authors to prove the eqmvalence between the operaUonal and denotatmnal semantics of programming languages