算法设计与分析王红梅第二动态规划详解

算法设计与分析王红梅第二版动态规划详解演示文稿现在是1页\一共有110页\编辑于星期日（优选）算法设计与分析王红梅第二版动态规划现在是2页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming3本章要点

6.1概述

6.2图问题中的动态规划法6.3组合问题中的动态规划法6.4查找问题中的动态规划法现在是3页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming46.1概述动态规划？在1950年代由美国数学家贝尔曼为研究最优控制问题而提出的概念。它是一种求解多阶段决策最优化问题的工具。与分治法的关系动态规划法也将待求解问题分解成若干子问题，但各问题间往往不是独立的。分治法对子问题的重叠部分要被重复计算多次。动态规划法将每个子问题只求解一次并保存在表中，下次查表获得解，免去重复计算。现在是4页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming5

最优化问题?有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数取得极值（极大或极小）的可行解称为最优解，这类问题就称为最优化问题。

6.1.1多阶段决策过程现在是5页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming6最优化问题约束条件可行解输出子集目标函数最优解最优化问题思想问题输入集合I={i1i2…in}现在是6页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming7例：0/1背包问题物品i或者被装入背包（xi=1），或者不被装入背后（xi=0）。有如下约束条件和目标函数：

（式6.1）（式6.2）

最优化问题于是问题归结为寻找一个满足式(6.1)的约束条件，并使式(6.2)的目标函数达到最大的解向量X=(x1,x2,…,xn)现在是7页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming8最优性原理

对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据；从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。

AP1P2P7

动态规划的决策过程BCDEP3P4P5P6初始状态最终状态现在是8页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming9

多阶段决策过程满足最优性原理（OptimalPrinciple）：无论决策过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。各子问题的解只与它前面的子问题的解相关，而且各子问题的解都是相对于当前状态的最优解，整个问题的最优解是由各个子问题的最优解构成。如果一个问题满足最优性原理通常称此问题具有最优子结构性质。

最优性原理

现在是9页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming10动态规划法的设计思想

动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。现在是10页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming11

原问题的解

原问题……

填表子问题1子问题2子问题n动态规划法的求解过程动态规划法的设计思想

现在是11页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming12求解过程动态规划法设计算法一般分成三个阶段：分段：将原问题分解为若干个相互重叠的子问题；分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；求解：利用递推式自底向上计算，实现动态规划过程。动态规划法的设计思想

现在是12页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming13n=5时分治法计算斐波那契数的过程

F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：计算斐波那契数分治法求解重复计算动态规划法的设计思想

现在是13页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming1401234567890112358132134动态规划法求解斐波那契数F(9)的填表过程：

注意到，计算F(n)是以计算它的两个重叠子问题

F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。

填表法动态规划法的设计思想

现在是14页\一共有110页\编辑于星期日一个简单的例子——数塔问题问题描述：从数塔的顶层出发，在每一个结点可以选择向左走或向右走，一直走到最底层，要求找出一条路径，使得路径上的数值和最大。81239156810512910184162023/4/24第6章动态规划法Page15现在是15页\一共有110页\编辑于星期日数塔问题——想法81239156810512910184162023/4/24第6章动态规划法Page16[想法]从顶层出发下一层选择取决于两个4层数塔的最大数值和。现在是16页\一共有110页\编辑于星期日求解初始子问题：底层的每个数字可看作1层数塔，则最大数值和就是其自身；再求解下一阶段的子问题：第4层的决策是在底层决策的基础上进行求解，可以看作4个2层数塔，对每个数塔进行求解；再求解下一阶段的子问题：第3层的决策是在第4层决策的基础上进行求解，可以看作3个2层的数塔，对每个数塔进行求解；以此类推，直到最后一个阶段：第1层的决策结果就是数塔问题的整体最优解。数塔问题——想法2023/4/24第6章动态规划法Page17现在是17页\一共有110页\编辑于星期日1.初始化数组maxAdd的最后一行为数塔的底层数据：

for(j=0;j<n;j++)

maxAdd[n-1][j]=d[n-1][j];2.从第n-1层开始直到第1层对下二维数组maxAdd[i][j]执行下述操作：

2.1maxAdd[i][j]=d[i][j]+max{maxAdd[i+1][j],maxAdd[i+1][j+1]};

2.2如果选择下标j的元素，则path[i][j]=j，否则path[i][j]=j+1；3.输出最大数值和maxAdd[0][0]；4.根据path数组确定每一层决策的列下标，输出路径信息；数塔问题——算法2023/4/24第6章动态规划法Page18现在是18页\一共有110页\编辑于星期日数塔问题——算法2023/4/24第6章动态规划法Page19[算法分析]步骤1的时间代价是O(n)，步骤2进行填表工作，需填写n-1行，由于数组maxAdd是下三角矩阵，第i行只需填写i个元素，故步骤2的时间代价是O(n2)。由于数组path已经记载每个决策的列下标，步骤4只需输出每行的决策结果，时间代价是O(n)。所以算法的时间复杂性是O(n2)。现在是19页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming20那些问题可以用动态规划法求解？能用动态规划法求解问题所具有的特征能够分解为相互重叠的若干子问题；满足最优性原理（也称最优子结构性质）：该问题的最优解中包含着其子问题的最优解。分析问题是否满足最优性原理的方法（是用反证法）先假设由问题的最优解导出的子问题的解不是最优的;然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。动态规划法的设计思想

现在是20页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming21本章要点

6.1概述6.2图问题中的动态规划法6.3组合问题中的动态规划法6.4查找问题中的动态规划法现在是21页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming226.2图问题中的动态规划法

6.2.3TSP问题

6.2.1多段图的最短路径问题6.2.2多源点最短路径问题

现在是22页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming23多段图的最短路径问题

多段图的最短路径问题？设图G=(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k,1≤i≤k），使得E中的任何一条边(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,

1＜m），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题：是求从源点到终点的最小代价路径。

现在是23页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming242120345678949387684756866537

一个多段图划分顶点子集：将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集。顶点编号：将顶点集合V中的所有顶点按照段的顺序进行编号，子集中的顶点互不邻接，段内顶点间相互顺序无关紧要。设顶点数为n，源点s的编号为0，终点t的编号为n-1，对E中的任何一条边(u,v)，顶点u的编号小于顶点v的编号。多段图的最短路径问题

现在是24页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming25下图是多段图吗？多段图的最短路径问题

现在是25页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming26

设s,s1,s2,…,sp,t是从s到t的一条最短路径，从源点s开始，设从s到下一段的顶点s1已经求出，则问题转化为求从s1到t的最短路径，显然s1,s2,…,sp,t一定构成一条从s1到t的最短路径，如若不然，设s1,r1,r2,…,rq,t是一条从s1到t的最短路径，则s,s1,r1,r2,…,rq,t将是一条从s到t的路径且比s,s1,s2,…,sp,t的路径长度要短，从而导致矛盾。所以，多段图的最短路径问题满足最优性原理。

证明多段图问题满足最优性原理多段图的最短路径问题

现在是26页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming27多段图的决策过程：多段图的边(u,v)，用cuv表边的权值，从源点s到终点t的最短路径记为d(s,t)，则从源点0到终点9的最短路径d(0,9)由下式确定：d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}上面是最后阶段的决策，它又依赖于d(1,9)、d(2,9)和d(3,9)，其中：d(1,9)=min{c14+d(4,9),c15+d(5,9)}d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}d(3,9)=min{c35+d(5,9),c36+d(6,9)}

这一阶段的决策又依赖于d(4,9)、d(5,9)和d(6,9)：多段图的最短路径问题

现在是27页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming28d(4,9)=min{c47+d(7,9),c48+d(8,9)}d(5,9)=min{c57+d(7,9),c58+d(8,9)}d(6,9)=min{c67+d(7,9),c68+d(8,9)}这一阶段的决策依赖d(7,9)和d(8,9)

，而d(7,9)和d(8,9)可以直接获得：d(7,9)=c79＝7(7→9)d(8,9)=c89＝3(8→9)再向前推导，有：d(6,9)=min{c67+d(7,9),c68+d(8,9)}=min{6+7,5+3}=8(6→8)d(5,9)=min{c57+d(7,9),c58+d(8,9)}=min{8+7,6+3}=9(5→8)d(4,9)=min{c47+d(7,9),c48+d(8,9)}=min{5+7,6+3}=9(4→8)多段图的最短路径问题

现在是28页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming29d(3,9)=min{c35+d(5,9),c36+d(6,9)}=min{4+9,7+8}=13(3→5)d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}=min{6+9,7+9,8+8}=15(2→4)d(1,9)=min{c14+d(4,9),c15+d(5,9)}=min{9+9,8+9}=17(1→5)d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}=min{4+17,2+15,3+13}=16(0→3)最后，得到最短路径为0→3→5→8→9，长度为16。

多段图的最短路径问题

现在是29页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming30多段图的最短路径问题的填表过程：前提条件设数组cost[n]:

作为存储子问题解的表格，cost[i]表示从顶点i到终点t的最短路径或最小花费；设数组path[n]：path[i]存放从顶点i到终点t的最小花费路径上顶点i的下一个顶点编号设数组route[i]：用于存放最短路径顶点子集填表过程第一阶段，确定第k-1段的所有顶点到达终点t的花费最小的通路；第二阶段，用第一阶段的信息，确定第k-2段的所有顶点到达终点t的花费最小的通路；如此依次进行，直到最后确定源点s到达终点t的花费最小的通路；多段图的最短路径问题

现在是30页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming31最后，从源点s的path信息中，确定它的前方顶点编号p1，从p1的path信息中，确定p1的前方顶点编号p2，如此递推，直到终点t。动态规划函数为：

cost[i]=min{cij+cost[j]}(i≤j≤n，且顶点j，i是邻接点)（式6.7）path[i]=取min{cij+cost[j]}的

j

（式6.8）多段图的最短路径问题

现在是31页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming32步骤：对所有的i，0≤i<n

，把cost[i]

初始化为最大值∞，path[i]

初始化为-1；cost[n-1]

初始化为0（如n=10,则cost[9]=0）；令i=n-2；根据（6.7）式和（6.8）式计算cost[i]

和path[i]

；i=i-1，若i≥0，转3；否则，转5；令i=0，route[i]=0；如果route[i]=n-1，算法结束；否则，转7；i=i+1，route[i]=path[route[i-1]]；转6多段图的最短路径问题

现在是32页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming33例:

求解下图所示的最短路径问题多段图的最短路径问题

2120345678949387684756866537现在是33页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming34多段图的最短路径问题

i=n-2=8i=i-1=7>0,继续计算现在是34页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming35多段图的最短路径问题

：最短路径现在是35页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming36多段图的最短路径问题

：计算最短路径顶点集route[n]i=0i=i+1Ifroute[i]<n-1Route[i]=n-1=9，算法结束最后，得到最短的路径为0，3，5，8，9，费用是16。现在是36页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming37多段图的最短路径问题

顶点i0123456789Cost[i]∞∞∞∞∞∞∞∞∞0Path[i]-1-1-1-1-1-1-1-1-1-1Route[i]0顶点i0123456789Cost[i]16171513998730Path[i]354588899-1Route[i]0现在是37页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming38多段图的最短路径问题

顶点i0123456789Cost[i]16171513998730Path[i]354588899-1Route[i]0顶点i0123456789Cost[i]16171513998730Path[i]354588899-1Route[i]03589route[i]=path[route[i-1]]现在是38页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming39算法6.2——多段图的最短路径

1．初始化：数组cost[n]初始化为最大值，数组path[n]初始化为-1，数组元素route[0]=0；

2．for(i=n-2;i>=0;i--)2.1对顶点i的每一个邻接点j，根据式6.7计算cost[i];2.2根据式6.8计算path[i];3．输出最短路径长度cost[0];4.计算route[i],

并输出最短路径经过的顶点：

4.1i=0:4.2循环直到route[i]=n-1

输出route[i]=path[route[i-1]];伪代码多段图的最短路径问题

现在是39页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming40算法6.2主要由三部分组成：第一部分是初始化部分，其时间性能为O(n)；第二部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执行n-1次，内层循环对所有出边进行计算，并且在所有循环中，每条出边只计算一次。假定图的边数为m，则这部分的时间性能是O(m)；第三部分是输出最短路径经过的顶点，设多段图划分为k段，其时间性能是O(k)。如忽略第一部分，算法6.2的时间复杂性为O(m+k)。多段图的最短路径问题

现在是40页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming416.2.2多源点最短路径问题

[问题]给定带权有向图G=(V,E)，对任意顶点vi和vj(i≠j)，求顶点vi和vj的最短路径长度。[想法]设d(vi,vj,V)是从顶点vi到vj经过顶点集合V的最短路径长度初始子问题：d(vi,vj,{})，即vi到vj弧，若不存在则为∞下个子问题：d(vi,vj,{v0})，取vi,vj和vi,v0,vj较短者下个子问题：d(vi,vj,{v0,v1})，取d(vi,vj,{v0})和vi,…,v1,…,vj较短者……d(vi,vj,{v0,…,vk})=min{d(vi,vj,{v0,…,vk-1}),d(vi,vk,{v0,…,vk-1})+d(vk,vj,{v0,…,vk-1})}现在是41页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming426.2.2多源点最短路径问题

动态规划函数(0≤i,j≤n-1): d(vi,vj,{})=cij d(vi,vj,{v0,…,vk})=min{d(vi,vj,{v0,…,vk-1}), d(vi,vk,{v0,…,vk-1})+d(vk,vj,{v0,…,vk-1})}现在是42页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming436.2.2多源点最短路径问题

现在是43页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming446.2.2多源点最短路径问题

[算法实现]设图G=(V,E)中顶点的编号为{0,1,…,n-1}，有向边上的权值存储在代价矩阵arc[n][n]中，数组dist[n][n]存放在迭代过程中求得的最短路径长度，初始为图的邻接矩阵，在迭代过程中，根据如下递推关系式进行迭代：dist-1[i][j]=arc[i][j]distk[i][j]=min{distk-1[i][j],distk-1[i][k]+distk-1[k][j]}0≤k≤n-1distk[i][j]是从顶点vi到vj经过顶点集合{v0,…,vk}的最短路径长度现在是44页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming456.2.2多源点最短路径问题

constintn=10;voidfloyd(intarc[n][n],intdist[n][n]){ inti,j,k; for(i=0;i<n;i++) //初始化矩阵dist for(j=0;j<n;j++) dist[i][j]=arc[i][j]; for(k=0;k<n;k++) //进行n次迭代 for(i=0;i<n;i++) for(j=0;j<n;j++) if(dist[i][k]+dist[k][j]<dist[i][j]) dist[i][j]=dist[i][k]+dist[k][j];}现在是45页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming466.2.2多源点最短路径问题

[算法分析]Floyd算法的基本语句是比较操作dist[i][k]+dist[k][j]<dist[i][j]，设图中有n个顶点，三层嵌套的循环实现对二维数组dist迭代n次，其时间复杂性是O(n3)。现在是46页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming47TSP问题

TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短,也就是在有向带权图G=<V,E>中，寻找路径最短的哈密尔问题。

设4个城市间的距离可以用代价矩阵来表示。C=∞3675∞2364∞2375∞

带权图的代价矩阵=Cij12341234现在是47页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming48

设s,s1,s2,…,sp,s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1,s2,…,sp,s一定构成一条从s1到s的最短路径。如若不然，设s1,r1,r2,…,rq,

s是一条从s1到s的最短路径且经过n-1个不同城市，则s,s1,r1,r2,…,rq,s将是一条从s出发的路径长度最短的简单回路且比s,s1,s2,…,sp,s要短，从而导致矛盾。所以，TSP问题满足最优性原理。首先证明TSP问题满足最优性原理:TSP问题

现在是48页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming49解TSP问题的过程描述如下：设从i出发，V’＝V－{i}令d(i,V’):表示从顶点i

出发，经过V’中各个顶点一次且仅一次，最终回到顶点i的最短路径长度。d(k,{}):从顶点k出发，回到i点的最短路径长度d(k,V’-{k}):从k出发，经过V’-{k}的点，回到i的最短路径长度则TSP的动态规划函数为：

d(i,V-{i})=d(i,V’)=

min{cik+d(k,V’－{k})}

(k∈V’)

（式6.5）

d(k,{})=cki(k≠i)

（式6.6）TSP问题

从城市0出发经城市1、2、3然后回到城市0的最短路径长度是：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,3})}现在是49页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming50上式是最初阶段的决策，而：

d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}这一阶段的决策又依赖于下面的计算结果：d(2,{3})=c23+d(3,φ)d(3,{2})=c32+d(2,φ)d(1,{3})=c13+d(3,φ)d(3,{1})=c31+d(1,φ)d(1,{2})=c12+d(2,φ)d(2,{3})=c21+d(1,φ)

而上式中的d(i,φ)可以直接获得：d(1,φ)=c10=5(1→0)d(2,φ})=c20=6(2→0)d(3,φ)=c30=3(3→0)TSP问题

现在是50页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming51有了这些结果，再向前计算，有：TSP问题

再向前倒推，有：1234562→33→21→33→11→22→1现在是51页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming52TSP问题

2→13→21→20→1最后：

所以，从0出发的TSP问题最短路径长度为10，其路径：01230

87109现在是52页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming53假设

n个顶点用0～n-1的数字编号，首先生成所有的顶点子集存放数组V[2n-1]中，当n=4时，从V[1]={1},…,

V[1,2,3]},设数组d[n][2n-1]存放迭代结果，其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次，最后回到出发点0的最短路径长度。根据：d(i,φ)=ci0(i≠j)

初始化d[i][0]：ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0

15

26

33

动态规划法求解TSP的填表过程TSP问题

现在是53页\一共有110页\编辑于星期日2023/4/24Chapter6DynamicProgramming54ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0

1015

86

7

269

5

10

331211

14

TSP问题