当前位置：文档之家 › 第6章 动态规划(上)

第6章 动态规划(上)

  • 格式：ppt
  • 大小：984.50 KB
  • 文档页数：62

下载文档原格式

  / 62

合集下载

第6章动态规划

第6章动态规划

第6章 动态规划动态规划（Dynamic Programming ）是解决多阶段决策过程最优化的一种有用的数学方法。

它是由美国学者Richard .Bellman 在1951年提出的，1957年他的专著《动态规划》一书问世，标志着运筹学的一个重要分支－动态规划的诞生.动态规划也是一种将多变量问题转化为单变量问题的一种方法。

在动态规划中，把困难的多阶段决策问题变换成一系列相互联系的比较容易的单阶段问题一个个地求解。

动态规划是考察解决问题的一种途径 ,而不是一种特殊的算法，不像线性规划那样有统一的数学模型和算法（如单纯形法）.事实上，在运用其解决问题的过程中还需要运用其它的优化算法。

因此，动态规划不像其它方法局限于解决某一类问题,它可以解决各类多阶段决策问题。

动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。

在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。

许多规划问题用动态规划的方法来处理,常比线性规划或非线性规划更有效。

特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。

动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。

本教材主要介绍动态规划的基本概念、理论和方法,并通过典型的案例说明这些理论和方法的应用。

6.1动态规划的基本理论6.1.1多阶段决策过程的数学描述有这样一类活动过程,其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策,以使整个过程达到最佳的活动效果。

任何一个阶段(stage ，即决策点)都是由输入(input ）、决策（decision ）、状态转移律（transformation function )和输出(output )构成的，如图6-1（a ）所示.其中输入和输出也称为状态(state ）,输入称为输入状态，输出称为输出状态。

运筹学思考练习题答案

运筹学思考练习题答案

运筹学思考练习题答案第⼀章 L.P 及单纯形法练习题答案⼀、判断下列说法是否正确1. 线性规划模型中增加⼀个约束条件，可⾏域的范围⼀般将缩⼩，减少⼀个约束条件，可⾏域的范围⼀般将扩⼤。

(?)2. 线性规划问题的每⼀个基解对应可⾏域的⼀个顶点。

(?)3. 如线性规划问题存在某个最优解，则该最优解⼀定对应可⾏域边界上的⼀个点。

(?)4. 单纯形法计算中，如不按最⼩⽐值原则选取换出变量，则在下⼀个基可⾏解中⾄少有⼀个基变量的值为负。

(?)5. ⼀旦⼀个⼈⼯变量在迭代中变为⾮基变量后，该变量及相应列的数字可以从单纯形表中删除，⽽不影响计算结果。

(?)6. 若1X 、2X 分别是某⼀线性规划问题的最优解，则1212X X X λλ=+也是该线性规划问题的最优解，其中1λ、2λ为正的实数。

(?)7. 线性规划⽤两阶段法求解时，第⼀阶段的⽬标函数通常写为ai iMinZ x =∑(x ai 为⼈⼯变量)，但也可写为i ai iMinZ k x =∑，只要所有k i 均为⼤于零的常数。

(?)8. 对⼀个有n 个变量、m 个约束的标准型的线性规划问题，其可⾏域的顶点恰好为m n C 个。

(?)9. 线性规划问题的可⾏解如为最优解，则该可⾏解⼀定是基可⾏解。

(?)10. 若线性规划问题具有可⾏解，且其可⾏域有界，则该线性规划问题最多具有有限个数的最优解。

(?)⼆、求得L.P 问题121231425j MaxZ 2x 3x x 2x x 84x x 164x x 12x 0;j 1,2,,5=+++=??+=??+=?≥=的解如下： X ⑴=(0,3,2,16,0)T ;X ⑵=(4,3,-2,0,0)T ;X ⑶=(3.5,2,0.5,2,4)T ;X ⑷=(8,0,0,-16,12)T ; =(4.5,2,-0.5,-2,4)T ; X ⑹=(3,2,1,4,4)T ;X ⑺=(4,2,0,0,4)T 。

要求：分别指出其中的基解、可⾏解、基可⾏解、⾮基可⾏解。

北交942管理运筹学考纲

北交942管理运筹学考纲

1、单纯型法（第1、2章）概念和描述：线性规划问题的模型、对偶问题的模型、基变量、非基变量、解的形式（基解、基可行解、最优解、无解、无可行解）、影子价格判定：线性规划问题解的形式、单纯型表运算的规则、对偶变换的规则证明：线性规划问题的矩阵运算、对偶理论步骤：对偶单纯型法的步骤、敏感性分析的步骤计算：单纯型法、改进单纯型法、互补松弛定理的运用、对偶单纯型法、敏感性分析计算（C-r、b、A-ij、新增变量和约束）2、运输问题（第3章）概念和描述：运输问题的模型、产销不平衡问题模型描述判定：运输问题中基变量的个数、最优解判定（尤其是如何给出多个最优解）、求最小还是求最大步骤：表上作业法的步骤、最优解的步骤计算：产销不平衡问题、求最大的问题（看例3-5、09年真题）3、整数规划（第5章）概念和描述：整数规划的数学模型（相互排斥的计划、相互排斥的约束、指派问题）步骤：分枝定界法的步骤、匈牙利算法的步骤计算：分枝定界法、割平面法、指派问题不考：0-1型整数规划的全枚举法4、动态规划（第6章）计算：一维资源分配（离散、连续）、生产和存储问题（生产计划、不确定性采购）、背包问题（课本的例题有些复杂，看真题好些）、复合系统可靠度、排序（直接看例6-10）、设备更新问题。

以上问题都要清楚各自的模型描述、状态和决策变量取值描述、状态转移方程和指标函数形式不考：二维资源分配、货郎担问题5、图论（第7章）概念和描述：连通图、割集、最短路等问题的模型描述、可行流、最大流、饱和弧、非饱和弧、增广链、最小费用增广链证明：定理7.8步骤：Dijkstra算法的步骤、Floyd算法的的步骤、最长路算法的递推关系、寻找增广联的调整步骤、最小费用最大流问题的转换步骤计算：最短路（Dijkstra、Floyd）、最长路、最大流、最小费用最大流不考:寻找最小支撑树算法、图的矩阵表示、最短路另外两个算法、中国邮路问题6、排队论（第9章）判定：问题所属的排队类型、little公式的适用对象证明：用生灭过程的状态转移方程推导MM1、MM1N、MMC、MMCN的排队参数（MM1的证明考过，其他的最好也好，实在不行就把公式记下来背吧）计算：MM1、MM1N、MMC、MMCN、MD1、ME1、MM1中的最优服务率、MMC中最优服务台数不考：MM1N及顾客数为有限中的最优服务率、顾客源有限的排队系统其他不用看的章节：第4线性规划应用举例、第8章络计划（不考大题）、第10章存贮论课后习题不用全做，调自己认为经典的做做，在用胡的习题集对答案就可以了。

运 筹 学 课 件

运 筹 学 课 件

12/3 4
z
1 2
x4
x5 42
x3
2 3
x4
1 3
x5
4
新典式
主元化 为1，主 元所在
x2
1 2
x4
6
列的其 余元素
x1
2 3
x4
1 3
x5
4
化为0
观察最后一个典式，所有检验数均为非负， 故其对应的基本可行解为最优解，即
X * 4,6,6,0,0T z* 42
去掉引入变量，得原问题的最优解为：
运筹学课件
目录
运筹学概论 第一章 线性规划基础 第二章 单纯形法 第三章 LP对偶理论 第四章 灵敏度分析 第五章 运输问题 第六章 整数规划 第七章 动态规划 第八章 网络分析
第二章 单纯形法
(SM-Simplex Method)
1947年，美国运筹学家Dantzig提出，原理是 代数迭代。
单纯形法中的单纯形的这个术语，与该方法毫 无关系，它源于求解方法的早期阶段所研究的一 个特殊问题，并延用下来。
CB B1b B1b
z
CB B1N CN X N X B B1NX N
CB B1b B1b
上述方程组的矩阵形式为
10
0 I
CB
B1N B1N
CN
z XB XN
CB B1b B1b
上式的系数增广阵称为对应于基B的单纯形表：
T(B)
CB B1b B1b
0 I
CB
B1N B1N
CN
形式的LP问题，必须解决三个问题： ⑴初始基本可行解的确定； ⑵解的最优性检验； ⑶基本可行解的转移规则。 这里先放一下⑴，研究⑵和⑶，为此，

第6章-动态规划

第6章-动态规划
f*n(Sn)为从第n个阶段到终点的最短距离， f*n+1(Sn+1)为从第n+1个阶段到终点的最短距离， dn(Sn,Xn)为第n个阶段的距离，f*5(S5)为递推 的起点，通常为已知的。
求解过程
由最后一个阶段的优化开始，按逆向顺序逐步 向前一阶段扩展，并将后一阶段的优化结果带 到扩展后的阶段中去，以此逐步向前推进，直 至得到全过程的优化结果。
f1
(
A)
min
dd11
( (
A, A,
B1) B2 )
ff22((BB12))
min
4 9
9 11
13
d1( A, B3) f2 (B3)
5 13
其最短路线是A→ B1→C2 →D2 →E ，相应的决 策变量是u1(A)=B1
因此，最优策略序列是：
u1(A) =B1, u2(B1)=C2, u3(C2)=D2, u4(D2)=E
5 8 C2 4 6 4
4 C3 2
C3
D1 4 2 6
D2 9 7
D3 5
D4
E1 1 F
E2 2
E5
F
动态规划的逆序解法与顺序解法
逆序（递推）解法：即由最后一段到第一段逐步 求出各点到终点的最短路线,最后求出A点到E点 的最短路线。运用逆序递推方法的好处是可以始 终盯住目标,不致脱离最终目标。 顺序解法：其寻优方向与过程的行进方向相同， 求解时是从第一段开始计算逐段向后推进，计算 后一阶段时要用到前一段求优的结果，最后一段 的计算结果就是全过程的最优结果。
B1
A
4+9=13
d(u1)+f2
B2
B3
f1(s1) u1*

现代控制理论基础 第6章 线性系统的最优控制

现代控制理论基础 第6章 线性系统的最优控制
，
7
方法的比较
总的来说，当控制量无约束时，‘采用“变分法” ；当控制量有 约束时，采用“极小值原理” 或“动态规划”；如果系统是线性的， 采用“线性二次型”方法最好，因为，一方面，二次型指标反映了大 量实际的工程性能指标的要求；另方面，理论上的分析及求解较简单、 方便、规范，而且还有标准的计算机程序可供使用；得到的控制器易 于通过状态反馈实现闭环最优控制，工程实现方便。在实际的工程控 制中，目前线性二次型最优控制己得到了广泛的成功应用。
J 值为极值 J （最大值或最小值），这种泛函求极值的方法，实际上 就是数学上的“变分”问题，须采用数学中的“变分法” 。
5
采用直接变分法求解最优控制率，难于甚至“无法解决容许控 制属于闭集”的最优控制问题，所以受到实际工程应用上的限制， 例如，每台电动机都有最大功率的限制；船舶或飞机的操纵舵面 也有最大偏转角的限制。况且采用直接变分法设计出的系统，其 抗参数变化的能力，即系统的鲁棒性也不强。因此，工程应用上 有较小的实用价值。
线性系统二次型的最化控制，因为其性能指标具有明确的物理 意义，在大量的工程实际中具有代表性，而且最优控制率的求解 较简单，并具有统一的解析表达式，构成的最优控制系统具有简 单的线性状态反馈的型式，易于工程实现，所以在国内外实际的 工程中目前己得到广泛应用。本章主要介绍其基本概念、基本原 理和设计方法。
下面只介绍线性二次型最优控制的基本概念、求解原理及设 计中的一些主要结论。
8
第三节 线性二次型最优控制
一、控制对象数学模型
线性系统的状态空间表达式
x(t) A(t)x(t) B(t)u(t)
y(t) C(t)x(t)
式中，
n x(t) 为 维状态向量；
（6-4）

中石油华东《运筹学》2014年秋学期在线作业(三)答案

《运筹学》2014年秋学期在线作业（三）
一,单选题
1. （第6章)关于动态规划的如下说法中错误的是()；
A. 状态转移方程表明了各阶段之间状态的联系
B. 过程指标函数必须由阶段指标函数相加得到
C. 动态规划基本方程必须有边界条件
D. 动态规划中决策变量可以为连续变量也可以为离散变量
?
正确答案：B
2. (第5章)下列关于整数规划问题的说法，正确的是()；
A. 整数规划问题解的目标函数值优于其对应的线性规划问题的解的目标函数值
B. 部分变量都取整数的问题称之为纯整数规划问题
C. 全部变量都取整数的问题称之为纯整数规划问题
D. 分配问题不是整数规划问题
?
正确答案：C
3. 题目和选项如下图所示：
A.
B.
C.
D.
?
正确答案：B
4. (第5章)在用匈牙利法求解指派问题时，当独立零元素个数小于任务数（人数）时：下列说法正确的是()；
A. 用最少的直线划去所有的非独立的零元素
B. 剩余的元素非零元素都减去本行的最小元素
C. 为保证所有元素大于零，应在横线和竖线交汇格元素加上最小元素
D. 用最少的直线划去所有的独立零元素
?
正确答案：C
5. (第6章)用逆序法求解资源分配问题时，为保证独立性，状态变量取值一般为()；
A. 各阶段分配的资源数
B. 当前阶段开始时前部过程已分配的资源数
C. 当前阶段开始时剩余给后部过程的资源数
D. 资源的总数量
?。

运筹学第三版课后习题答案 (2)

运筹学第三版课后习题答案第一章：引论1.1 课后习题习题1a)运筹学是一门应用数学的学科，旨在解决实际问题中的决策和优化问题。

它包括数学模型的建立、问题求解方法的设计等方面。

b)运筹学可以应用于各个领域，如物流管理、生产计划、流程优化等。

它可以帮助组织提高效率、降低成本、优化资源分配等。

c)运筹学主要包括线性规划、整数规划、指派问题等方法。

习题2运筹学的应用可以帮助组织提高效率、降低成本、优化资源分配等。

它可以帮助制定最佳的生产计划，优化供应链管理，提高运输效率等。

运筹学方法的应用还可以帮助解决紧急情况下的应急调度问题，优化医疗资源分配等。

1.2 课后习题习题1运筹学方法可以应用于各个领域，如物流管理、生产计划、供应链管理、流程优化等。

在物流管理中，可以使用运筹学方法优化仓储和运输的布局，提高货物的运输效率。

在生产计划中，可以使用运筹学方法优化产品的生产数量和生产周期，降低生产成本。

在供应链管理中，可以使用运筹学方法优化订单配送和库存管理，提高供应链的效率。

在流程优化中，可以使用运筹学方法优化业务流程，提高整体效率。

习题2在物流管理中，可以使用运筹学方法优化车辆的调度和路线规划，以提高运输效率和降低成本。

在生产计划中，可以使用运筹学方法优化生产线的安排和产品的生产量，以降低生产成本和提高产能利用率。

在供应链管理中，可以使用运筹学方法优化供应链各个环节的协调和调度，以提高整体效率和减少库存成本。

在流程优化中，可以使用运筹学方法优化业务流程的排布和资源的分配，以提高流程效率和客户满意度。

第二章：线性规划基础2.1 课后习题习题1线性规划是一种数学优化方法，用于解决包含线性约束和线性目标函数的优化问题。

其一般形式为：max c^T*xs.t. Ax <= bx >= 0其中，c是目标函数的系数向量，x是决策变量向量，A是约束矩阵，b是约束向量。

习题2使用线性规划方法可以解决许多实际问题，如生产计划、供应链管理、资源分配等。

第6章 动态规划

第6章动态规划判断06100011判断：在动态规划模型中，问题的阶段数等于问题中的子问题的数目；06100021判断：动态规划中，定义状态时应保证在各个阶段中所作决策的相互独立性；06100031判断：）动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策；06100041判断：对一个动态规划问题，应用顺推或逆推解法可能会得出不同的最优解；06100051判断：动态规划计算中的“维数障碍”主要是由于问题中阶段数的急剧增加而引起的；06100061判断：）假如一个线性规划问题含有5个变量和3个约束，则用动态规划方法求解时将划分为3个阶段，每个阶段的状态将由一个5维的向量组成；06100071判断：任何一个多阶段决策过程的最优化问题，都可以用非线性规划模型来描述。

06100081判断：动态规划问题如果按状态转移率区分,可分成确定性的与随机性的.简答06200011简答：一个N阶段的决策过程具有哪特征？06200021简答：试述动态规划的优点。

06200031简答：试述最优化原理的内容06200041简答：试述动态规划数学模型的四种类型.计算题最短路问题06301012设某厂自国外进口一步精密机器，由机器制造厂至出口港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，期间的运输成本如下图所示，试求运费最低的路线。

06301022、某工厂从国外引进一台设备，由A到G港口有多条通路可供选择，其路线及费用如下图所示。

现要确定一条从A到G的使总费用最小的路线。

请将该问题描述成一个动态规划问题，然后求其最优解。

资源分配06302012有一部货车每天沿着公路给四个零售店卸下6箱货物，如果各零售店出售该货物06302022设有某种肥料共6个单位重量，准备供给四块粮田用，其每块粮田施肥数量与增06302033某公司打算向承包的三个营业区增设六个销售店，每个营业地区至少增设一个，从各区赚取的利润与增设的销售店个数有关，其数据如下表所示。

运筹学教材课件(第四章动态规划)


最优解的存在性
对于多阶段决策问题，如果每个 阶段的决策空间是有限的，则存 在最优解。
最优解的唯一性
对于某些多阶段决策问题，可能 存在多个最优解。在这种情况下， 我们需要进一步分析问题的性质 和约束条件，以确定最优解的个 数和性质。
最优解的稳定性
在某些情况下，最优解可能受到 参数变化的影响。我们需要分析 最优解的稳定性，以确保最优解 在参数变化时仍然保持最优。
VS
详细描述
排序问题可以分为多种类型，如冒泡排序 、快速排序、归并排序等。动态规划可以 通过将问题分解为子问题，逐一求解最优 解，最终得到全局最优解。在排序问题中 ，动态规划可以应用于求解最小化总成本 、最大化总效益等问题。
04
动态规划的求解方法
逆推法
逆推法
从问题的目标状态出发，逆向推算出达到目标状态的 最优决策，直到达到初始状态为止。
案例二：投资组合优化问题
要点一
总结词
要点二
详细描述
投资组合优化问题是动态规划在金融领域的重要应用，通 过合理配置资产，降低投资风险并提高投资收益。
投资组合优化问题需要考虑市场走势、资产特性、风险偏 好等多种因素，通过动态规划的方法，可以确定最优的投 资组合，使得投资者在风险可控的前提下，实现收益最大 化。
详细描述
在背包问题中，给定一组物品，每个物品都有一定的重量和价值，要求在不超过背包容量的限制下， 选择总价值最大的物品组合。通过动态规划的方法，可以将背包问题分解为一系列子问题，逐一求解 最优解。
排序问题
总结词
排序问题是动态规划应用的另一个重要 领域，主要涉及到将一组元素按照一定 的顺序排列，以达到最优的目标。
本最小化和效率最大化。
感谢您的观看
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

动态规划函数：
cost[i ] min{cij cost[ j ]}
i j n
path[i ] 使c ij cost[ j ]最小的 j
算法设计与分析 徐浩
步骤描述如下：
例：
4 0 3 1
9 6 8 7
4
6 8 6 6
5 7 7 9 8 5
算法设计与分析 徐浩
1
2 1 3 4 8 7
path[ 1 ] 5
i 0 ： cost [ 0 ] min { c 01 cost [ 1 ] , c02 cost [ 2 ] , c 03 cost [ 3 ] }
min { 4 15 , 1 14 , 3 13} 15
path[ 0 ] 2
route [0] 0
d (3, {2,4}) min{4 6,2 12} 10
d (4,{2,3}) min{ 7 8,5 9} 14
d (1,{2,3,4}) min{ 3 7,6 10,7 14} 10
算法设计与分析 徐浩
求解示意图
d(1,{2,3,4})
d(2,{3,4})
c24 d (4, ) c24 c41 6
c42 d (2, ) c42 c21 12
c23 d (3, ) c23 c31 8
c32 d (2, ) c32 c21 9
d (2,{3,4}) min{2 5,3 11 } 7
p(2,21)
s(2,22)
s(2,2r2)
s(2,r11)
s(2,r12)
s(2,r1r2)
赖以决策的策略或目标，称为动态规划函数 最优状态s(2,22),倒推得s ( 2, 22 ) p ( 2, 22 ) s ( 1, 2 ) p ( 1, 2 ) s 0 最优决策序列 p ( 1, 2 ) p ( 2, 22 ) 状态转移序列 s 0 s ( 1, 2 ) s ( 2, 22 )
path[ 4 ] 8
i 3： cos t [ 3 ] min { c35 cos t [ 5 ] , c36 cos t [ 6 ] } min { 4 9 , 7 8 } 13
path[ 3 ] 5
i 2 ： cos t [ 2 ] min { c 23 cos t [ 3 ] , c 24 cos t [ 4 ] , c 25 cos t [ 5 ] , c 26 cos t [ 6 ]}
算法设计与分析 徐浩
算法实现：
struct NODE { /* 邻接表结点的数据结构 */ int v_num; /* 邻接顶点的编号 */ Type len; /* 邻接顶点与该顶点的费用 */ struct NODE *next; /* 下一个邻接顶点 */ }; struct NODE node[n]; /* 多段图邻接表头结点 */ Type cost[n]; /* 在阶段决策中,各个顶点到收点的最小费用 */ int route[n];/* 从源点到收点的最短路径上的顶点编号 */ int path[n]; /* 在阶段决策中,各个顶点到收点的最短路径上的前 方顶点编号 */
可以产生一种新状态,见下图
算法设计与分析 徐浩
S0
p(1,1)
p(1,2)
p(1,r1)
s(1,1)
s(1,2)
s(1,r1)
p(2,11)
p(2,12)
p(2,1r2)
p(2,21)
p(2,22)
p(2,2r2)
p(2,r11)
p(2,r12)
p(2,r1r2)
s(2,11)
p(2,12)
s(2,1r2)
d(3,{2,4})
d(4,{2,3})
d(3,{4}) d(4,{3}) d(2,{4}) d(4,{2}) d(2,{3}) d(3,{2})
d(4,φ )
d(3,φ )
d(4,φ )
d(2,φ )
d(3,φ )
d(2,φ )
花费的时间仍是指数时间,但是比穷举法要少
T T1 n 2 2n 1 (n 2 2n )
5
3
6
i 8： cos t [ 8 ] c89 cos t [ 9 ] 3 0 3
path[ 8 ] 9
i 7 ： cos t [ 7 ] c 79 cos t [ 9 ] 7 0 7
path[ 7 ] 9
i 6 ： cost [ 6 ] min { c 67 cost [ 7 ] , c 68 cos t [ 8 ] } min { 6 7 , 5 3 } 8


算法设计与分析 徐浩
动态规划的决策过程
最后阶段形成最优决策，然后向前回溯 直到初始阶段，决策的具体结果和状态 转移由初始阶段开始计算，向后递归迭 代。 实例：货郎担问题
3 6 7 5 2 3 C (cij ) 6 4 2 3 7 5
算法设计与分析 徐浩
算法6.1 多段图的动态规划算法 输入：多段图邻接表头结点node[],顶点个数n 输出：最短路径费用,最短路径上的顶点编号顺序route[] 1. template <class Type> 2. #define MAX_TYPE max_value_of_Type 3. #define ZERO_TYPE zero_value_of_Type 4. Type fgraph(struct NODE node[],int route[],int n) 5. { 6. int i; 7. struct NODE *pnode; 8. int *path = new int[n]; 9. Type min_cost,*cost = new Type[n]; 10. for (i=0;i<n;i++) { 11. cost[i] = MAX_TYPE; path[i] = -1; rouet[i] = 0; 12. } 13. cost[n-1] = ZERO_TYPE; 14. for (i=n-2;i>=0;i--) { 15. pnode = node[i]->next;
策略
算法设计与分析 徐浩
最终状态
pn
sn
初始状态
最优性原理：解决这类问题多阶段决策特性， 无论过程的初始状态和初始决策如何，其余决 策必须相对初始决策所产生的状态，构成一个 最优决策序列。 每一阶段决策仅与前一阶段产生的状态有关， 与如何达到状态的方式无关，每一阶段可作 为一个子问题处理。每阶段决策可以有多个 决策选择，达到多个状态，但只有一个决策 最优。 作出如下假定：一种状态作出多种决策，每种决策
算法设计与分析 徐浩
16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. }
算法设计与分析 徐浩
动态规划算法与分治法类似，其基本思想也是将待求解 问题分解成若干个子问题
T(n)
=
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
算法设计与分析 徐浩
算法总体思想
但是经分解得到的子问题往往不是互相独立的。不同子 问题的数目常常只有多项式量级。在用分治法求解时， 有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找 出已求得的答案，就可以避免大量重复计算，从而得到 多项式时间算法。
T(n)
n/2
T(n/4) T(n/4) T(n/4)
=
n
n/2
n/2 n/2
T(n/4)
T(n/4)
T(n/4) T(n/4) T(n/4)T(n/4)T(n/4) T(n/4)
算法设计与分析 徐浩
动态规划基本步骤
找出最优解的性质，并刻划其结构特征。 递归地定义最优值（动态规划函数）。 以自底向上的方式计算出最优值（回溯/迭 代）。 根据计算最优值时得到的信息，构造最优 解。
min {1 13, 6 9 , 7 9 , 8 8 } 14
path[ 2 ] 3
i 1： cos t [ 1 ] min { c14 cos t [ 4 ] , c15 cos t [ 5 ] } min { 9 9 , 6 9 } 15
费用矩阵
3 6 7 5 2 3 C (cij ) 6 4 2 3 7 5
算法设计与分析 徐浩
d (1,{2,3,4}) min{ c12 d (2,{3,4}), c13 d (3,{2,4}), c14 d (4,{2,3})}
path[ 6 ] min { c57 cost [ 7 ] , c58 cost [ 8 ] } min { 8 7 , 6 3 } 9
path[ 5 ] 8
i 4 ： cost [ 4 ] min { c 47 cost [ 7 ] , c 48 cost [ 8 ] } min { 5 7 , 6 3 } 9
i 1
n
算法设计与分析 徐浩
多段图的最短路径问题
多段图的决策过程
定义：给定有向连通赋权图G=(V,E,W),如果把顶点集合V划分为k个不相交的 子集Vi，1≤i≤k,k≥2,使得E中的任何一条边（u,v），必有u∈Vi,v ∈Vi+m,m ≥1,则称为多段图。令|V1|=|Vk|=1，s为源点，t为收点。多段图最 短路径问题是求从源点s到达收点t的最小花费的通路。S编号为0，t编号为n1，E中任意一条边（u,v），u编号小于v。 cost[i]：存放顶点i到收点t的最小花费 path[i]：存放顶点i到收点t的最小花费通路上的前方顶点编号。 route[n]：存放从源点s出发到达收点t的最短路径上的顶点编号