Finding the solution of a dynamic programming problem m the form of polyadic functional 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. © 1981, ACM. All rights reserved.
Dynamic Programming as Graph Searching: An Algebraic Approach
Gnesi S;
1981
Abstract
Finding the solution of a dynamic programming problem m the form of polyadic functional 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. © 1981, ACM. All rights reserved.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_421615-doc_149736.pdf
solo utenti autorizzati
Descrizione: Dynamic programming as graph searching : an algebraic approach
Tipologia:
Versione Editoriale (PDF)
Dimensione
809.14 kB
Formato
Adobe PDF
|
809.14 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
