Finite-State Processes and Dynamic Programming

Finite-State Processes and Dynamic Programming
复制标题

有限状态过程和动态规划

DOI：
--
复制
发表时间：
1967
期刊：
影响因子：
--
通讯作者：
M. Held
M. Held
中科院分区：
--
文献类型：
--
作者：
R. Karp;M. Held

文献摘要

被引文献

相似文献

本文提出了一种形式体系，其中严格研究了动态规划在离散、确定性问题中的应用。这一发展背后的两个核心概念是离散决策过程和顺序决策过程。离散决策过程提供了一种方便的问题陈述方式，而单调顺序决策过程（叠加了一定成本结构的有限自动机）自然对应于动态规划算法。通过单调顺序决策过程来表征离散决策过程，并将该表征用于各种问题的动态规划算法的偏差中。
This paper develops a formalism within which the application of dynamic programming to discrete, deterministic problems is rigorously studied. The two central concepts underlying this development are discrete decision process and sequential decision process. Discrete decision processes provide a convenient means of problem statement, while monotone sequential decision processes (which are finite automata with a certain cost structure superimposed) correspond naturally to dynamic programming algorithms. The representations of discrete decision processes by monotone sequential decision processes are characterized, and this characterization is used in the deviation of dynamic programming algorithms for a variety of problems.