数据结构域算法设计-实验项目五动态规划

《数据结构域算法设计-实验项目五动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验项目五　动态规划实验学时：2实验目的：动态规划（dynamicprogramming，DP）是解决多阶段决策问题的一种有效的数量化方法，难度比较大，技巧性也很强。Lindo/lingo是求解动态规划比较常用的软件之一，通过本实验，掌握动态规划模型在Lindo/lingo中的求解。实验要求：1.掌握动态规划的建模步骤及方法；2.掌握动态规划模型在Lindo/lingo转化及求解；3.学会动态规划的执行结果分析实验内容及步骤：例：如图5-1所示，某地要从A向F地铺设一条输油管道，各点间连线上的数字表示距离

2、。问应选择什么路线，可是总距离最短？　　　　　　　　　　　　　　　　　　　图5-1下面简单说明动态规划的求解建模过程，有助于下一步在Lindo/lingo中模型的表示，这是一个很重要的过程，建议读者不要跳过。动态规划方法求解时注意事项：（1）动态规划的三个基本要素：阶段、状态、决策。其中最关键的是状态的描述，最难的也是状态的设计，它关系到算法的时间、空间复杂度，也跟实现的复杂度息息相关。（2）动态规划的两个条件：最优子结构、无后效性，其中后效性往往容易被忽视。（3）动态规划本质是用空间换时间，在有大量重叠

3、子问题的时候其优势才能充分体现出来。上例的求解过程如下：（1）阶段与阶段变量：先把问题从中间站B，C，D，E用空间位置分成5个阶段，阶段用阶段变量k来描述，k=1,表示第一阶段，k=2表示第二阶段，…（2）状态与状态变量：每一阶段的左端点（初始条件）集合称为本阶段的状态（即开始的客观条件，或称阶段初态）。如第三阶段有四个状态S3=｛C1,C2，C3，C4｝,第四阶段有三个状态S4=｛D1,D2,D3｝,…描述过程状态的变量称为状态变量：用小写s1,s2,s3…表示第一，第二，第三…阶段的状态变量。当处在状

4、态C2时，我们可记s3=C2(3)决策与决策变量：如当处于C2状态时，下一步怎么走？如何选择路线？即如何决策。是走向D1，还是走向D2？当过程处于某一阶段的某一状态时，可以作出不同的决策（或选择），从而确定下一阶段的状态，这种决定（或选择）叫决策。如选择D2，记u3（C2）=D2即当处于C2状态时，下一步的决策为D2。其中uk(sk)表示第k阶段当状态处于sk时的决策变量。一般地，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。如D3(C2)=｛D1，D2｝显然，uk(sk)∈Dk(sk)。（4）

5、策略与最优策略：每一阶段产生一个决策，5个阶段的决策就构成一个决策序列：　　u1(s1)，u2(s2)，u3(s3)，u4(s4)，u5(s5)称为一策略。所谓策略是指按一定的顺序排列的决策组成的集合，也称决策序列。这里的最短路径成为最优策略。动态规划就是在允许策略集中选最优策略。（5）状态转移方程：是描述由第k阶段到第k+1阶段状态转移规律的关系式。sk+1=Tk(sk,uk)上例中状态转移方程为：sk+1=uk(sk)（6）指标函数与最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数。相当于动

6、态的目标函数，最后一个阶段的目标函数就是总的目标函数。它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段，从状态sk出发，采用决策uk时的效益，用dk(sk,uk)表示。最优指标函数是指从第k阶段状态sk采用最优策略到过程终止时的最佳效益值，用fk(sk)表示。例如：d（C2,D1）是指由C2出发，下一阶段的决策是D1的两点间的距离。即d（C2,D1）=4。f2(B1)表示从B1到F的最短距离。整个问题即为f1(A)=？在这里我们选择逆序递推法求解：倒退着从F向A走，每倒退一步，思想上问自己：“从现

7、在出发，退向何处？到F的距离最短？”我们分5步来解决问题：（1）k=5时求f5(s5)=？此时状态集S5=｛E1，E2｝，故分情况讨论，由E1到终点F的最短距离为f5(E5)=5同理，f5(E2)=3。故最优决策为：u5∗(E1)=F，u5∗(E2)=Fk=4时下求f4(s4)=？由于S4=｛D1,D2,D3｝下分四种情况进行讨论：（5）k=1时，S1=｛A｝再按计算顺序的反推可得最优策略：u1∗(A)=B1.u2∗(B1)=C2.u3∗(C2)=D2.u∗4(D2)=E2.u5∗(E2)=F从而得最优路

8、径：a58最短距离为：f1(A)=17。由上面的过程可以看出，在求解的各个阶段利用了第k段和第k+1段的如下关系：此递推关系称为动态规划的基本方程。式（7.2）称为边界条件。每步的计算过程及最路径如图5-2所示。　　　　　　　　　　图5-2当然本题也可用顺序法求解，但与逆序法无本质的区别。一般来说，当初始状态给定时，用逆序解法，当终止状态给定时，用顺序解法。若既给定了初始状态又给定了终止状态，则两种方法均可使用。下面用ling