高中 计算机 竞赛 辅导,高中计算机竞赛 编程 动态规划解析辅导.doc

高中 计算机 竞赛 辅导,高中计算机竞赛 编程 动态规划解析辅导.doc

第二节 动态规划

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

一、 动态规划的基本模型

(一)多阶段决策过程的最优化问题

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如下图所示：

这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。

例 3-2-1 ：最短路径问题。下图给出了一个地图，地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？

分析：把A到E的全过程分成四个阶段，用K表示阶段变量，第1阶段有一个初始状态A，有两条可供选择的支路A-B1、A-B2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。用DK(XI，X+1J)表示在第K阶段由初始状态XI到下阶段的初始状态X+1J的路径距离，FK(XI)表示从第K阶段的XI到终点E的最短距离，利用倒推的方法，求解A到E的最短距离。具体计算过程如下：

S1 ： K = 4 有

F4(D1)= 3，

F4(D2)= 4，

F4(D3)= 3；

S2 ： K = 3 有

F3(C1)= MIN{ D3(C1，D1)+ F4(D1)，D3(C1，D2)+ F4(D2)}

= MIN{ 5+3，6+4 } = 8，

F3(C2)= D3(C2，D1)+ F4(D1)= 5+3 = 8；

F3(C3)= D3(C3，D3)+ F4(D3)= 8+3 = 11；

F3(C4)= D3(C4，D3)+ F4(D3)= 3+3 = 6；

S3 ： K = 2 有

F2(B1)= MIN{ D2(B1，C1)+ F3(C1)，D2(B1，C2)+ F3(C2)，

D2(B1，C3)+ F3(C3)} = MIN{ 1+8,6+8,3+11} = 9,

F2(B2)= MIN{ D2(B2，C2)+ F3(C2)，D2(B2，C4)+ F3(C4)}

= MIN{ 8+8，4+6 } = 10；

S4 ： K = 1 有

F1(A)= MIN{ D1(A，B1)+ F2(B1)，D1(A，B2)+ F2(B2)}

= MIN{ 5+9，3+10} = 13。

因此由A点到E点的全过程最短路径为A→B2→C4→D3→E；最短路程长度为13。

从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E的最短距离，当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。

在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。

(二)动态规划的基本概念和基本模型构成

现在我们来介绍动态规划的基本概念。

1. 阶段和阶段变量：

用动态规划求解一个问题时，需要将问题的全过程恰当地分成若干个相互联系的阶段，以便按一定的次序去求解。描述阶段的变量称为阶段变量，通常用K表示，阶段的划分一般是根据时间和空间的自然特征来划分，同时阶段的划分要便于把问题转化成多阶段决策过程，如例题 3-1-1中，可将其划分成4个阶段，即K = 1，2，3，4。

2. 状态和状态变量：

某一阶段的出发位置称为状态，通常一个阶段包含若干状态。一般地，状态可由变量来描述，用来描述状态的变量称为状态变量。如例题 3-1-1中，C3是一个状态变量。

3. 决策、决策变量和决策允许集