题库(文件较多)(5)

6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 1 2 3 2 2 9 10 9 10

TSP.OUT 1 2 3 4 4 5 16 1 2 1 5 4 5 11 1 1 19

丢失的数列（LOSE）

提交文件名：LOSE.PAS 问题描述：

小学生永琪刚刚做完她的作业。今天老师给她几个由若干个互不相同的整数组成的列表，作业是计算出每个列表中每一对整数的和。为了防止抄袭，老师给学生们的列表是各不相同的，因此，她只能自己独立完成作业。由于永琪在算术方面并不太好而且老师给的列表又比较多，这次作业的确是一项坚难的事。

在她做完作业后，永琪就出门与她的朋友们一走玩去了。当她回到家时，她发现列表不见了，只剩下她写下答案的纸张。由于老师要检查永琪作业，她必须在下一节课交回这些列表。到底是谁拿走了列表呢？原来是她的妈妈把这些列表当成垃圾，并将它们扔进了垃圾桶倒掉了。于是她迅速跑到屋外垃圾桶，唉！垃圾收集工又已经倒空了。这下该怎么办呢？永琪犹豫了一下，心想一定会有办法恢复这些列表，她打电话给你，请求帮助。

在这个问题中，你要解决永琪的烦恼。对于她写下的每个列表中的各个和，你的程序要恢复这个列表中的每个互不相同的整数。由于永琪不擅长算术，可能存在一系列和它们是无法恢复的，也就是说，如果不存在一个整数序列，它能产生这些和数，你的程序输出\－1\。 输入文件（LOSE.IN）：

输入文件包含T组数据。输入文件的第一行包含一个整数T，表示测试数据的组数，也就是永琪从她的老师那里拿到的列表的数目。每个数据的第一行为整数N（2

对于每个测试数据，输出仅有一行，如果有解，以递增顺序输出这N个互不相同的整数，否则输出无解。整数之间用一个空格隔开。 输入输出样例： LOSE.IN 3 4

4 5 7 10 12 13 3 2 5 6

21

5

3 4 5 5 6 6 7 7 8 9

LOSE.OUT 1 3 4 9 -1 1 2 3 4 5

第三讲 动态规划

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

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

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

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

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

22

分析：把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. 决策、决策变量和决策允许集合：

在对问题的处理中作出的每种选择性的行动就是决策。即从该阶段的每一个状态出发，通过一次选择性的行动转移至下一阶段的相应状态。一个实际问题可能要有多次决策和多个决策点，在每一个阶段的每一个状态中都需要有一次决策，决策也可以用变量来描述，称这种变量为决策变量。在实际

23

问题中，决策变量的取值往往限制在某一个范围之内，此范围称为允许决策集合。如例题 3-1-1中，F3（C3）就是一个决策变量。 4．策略和最优策略：

所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量所组成的有序总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略成为最优策略。 5. 状态转移方程

前一阶段的终点就是后一阶段的起点，对前一阶段的状态作出某种决策，产生后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。

在上面介绍的动态规划基本概念的基础上，可以得到动态规划的基本模型构成如下： 1． 确定问题的决策对象。 2． 对决策过程划分阶段。 3． 对各阶段确定状态变量。

4． 根据状态变量确定费用函数和目标函数。

5． 建立各阶段状态变量的转移过程，确定状态转移方程。

三、最优化原理与无后效性

上面已经介绍了动态规划模型的基本组成，现在需要解决的问题是：什么样的“多阶段决策问题”才可以采用动态规划的方法求解。

一般来说，能够采用动态规划方法求解的问题，必须满足最优化原理和无后效性原则： 1.

动态规划的最优化原理。作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，而非最优解对问题的求解没有影响。在例题 3-1-1最短路径问题中，A到E的最优路径上的任一点到终点E的路径，也必然是该点到终点E的一条最优路径，即整体优化可以分解为若干个局部优化。 2.

动态规划的无后效性原则。所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响过程未来的演变。在例题 3-1-1最短路径问题中，问题被划分成各个阶段之后，阶段K中的状态只能由阶段K+1中的状态通过状态转移方程得来，与其它状态没有关系，特别与未发生的状态没有关系，例如从Ci到E的最短路径，只与Ci的位置有关，它是由Di中的状态通过状态转移方程得来，与E状态，特别是A到Ci的路径选择无关，这就是无后效性。

由此可见，对于不能划分阶段的问题，不能运用动态规划来解；对于能划分阶段，但不符合最优化原理的，也不能用动态规划来解；既能划分阶段，又符合最优化原理的，但不具备无后效性原则，还是不能用动态规划来解；误用动态规划程序设计方法求解会导致错误的结果。

第二节 动态规划的设计与实现 一、动态规划设计方法的一般模式

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态；或倒过来，从结束状态开始，通过对中间阶段决策的选择，达到初始状态。这些决策形成一个决策序列，同时确定了完成整个过程的一条活动路线，通常是求最优活动路线。

动态规划的设计都有着一定的模式，一般要经历以下几个步骤：

1． 划分阶段：按照问题的时间或空间特征，把问题划分为若干个阶段。在划分阶段时，注意划分后的阶

段一定是有序的或者是可排序的，否则问题就无法求解。

24

2． 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，

状态的选择要满足无后效性。

3． 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的

状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可以写出。但事实上常常是反过来做，根据相邻两段的各个状态之间的关系来确定决策。

4． 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 5． 程序的设计实现：一旦设计完成，实现就会非常简单。下面我们给出从初始状态开始，通过对中间阶

段决策的选择，达到结束状态，按照阶段、状态和决策的层次关系，写出的程序流程的一般形式：

所有状态费用的初始化；

for i := 阶段最大值-1 downto 1 do {倒推每一个阶段}

for j := 状态最小值to 状态最大值do {枚举阶段i的每一个状态}

for k := 决策最小值to 决策最大值do {枚举阶段i中状态j可选择的每一种决策} begin

f[i,j] ← min{d[i,j,k] + f[i+1,k]}

end；

输出f[1,1];

例 3-1-1对应的Pascal程序如下： var

d : array[1..4,1..4,1..4] of byte; f : array[1..5,1..4] of byte; i,j,k,min : byte; begin

fillchar(d,sizeof(d),0); d[1,1,1] := 5; d[1,1,2] := 3;

d[2,1,1] := 1; d[2,1,2] := 6; d[2,1,3] := 3; d[2,2,2] := 8; d[2,2,4] := 4; d[3,1,1] := 5; d[3,1,2] := 6; d[3,2,1] := 5; d[3,3,3] := 8; d[3,4,3] := 3; d[4,1,1] := 3; d[4,2,1] := 4; d[4,3,1] := 3;

fillchar(f,sizeof(f),255); f[5,1] := 0;

for i := 4 downto 1 do for j := 1 to 4 do for k := 1 to 4 do if d[i,j,k] <> 0 then

if f[i,j] > d[i,j,k]+f[i+1,k] then f[i,j] := d[i,j,k]+f[i+1,k]; writeln(f[1,1]); readln;

25

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库题库(文件较多)(5)在线全文阅读。