数据结构与算法动态规划课件

第7章动态规划

动态规划概述数塔最小代价子母树非优化问题实例单起点最短路径问题

Warshall传递闭包算法完全最短路径问题的Floyd算法最优二叉查找树

01背包问题本章习题动态规划概述

动态规划概述动态规划（DynamicProgramming），在20世纪50年代由美国数学家RichardBellman（理查德.贝尔曼）提出，作为多阶段决策过程最优化的一种通用算法设计法，不仅解决特定类型的最优化问题，也包括某些非最优化问题。多阶段决策过程最优化诸多实际问题：有多个解，但要找到最优解。穷举法通过找出全部解，再从中找出最优解。对于那些计算复杂度高的如组合问题，找出其全部解所耗费的计算时间往往不可接受！为降低求解难度，把求解过程分为一系列阶段，各个阶段按最优性原则计算，在最后阶段可得最优解。包括：分段、求解两大步。——不能段化的问题不能用动态规划法求解。最优性原则阶段1阶段2......阶段n求解算法求解算法求解算法多阶段决策过程动态：求解算法施加的状态是变化的。当前状态只与直接前趋有关，对直接前趋施加求解算法，成为当前状态。最优性原则

(PrincipleofOptimality):问题的最优解，是由其子问题的最优解组成。特定问题该原则不一定满足（罕见），因此，有必要检查该原则的适用性。某些多阶段决策问题本身没有最优化要求，如后面的中国象棋马从棋盘上一点移到另一点的全路径问题，又如计算裴波那契序列的动态规划算法，都属于非最优化问题的动态规划法。动态规划法的特点：1.分阶段计算。对最优化问题，各阶段满足最优性原则。2.一般用自顶向下分析（规模减小），自底向上实现（规模增加）。计算过程：一阶段一阶段地向前推进，直到最终状态。数塔

数塔有一个三角形数塔如图。求一条自塔顶到塔底的路径，该路径上节点值之和最大。（注意动态规划法与穷举法、贪婪法的区别）贪婪算法：从塔顶到塔底，13+12+16+15+24=80问题分段：每一级台阶划分为一个阶段——多阶段决策优化问题。逐段计算：当前问题的最优解由各子问题的最优解组成。

如：max(12+6,7+6)=18，max(40+18,40+27)=67,......5级4级3级2级1级1827393267465578679113111274014161582467131211数塔问题：动态规划法与穷举法效率比较

数塔：动态规划法与穷举法的时间效率比较输入规模：为便于分析，选数塔层数k,k>0基本操作：加法运算效率类别：无最佳、最差（均从塔顶到塔底）增长函数T(k)：各层节点数：1,2,3,4,5,......

节点的总数：1,3,6,10,15,

......

数塔层数k：1,2,3,4,

5,......

路径总数t：0,2,

4,8,16,......t=2k-1,k>01.穷举法：T(k)=(k-1)2k-1，k>0指数型本例k=5，每条路径5个节点做k-1=4次加法，共64次。2.动态规划法：（层节点数=层数）塔底向塔顶计算，第k层加法总数为第k-1层的节点数×2：

T(k)=2×(k-1+...+3+2+1)=k(k-1),k>0平方型本例k=5，加法总数2×(4+3+2+1)=20次最小代价子母树

最小代价子母树

有n≥2堆沙子，重量向量W=(w1,...wn)，将它们归并为1堆。规则：只能将相邻2堆归为1堆，经过n-1次归并后成为1堆。要求：找到代价最小的归并方案。

代价：新产生沙堆的质量和。代价最小的归并树即最小代价子母树。动态规划法求解：问题分段：将每次归并划分为一个阶段，共n-1个阶段。逐段计算：自底向上（规模增大n=2,3,...,n-1）n=2：1种归并法即2合1.n=3：2种归并法，第1种归并法如图，前1堆后2堆c(i,j)——从第i堆到第j堆的代价和w(i,j)——从第i堆到第j堆的重量和c(1,3)=15+28=43=c(2,3)+w(1,3)13781528序号1

2313781621418n=7最小代价子母树(续1)n=4n=3：第2种归并法，前2堆后1堆n=4：有3大类归并法。前1堆后3堆、前2堆后2堆、前3堆后1堆

3堆又有2种归并法，共5小类归并法。

前1堆情况1：78163115序号1

2341344c(1,4)=15+31+44=90=c(2,4)+w(1,4)c(1,3)=20+28=48=c(1,2)

+w(1,3)n=3最优归并方案：c(1,3)=min{c(2,3),c(1,2)}+w(1,3)13782028序号1

23最小代价子母树(续2)n=4n=4：前1堆情况2：781624311344序号1

234c(1,4)=24+31+44=99=c(2,4)+w(1,4)n=4：前2堆781624201344序号1

234c(1,4)=20+24+44=88

=c(1,2)+c(3,4)+w(1,4)最小代价子母树(续3)n=4n=4：前3堆情况1781620281344序号1

234c(1,4)=20+28+44=92

=c(1,3)+w(1,4)n=4：前3堆情况2781615281344序号1

234c(1,4)=15+28+44=87=c(1,3)+w(1,4)最小代价子母树(续4)n=4【归纳】n=4（3大类归并方案）

c(1,4)=min{c(2,4),c(1,2)+c(3,4),c(1,3)}+w(1,4)

前1堆前2堆前3堆【推广】对于任意的n≥2（可设计递归算法：自顶向下计算）c(1,n)=min{c(2,n),c(1,2)+c(3,n),c(1,3)+c(4,n),...,c(1,n-1)}+w(1,n)

前1堆前2堆前3堆......前n-1堆上式称动态方程——以方程形式给出的动态规划算法。很多动态规划算法并不能以方程形式给出。非最优化问题实例

非最优化问题实例中国象棋“马”的路径

——在m×n棋盘上，求：马从P跳到Q的所有路径。654321654321654321另可用回溯法求解递推求解中的交叠子问题

递归算法之重复计算交叠子问题【实例】计算裴波那契数的递归算法

F(n)=F(n-1)+F(n-2)，n>1F(0)=0,F(1)=1考察F(5)

计算过程，递归树表示F(5)F(4)F(3)F(2)F(3)F(1)F(2)F(1)F(0)F(0)F(1)F(2)F(1)F(0)F(1)计算F(5)要重复计算F(2)、F(3)，降低了时间效率——交叠子问题重复计算。动态规划法：自底向上计算依次计算F(0),F(1),F(2),...,F(n)一次，各次计算结果存入数组，最后一个元素就是F(n).——一个循环即可实现。单起点最短路径问题

单起点最短路径问题（区别于完全最短路径问题）单起点（单源）最短路径问题——

给定一个连通图（有向或无向），找起始顶点到结束顶点的最短路径。完全最短路径问题——找每个顶点到其他所有顶点的最短路径。分段：顶点集分为k个不相交子集Vd,1≤d≤k,k≥2,级内顶点不相邻任一条边(u,v)，u∈Vd+m,

v∈Vd

,m≥1.|V1|=|Vk|=1段内顶点相邻如何处理？12345678910图示算法过程：红色数字为各阶段结果（最优性原则）源点收点841210819171316V5V4V3V2V1分段k=5k=4k=3k=2k=1计算方向Warshall传递闭包算法Warshall传递闭包算法传递闭包1234有向图邻接矩阵传递闭包（待求）n个顶点有向图的传递闭包定义为一个n阶布尔矩阵R：若从顶点i到j存在路径R[i][j]=1,否则R[i][j]=0.例如R[2][2]

=1——存在路径2412.传递闭包给出：各顶点是否存在路径（任意长度）。

DFS或BFS生成传递闭包（R初始化为0）任一顶点k出发，将DFS或BFS遍历能访问到的顶点置1（第k行）。——遍历结束，可能会存在没访问到的顶点（非连通或无路径）。从每个顶点出发遍历，即可生成图的传递闭包。由于该方法对有向图遍历多次，时间效率不高——希望找到更好的算法！Warshall算法生成传递闭包Warshall（沃思霍尔）算法生成传递闭包问题分段：传递闭包的规模n分段。

逐段计算：k=1,2,...,n

计算一系列k阶矩阵R(k)来构造最终

n阶传递闭包R(n)：

R(0)→R(1)→...→R(k)→...→R(n-1)

→R(n)

初始矩阵

中间矩阵

传递闭包R(k)由R(k-1)计算：

R(0)——不允许路径中包含任何中间顶点（邻接矩阵）

R(1)——允许路径中包含1个中间顶点，编号1R(2)——允许路径中包含2个中间顶点，编号1，2R(k)——允许路径中包含k个中间顶点，编号1，2，...，k

R(n)

——允许路径中包含全部n个顶点

R(k)

相对R(k-1)，路径中允许增加一个顶点。因此，可包含更多的1.——增加前为1的增加后依然为1.举例说明Warshall算法生成传递闭包的过程举例说明Warshall算法生成传递闭包的过程1234路径中不允许包含中间顶点。加框行列用于计算矩阵R(1)：框内1元素所在行列元素置10变1规则：R(1)[4][2]=1

路径中允许包含第一个顶点作为中间顶点，允许包含编号不大于1的中间顶点（即1）新增1条路径：412（原有41

12）加框行列用于计算矩阵R(2)路径中允许包含前2个顶点作为中间顶点，即允许包含编号不大于2的中间顶点（即12）。新增2条路径：124，4124框起来的行和列用于计算后继矩阵R(3)举例说明Warshall算法生成传递闭包的过程（续）路径中允许包含前3个顶点作为中间顶点，即允许包含编号不大于3的中间顶点（123）没有新增路径。框内元素计算矩阵R(4)路径中允许包含前4个顶点作为中间顶点，即允许包含编号不大于4的中间顶点（1234）新增5条路径。或与和1或为1，和0与为0行列看作比特串完全最短路径问题的Floyd算法

完全最短路径问题的Floyd（弗诺依德）算法给定一个带权连通图（有向或无向），要求找出从每个顶点到其他所有顶点的距离——最短路径的长度。权重矩阵与距离矩阵动态规划法Floyd算法：非常类似Warshall算法。

要求：不含长度为负的回路。123426713带权有向图权重矩阵距离矩阵（待求）不包含起始顶点和终止顶点是同一个顶点的回路即认为自己到自己距离最短为0（对角元素=0）举例说明Floyd算法过程

举例说明Floyd算法过程初始为权重矩阵。加框的行列用于计算矩阵

D(1)：框内非无穷大元素相加，遵循元素的改写规则：新元素值比原元素值小，用新值改写。路径中允许包含编号不大于2的中间顶点。新增1条路径：321.框内元素计算D(3)问：为何D(2)[3][3]=0，非7+5=12？路径3213答：对角元=0，自己到自己距离最短。所以，此元素不被改写。路径中允许包含编号不大于1的中间顶点。新增2条路径：413,213.框内元素计算D(2)123426713举例说明Floyd算法过程（续）路径中允许包含编号不大于3的中间顶点。新增2条路径132，432.框内元素计算D(4)路径中允许包含编号不大于4的中间顶点。没有新增路径，有一条更短路径：341问：下划线元素为什么没有被改写？最优二叉查找树

最优二叉查找树最优BST

要求：整棵BST的平均比较次数

最少。优点：查找效率高，平均效率为logn型，最坏为线性（链）。蛮力法找最优BST（举例说明）已知：4个键{

a1,a2,a3,a4}，出现概率依次为{0.1,0.2,0.4,0.3}要求：构造最优BST回顾：BST的构造不唯一数量：n>0个键的BST总数=第n个卡塔兰数算法：穷举计算每个BST的平均比较次数，选出比较次数最少的。以4n/n1.5速度→∞举例说明：解最优BST问题的蛮力策略（穷举法）计算BST平均比较次数——统计平均选两棵BST计算，不一定最优a1a2a3a40.10.20.40.3比较1次比较2次比较3次比较4次a1a2a3a40.10.20.40.3比较1次比较2次比较3次【上图】0.1×1+0.2×2+0.4×3+0.3×4=2.9【下图】

0.2×1+0.1×2+0.4×2+0.3×3=2.1结论：一定存在平均比较次数最少的BST

动态规划法生成最优BST算法原理

动态规划法生成最优BST算法设计问题

n个键，查找概率，生成最优BST

使整棵树的平均查找次数C[1,n]→min（耗费）说明

C[i,j]表示构成BST的耗费，1≤i≤j≤n,树选择其中键作根，其左子树，右子树分段

——按规模n分段：

1→2→3→......→n-1→n——逐段构造最优BST.逐段计算

C[1,2]→C[1,3]→......→C[1,n]

要求：选择k

使得整棵树的平均查找次数C[i,j]→min

——左右子树递归执行这样的根生成过程。升序排序动态规划法生成最优BST算法原理（续）akpk最优BST最优BST根层L(ak)=1k-1=i：左子树缩为单节点k+1=j：右子树缩为单节点

k<i：左子树为空树

k>j：右子树为空树1≤i≤j≤n递推计算式举例说明：动态规划法生成最优BST过程【例】动态规划法生成最优BST例：4个键{a1,a2,a3,a4}，出现概率依次为{0.1,0.2,0.4,0.3}求：构造包含这4个键的最优BST（n=4）解：逐段计算：C[1,2]→C[1,3]→......→C[1,n]（本例n=4）k——根的下标。C[2,3]=0.8

的计算在下页12两个键123三个键举例说明：动态规划法生成最优BST过程（续1）

举例说明：动态规划法生成最优BST过程（续1）计算公式：23两个键最终结果1234键34两个键举例说明：动态规划法生成最优BST过程（续2）

举例说明：动态规划法生成最优BST过程（续2）计算公式：最终结果1234键234三个键将各阶段计算结果用

主表C

和

根表R

描述如下：动态规划算法：主表C和根表K各阶段计算结果用主表C和根表R描述

——计算时有j=0，j从0开始编号。

4个键{a1,a2,a3,a4}的出现概率依次为{0.1,0.2,0.4,0.3}j=01234i=100.10.41.11.7200.20.81.4300.41.0400.350主表C[i,j]各段计算：如

C[2,4]=1.4箭头表示一对求和元素，将最小和与当前节点概率和

(p2+p3+p4)相加：C[2,4]=0.5+(0.2+0.4+0.3)=1.4，如此计算C[i,j],1≤i＜j≤n=4实际计算时i、j的范围

i:1～n-1，j:2～n，红色数字表示。j=01234i=112332233333445根表R[i,j]动态规划法算例的计算结果图本例最优BSTj=01234i=112332233333445根表R[i,j]根表知，4个键的最优根下标为3即a3，左子树为a1a2右子树为a4，左子树的结构是什么？再看根表，a1a2构成的最优子树根是a2，因为a1<a2，所以，1键是2键的左节点。a10.1a30.4a40.30.2a2动态规划法生成最优BST算法

动态规划法生成最优BST算法j=01234i=100.10.41.11.7200.20.81.4300.41.0400.350立方型效率R[i,j]可以限定在R[i,j-1]和R[i+1,j]之间，效率降至平方型。动态规划法解01背包

动态规划法解01背包问题已知：n个重量w1,...,wn、价值v1,...,vn的物品和一个承重量W的背包。要求：找出最有价值子集，且能装入背包中（不超重）。01背包最优化模型（xi=0：i

物品不装入，xi=1：i

物品装入）求：满足约束方程、目标函数取最大值的解向量X=(x1,...,xn)

蛮力法（前面讲过）穷举n个物品全部组合（幂集，子集数=2n），找出最有价值子集。贪婪法——后述，不一定能找到最优解。物品数承重量动态规划法求解01背包

动态规划法求解01背包分段把物品个数(n)、背包承重量(W)进行分段。

V(i,j)：前i个物品能装入背包（当前剩余承重量j）的最大总价值前i个物品的最优子集总价值（动态规划函数）：

V(0,j)=0（0个物品），V(i,0)=0（承重量0）

V(i,j)=V(i-1,j)

第i个物品不能装入，j<wi（超重）

V(i,j)=

max{vi+V(i-1,j-wi),V(i-1,j)}

j>wi（不超重）

（

i在最优子集中）（i不在最优子集中）逐段计算：V(i,j)→V(n,W)，i：0→n,j：0→W

第1阶段：装入1个物品，计算各种承重量下的最优价值子集第2阶段：装入2个物品，计算各种承重量下的最优价值子集

第n阶段：装入n个物品，计算各种承重量下的最优价值子集动态规划法解01背包问题的算法表

动态规划法解01背包问题的算法表

V(0,j)=0（0个物品），V(i,0)=0（承重量0）

V(i,j)=V(i-1,j)

第i个物品不能装入，j<wi（超重）

V(i,j)=

max{vi+V(i-1,j-wi),V(i-1,j)}

j>wi（不超重）

（

i在最优子集中）（i不在最优子集中）Vj=0...j-wi...j...j=Wi=00...0...0...0......i-10V(i-1,j-wi)V(i-1,j)i0V(i,j)......i=n0V(n,W)说明：可按行（或列）填写此表。目标动态规划法解01背包问题算例【算例】动态规划法解01背包问题已知01背包数据如下表，求：放入背包的最有价值物品集合。物品i重量wi价值vi承重量W1w1=2v1=12W=52w2=1v2=103w3=3v3=204w4=2v4=15Vj=012345i=000000010012121212201012222222301012223032401015253037按行或列填表计算的结果例如：接下来，找出最优解的物品集合。动态规划法解01背包问题算例（续）回溯最优解，找到最优子集{w1,w2,w4}最优解有w4最优解无w3最优解有w2最优解有w1最优解回溯计算01背包的动态规划算法（带记忆功能）01背包的动态规划算法（带记忆功能）算法递推式

V(i,j)=max{V(i-1,j),vi+V(i-1,j-wi)}交叠子问题直接用递推式设计递归算法——重复计算交叠子问题，降低效率。避免交叠子问题的递归算法一般递归过程（内层为更小子问题）是自顶向下（规模减小），缺点是产生交叠子问题。动态规划算法采用自底向上计算（规模增大），可避免交叠子问题重复计算。自底向上计算也有缺点：对某些问题，可能一部分子问题的求解是不必要的，比如某个序列的后项由前面2个奇数项构成，前面偶数项的计算就是非必要的。

问1：如何设计无交叠子问题的递归算法？问2：递归算法会求解非必要子问题吗？

答1：保存子问题的计算结果，后续计算需要时查表，不再计算。答2：不会。计算需要递归式中的各项，否则计算不出来。01背包的动态规划算法（带记忆功能）续MFKnapsack(i,j)//带记忆功能的递归算法

//W[1...n],Value[1...n],V[0...n][0...w]全局变量

V[0...n][0...w]←-1，V[0][0]←0if(V[i][j]<0)//未计算：计算V[i][j