Page 28 - 当代控制理论及应用技术概论

当代控制理论及应用技术概论
Introduction to Contemporary Control Theory and Applied Technology

动态规划基本思想：动态规划算法通常用于求解具有某种最优性质的问题。
在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到
具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分
解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与
分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互

相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问
题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时
再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用

一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它
被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规
划算法多种多样，但它们具有相同的填表格式。
动态规划问题中的术语：
阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于

求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情
况下，阶段变量是离散的，用 k 表示。此外，也有阶段变量是连续的情形。如果
过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决

策时，阶段变量就是连续的。
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的
主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位
置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。
无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则

在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定
时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表
示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个

线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以
前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前
的状态去影响它的未来的发展，这个性质称为无后效性。
决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一
种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可

以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策

20
20