第五章-动态规划详解课件

第5章动态规划

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

01背包问题第5章动态规划动态规划概述动态规划概述

动态规划概述动态规划（DynamicProgramming），在20世纪50年代由美国数学家RichardBellman（理查德.贝尔曼）发明，作为多阶段决策过程最优化的一种通用方法，对最优化问题提出最优性原则，从而创建最优化问题的一种新算法设计技术——动态规划，它是一种重要的应用数学工具。至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题，而最终把它作为一种通用的算法设计技术，即包括某些非最优化问题。多阶段决策过程最优化：现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算复杂度很高、计算量很大的问题（如求最佳子集的组合问题），要找出一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了降低求解问题的难度，把求解过程分为一系列阶段，各个阶段依次按照最优性原则计算，最后阶段计算得到最优解。包括分段、求解两大步。注：不能段化的问题不能用动态规划法求解。动态规划概述动态规划概述最优性原则阶段1阶段2......阶段n求解算法求解算法求解算法多阶段决策过程图示动态的含义：求解算法施加的状态是变化的。当前状态只与其直接前趋状态有关，对其直接前趋状态施加求解算法，成为当前状态。最优性原则(PrincipleofOptimality)：一个最优问题任何实例的最优解，是由该实例的子实例的最优解组成的。对特定问题该原则不一定满足（罕见），有必要检查其适用性。子实例组成父实例，父实例分解为子实例。对于某些多阶段决策问题，问题本身没有最优化要求，比如后面要讲到的求中国象棋马从棋盘上一点移动到另一点的全部路径问题，又如计算裴波那契序列的动态规划算法，它们属于非最优化问题的动态规划法。动态规划法的特点：1.分阶段（级）决策。对最优化问题，用最优性原则设计。2.一般采用自顶向下分析（规模减小），自底向上计算（规模增加）。计算过程是一级一级（一阶段一阶段）地向前推进，直到最终状态。最优性原则阶段1阶段2......阶段n求解算法求解算数塔

数塔问题：设有一三角形数塔如图。求一条自塔顶到塔底的路径，该路径上

节点值之和最大。分段：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。无法分段的问题，不能用动态规划法求解。求解：动态规划法求解。自底向上计算，各实例计算满足最优性原则，如实例18的子实例为12和7，max(12+6,7+6)=18。5级4级3级2级1级182739326746657873911311874014261582467131211数塔数塔分段：每一级台阶自然划分为一个阶段，成为多阶段决策数塔问题：动态规划法与穷举法效率比较

数塔：动态规划法与穷举法的时间效率比较输入规模：为便于分析，选择数塔层数k(k>0)；基本操作：节点值求和运算；增长函数：加法次数与k的关系；效率类别：没有最佳、最差情况；（都要从塔顶计算到塔底）增长率（次数）：各层节点数升序：1,2,3,4,5,6,7,8,9,10,...

节点总数

n

升序：1,3,6,10,15,21,28,36,45,55,...

层数k（顶为1）：1,2,3,4,5,6,7,8,9,10,...

路径总数t升序：

2,

4,8,16,32,...,t=2k-1,k>11.穷举法：T(k)=(k-1)2k-1，k>1（指数级）本例k=5，每条路径上5个节点做4次加法，共64次加法。2.动态规划法：（层节点数=层数）自底向上计算，k层加法总数为k-1层节点数×2，有效率计算式：

T(k)=2×(k-1+...+3+2+1)=k(k-1),k>1（平方级）本例加法总数2×(4+3+2+1)=20次，比64次少很多。数塔问题：动态规划法与穷举法效率比较数塔：动态规划法与穷举非最优化问题实例

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

问题：在m×n棋盘上，求马从P点跳到Q点的所有路径。654321654321654321可用回溯法和递归法求解，但递归法效率很低，栈空间占用很大。非最优化问题实例非最优化问题实例654最小代价子母树

最小代价子母树

问题：n(n>1)堆沙子，重量向量W=(w1,...wn)。要将它们归并为1堆，归并规则：每次只能将相邻2堆归并为1堆，经过n-1次归并后，最终归并为一堆。总代价为归并过程中新产生的沙堆质量之和，这个代价最小的归并树称为最小代价子母树。分析：属于最优化问题，目标为总代价最小。分段：显然需要n-1次归并才能将n堆归并为1堆。自然地可以将每次归并划分为一个阶段，成为多阶段决策问题，尝试动态规划法。求解：（此处采用自底向上的分析，找规律较简洁）当n=2时：仅一种归并法即2合1。当n=3时：有2种归并方法，第一种归并方法如图，前1堆后2堆。13781528f(i,j)——从第i堆到第j堆的代价和。g(i,j)——从第i堆到第j堆的重量和。f(1,3)=15+28=43

（最优结果）

=f(2,3)+g(1,3)序号1

233级2级1小代价子母树最小代价子母树13781528f(i,j)最小代价子母树(续1)n=4n=3时：第二种归并方法，前2堆后1堆。n=4时：有3大类归并法。前1堆后3堆、前2堆后2堆、前3堆后1堆。因3堆有2种归并法，所以一共5小类归并法。前1堆第1种情况：78163115序号1

2341344f(1,4)=15+31+44=90=f(2,4)+g(1,4)w不变

=f(2,3)+g(2,4)+g(1,4)若f(2,4)越小，则f(1,4)就越小。13782028f(i,j)——从第i堆到第j堆的代价和。g(i,j)——从第i堆到第j堆的重量和。f(1,3)=20+28=48

=f(1,2)+g(1,3)序号1

233级2级1级4级3级2级1级最小代价子母树(续1)n=4n=3时：第二种归并方法，前2最小代价子母树(续2)n=4n=4时：前1堆的第2种情况。781624311344序号1

234f(1,4)=24+31+44=99=f(2,4)+g(1,4)w不变

=f(3,4)+g(2,4)+g(1,4)若f(2,4)越小，则f(1,4)就越小。n=4时：前2堆情况。781624201344序号1

234f(1,4)=20+24+44=88=f(1,2)+f(3,4)+g(1,4)若f(1,2)+f(3,4)越小，f(1,4)就越小4级3级2级1级3级2级1级最小代价子母树(续2)n=4n=4时：前1堆的第2种情况最小代价子母树(续3)n=4n=4时：前3堆的第1种情况。781620281344n=4时：前3堆的第2种情况。序号1

234f(1,4)=20+28+44=92=f(1,3)+g(1,4)w不变

=f(1,2)+g(1,3)+g(1,4)若f(1,3)越小，则f(1,4)就越小。781615281344序号1

234f(1,4)=15+28+44=87最优

=f(1,3)+g(1,4)w不变

=f(2,3)+g(1,3)+g(1,4)若f(1,3)越小，则f(1,4)就越小。4级3级2级1级4级3级2级1级最小代价子母树(续3)n=4n=4时：前3堆的第1种情况最小代价子母树(续4)n=4将n=4归纳为3大类情况：f(1,4)=min

{f(2,4),f(1,2)+f(3,4),f(1,3)}

+g(1,4)

前1堆前2堆前3堆将n=4计算式推广，对于任意的n(n>1)，归纳出如下公式：f(1,n)=min{f(2,n),f(1,2)+f(3,n),f(1,3)+f(4,n),...,f(1,n-1)}

+

g(1,n)

前1堆前2堆前3堆......前n-1堆上式称为动态方程，即用方程给出的动态规划算法。很多动态规划算法不能用方程形式给出，只能是描述性的。最小代价子母树(续4)n=4F(1,n)在(13,7,8,16,21,4,18)上的结果F(1,n)在(13,7,8,16,21,4,18)上的结果//w[1...n]:n堆沙子的质量序列//g[1...n;1...n]:g[i,j]=//f[1…n:1…n]:f[I,j]表示第i层从第j个位置开始i堆沙子的最小归并代价,并约定f[1,i]=0proceduremincpt(w)begin

计算g[i,j]=g[j,i]=f[i,j]←0(1≤i≤n,1≤j≤n);fori←2tondo//i表示层次,也是归并沙子的堆数,在上图中,表示行号

forj←1ton-i+1do//表示列号

beginmin←f[i-1,j];

fork←i-1step-1untill1doifmin>f[k,j]+f[i-k,j+k]then//min{f(1,n-1),f(1,2)+f(3,n),f(1,3)+f(4,n)…min←f[k,j]+f[i-k,j+k];f[i,j]←g[j,i+j-1]+min;end;return(f[n,1]);endp;//w[1...n]:n堆沙子的质量序列递推求解中的交叠子问题

递推求解中的交叠子问题（非最优化问题）实例：计算裴波那契数的递归版本。递推式：n>1，F(n)=F(n-1)+F(n-2)F(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(5)分为两个子问题F(4)和F(3)，F(4)包含了F(3)。动态规划法：自底向上计算依次计算F(0),F(1),F(2),...,F(n)一次，各次计算结果存入数组，最后一个元素就是F(n)。用一个单循环即可简单实现。递推求解中的交叠子问题递推求解中的交叠子问题（非最优化问单起点最短路径问题

单起点最短路径问题（区别于完全最短路径问题）概念：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点的最短路径，此即单起点（单源）最短路径问题。完全最短路径问题要求找到从每个顶点到其他所有顶点之间的最短路径。分段：顶点集分为k个不相交子集Vd,1≤d≤k,k≥2,级内顶点不相邻。任一条边(u,v)，u∈Vd，v∈Vd+m，m≥1。令|V1|=|Vk|=1。从源点到收点依次编号V1V2V3V4V512345678910分级k=1k=2k=3k=4k=5图示求解过程：红色数字为实例求解结果（最优性原则）本例：带权有向图源点收点计算方向841210819171316单起点最短路径问题单起点最短路径问题（区别于完全最短路径对于一个有k级的动态规划,需要列出从s到t的每一条路上的k-2次判定结果.其中第i级判定是利用最优化原理确定Vi+1中的哪一个顶点在可能得到的最佳线路上.设D(i,j)是从顶点集Vi中的点j到t的一条最小耗费路线,cost(i,j)是这条路线的耗费.由后向前推算,得:cost(i,j)=min{C(j,l)+cost(i+1,l)}C(j,l):表示顶点集Vi中的顶点j到顶点集Vi+1中的点l的耗费cost(i+1,l):表示顶点集Vi+1中的点l到目标点t的耗费对于一个有k级的动态规划,需要列出从s到t的每一条路上的k-cost(3,5)=min(4+cost(4,8),8+cost(4,9))=min(4+8,8+4)=12//第三层中,顶点5到终点的耗费cost(3,6)=min(9+cost(4,8),6+cost(4,9))=min(9+8,6+4)=10//取顶点9cost(3,7)=min(5+cost(4,8),4+cost(4,9))=min(5+8,4+4)=8cost(2,2)=min(10+cost(3,5),9+cost(3,6))=min(10+12,9+10)=19cost(2,3)=min(6+12,7+10,10+8)=17cost(2,4)=min(3+10,8+8)=13//取顶点6cost(1,1)=min(4+19,2+17,3+13)=16//取顶点4cost(3,5)=min(4+cost(4,8),8+co由cost(1,1)=3+cost(2,4)记下结点4由cost(2,4)=3+cost(3,6)记下结点6由cost(3,6)=6+cost(4,9)记下结点9即D(1,1)=4,D(2,4)=6,D(3,6)=9,D(4,9)=10所以得到线路:1,4,6,9,10由cost(1,1)=3+cost(2,4)记下结点4//最短路径算法输入:图的顶点编号表,各顶点的邻接表,边的耗费函数C(i,j)表.输出:从s到t的一条最小耗费路线及其耗费cost(1,s),即cost(1)procdureFGRAPHbeginfori←1tondocost[i]←0;forj←n-1step-1to1do begin 设顶点r使(j,r)∈E,且C(j,r)+cost[r]最小;

//耗费时间(n+E)

cost[j]←C(j,r)+cost[r]; D[j]←r;//记下最短路径经历的顶点

End;p[1]←1;

//找最小耗费路线p[k]←n;forj←2tok-1do p[j]←D[p[j-1]];endp;//最短路径算法最优二叉查找树

最优二叉查找树（最优BST）前面我们已经讲过BST的相关算法及特性，本节介绍什么是最优BST，以及用动态规划算法来构造BST。最优BST概念问题的提出：基于统计先验知识，我们可统计出一个数表（集合）中各元素的查找概率，理解为集合各元素的出现频率。比如中文输入法字库中各词条（单字、词组等）的先验概率，针对用户习惯可以自动调整词频——所谓动态调频、高频先现原则，以减少用户翻查次数。这就是最优二叉查找树问题：查找过程中键值比较次数最少，或者说希望用最少的键值比较次数找到每个关键码（键值）。为解决这样的问题，显然需要对集合的每个元素赋予一个特殊属性——查找概率。最优BST：最优BST整棵树的平均键值比较次数最小。BST好处是查找效率高，平均查找效率属于logn型，最坏为线性（完全不平衡）。最优二叉查找树最优二叉查找树（最优BST）举例说明：解最优BST问题的蛮力策略（穷举法）

举例说明：解最优BST问题的蛮力策略（穷举法）已知：4个键{a1,a2,a3,a4}，出现概率依次为{0.1,0.2,0.4,0.3}要求：构造包含这4个键的最优BST。策略：穷举生成包含4个键的全部BST，共14种。然后计算每个BST的

平均键值比较次数，从中选择比较次数最小的作为最优BST。包含n个键的BST总数等于第n个卡塔兰数：BST的平均键值比较次数的计算：（统计平均）它以4n/n1.5速度→(+∞)包含4个键的两种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算法原理

动态规划法生成最优BST算法原理问题：n个键，查找概率，构成最优BST，表示为，求这棵树的平均查找次数C[1,n]

（耗费最低）。换言之，如何构造这棵最优BST，使得C[1,n]最小。分段求解：（自顶向下分析：规模减小）

动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解由其直接前趋实例解计算得到。对于最优BST问题，利用减一技术和最优性原则，如果前n-1

个节点构成最优BST，加入一个节点an

后要求构成规模n

的最优BST。按n-1,n-2,...,2,1递归，问题可解。自底向上计算：C[1,2]→C[1,3]→...→C[1,n]。为不失一般性用C[i,j]表示由构成的BST的耗费。其中

1≤i≤j≤n。这棵树表示为。从中选择一个键作根节点，它的左子树为，右子树为。要求选择的k使得整棵树的平均查找次数C[i,j]最小。左右子树递归执行此过程。（根的生成过程）动态规划法生成最优BST算法原理动态规划法生成最优B动态规划法生成最优BST算法原理（续）akpk最优BST最优BST根层：L(ak)=1k-1=i：左子树缩为单节点。k+1=j：右子树缩为单节点。k<i：左子树为空树。k>j：右子树为空树。1≤i≤j≤n自顶向下分析递推计算式动态规划法生成最优BST算法原理（续）akpk最优最优根层：举例说明：动态规划法生成最优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过程举例说明：动态规划法举例说明：动态规划法生成最优BST过程（续1）

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

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

主表C

和

根表R

描述如下：举例说明：动态规划法生成最优BST过程（续2）举例说明：动动态规划算法：主表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]动态规划算法：主表C和根表K各阶段计算结果用主表C和根动态规划法算例的计算结果图本例计算结果：akpk最优BST最优BSTa10.1a30.4a40.30.2a2j=01234i=112332233333445根表R[i,j]根表可知，4个键的最优根下标为3即a3键。它的左子树为a1a2键，右子树为a4键。左子树是什么结构呢？再看根表，a1a2构成的最优子树根是a2。因为a1<a2，所以1键是2键的左节点。最终结果图动态规划法算例的计算结果图本例计算结果：akpk最优最优a1动态规划法生成最优BST算法

动态规划法生成最优BST算法procedureSUBTREE-ROOT//w权值矩阵,C代价矩阵,r最优树根列表beginfori←1tondo begin w[i,i]←q[i];C[i,i]←0; end;forl←1tondofori←0ton-1do begin j←i+1;w[i,j]←w[i,j-1]+p[j]+q[j];

令m是使得C[i,k-1]+C[k,j]最小的k值(i<k<=j);C[i,j]←w[i,j]+C[i,m-1]+C[m,j]; r[i,j]←a[m]; end;endp;动态规划法生成最优BST算法动态规划法生成最优BST算法pprocedureBUILDTREE(i,j)begincreattherootofT[i,j],thatis,nodev[i,j]Markv[i,j]byr[i][j];Letmbethesubscriptofr[i,j]ifi<m-1thenBUILDTREE(i,m-1);//Buildtheleftsubtreeofv[i,j];ifm<jthenBUILDTREE(m,j);//Buildtherightsubtreeofv[i,j]endp;procedureBUILDTREE(i,j)动态规划法解01背包

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

物品不装入，xi=1：i

物品装入）求满足约束方程的是目标函数达到最大的解向量X=(x1,...,xn)。穷举n个物品全部组合（幂集，子集数=2n），从中找出最有价值子集。贪婪法不一定能找到最优解。物品数承重量动态规划法解01背包动态规划法解01背包物品数承重量动态规划法求解01背包

动态规划法求解01背包分段：动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解由直接前趋子实例解计算得到。对于01背包问题，可利用减一技术和最优性原则，按物品数量和背包承重量分段。

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）目标

V(n,W)

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

动态规划法解01背包问题的算法表：前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不在最优子集中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背包问题算例

动态规划法解01背包问题算例例：01背包数据如下表，求：能够放入背包的最有价值的物品集合。物品i重量wi价值vi承重量W1w1=2v1=12W=52w2=1v2=103w3=3v3=204w4=2v4=15Vj=012345i=000000010012121212201012222222301012223032401015253037自底向上：按行或列填表。递推公式：例如：接下来，找出最优解的物品集合。动态规划法解01背包问题算例动态规划法解01背包问题算例物动态规划法解01背包问题算例（续）通过最优解的回溯，找出最优子集为{w1,w2,w4}最优解有w4最优解无w3最优解有w2最优解有w1最优解回溯2动态规划法解01背包问题算例（续）通过最优解的回溯，找出最优第5章动态规划

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

01背包问题第5章动态规划动态规划概述动态规划概述

动态规划概述动态规划（DynamicProgramming），在20世纪50年代由美国数学家RichardBellman（理查德.贝尔曼）发明，作为多阶段决策过程最优化的一种通用方法，对最优化问题提出最优性原则，从而创建最优化问题的一种新算法设计技术——动态规划，它是一种重要的应用数学工具。至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题，而最终把它作为一种通用的算法设计技术，即包括某些非最优化问题。多阶段决策过程最优化：现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算复杂度很高、计算量很大的问题（如求最佳子集的组合问题），要找出一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了降低求解问题的难度，把求解过程分为一系列阶段，各个阶段依次按照最优性原则计算，最后阶段计算得到最优解。包括分段、求解两大步。注：不能段化的问题不能用动态规划法求解。动态规划概述动态规划概述最优性原则阶段1阶段2......阶段n求解算法求解算法求解算法多阶段决策过程图示动态的含义：求解算法施加的状态是变化的。当前状态只与其直接前趋状态有关，对其直接前趋状态施加求解算法，成为当前状态。最优性原则(PrincipleofOptimality)：一个最优问题任何实例的最优解，是由该实例的子实例的最优解组成的。对特定问题该原则不一定满足（罕见），有必要检查其适用性。子实例组成父实例，父实例分解为子实例。对于某些多阶段决策问题，问题本身没有最优化要求，比如后面要讲到的求中国象棋马从棋盘上一点移动到另一点的全部路径问题，又如计算裴波那契序列的动态规划算法，它们属于非最优化问题的动态规划法。动态规划法的特点：1.分阶段（级）决策。对最优化问题，用最优性原则设计。2.一般采用自顶向下分析（规模减小），自底向上计算（规模增加）。计算过程是一级一级（一阶段一阶段）地向前推进，直到最终状态。最优性原则阶段1阶段2......阶段n求解算法求解算数塔

数塔问题：设有一三角形数塔如图。求一条自塔顶到塔底的路径，该路径上

节点值之和最大。分段：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。无法分段的问题，不能用动态规划法求解。求解：动态规划法求解。自底向上计算，各实例计算满足最优性原则，如实例18的子实例为12和7，max(12+6,7+6)=18。5级4级3级2级1级182739326746657873911311874014261582467131211数塔数塔分段：每一级台阶自然划分为一个阶段，成为多阶段决策数塔问题：动态规划法与穷举法效率比较

数塔：动态规划法与穷举法的时间效率比较输入规模：为便于分析，选择数塔层数k(k>0)；基本操作：节点值求和运算；增长函数：加法次数与k的关系；效率类别：没有最佳、最差情况；（都要从塔顶计算到塔底）增长率（次数）：各层节点数升序：1,2,3,4,5,6,7,8,9,10,...

节点总数

n

升序：1,3,6,10,15,21,28,36,45,55,...

层数k（顶为1）：1,2,3,4,5,6,7,8,9,10,...

路径总数t升序：

2,

4,8,16,32,...,t=2k-1,k>11.穷举法：T(k)=(k-1)2k-1，k>1（指数级）本例k=5，每条路径上5个节点做4次加法，共64次加法。2.动态规划法：（层节点数=层数）自底向上计算，k层加法总数为k-1层节点数×2，有效率计算式：

T(k)=2×(k-1+...+3+2+1)=k(k-1),k>1（平方级）本例加法总数2×(4+3+2+1)=20次，比64次少很多。数塔问题：动态规划法与穷举法效率比较数塔：动态规划法与穷举非最优化问题实例

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

问题：在m×n棋盘上，求马从P点跳到Q点的所有路径。654321654321654321可用回溯法和递归法求解，但递归法效率很低，栈空间占用很大。非最优化问题实例非最优化问题实例654最小代价子母树

最小代价子母树

问题：n(n>1)堆沙子，重量向量W=(w1,...wn)。要将它们归并为1堆，归并规则：每次只能将相邻2堆归并为1堆，经过n-1次归并后，最终归并为一堆。总代价为归并过程中新产生的沙堆质量之和，这个代价最小的归并树称为最小代价子母树。分析：属于最优化问题，目标为总代价最小。分段：显然需要n-1次归并才能将n堆归并为1堆。自然地可以将每次归并划分为一个阶段，成为多阶段决策问题，尝试动态规划法。求解：（此处采用自底向上的分析，找规律较简洁）当n=2时：仅一种归并法即2合1。当n=3时：有2种归并方法，第一种归并方法如图，前1堆后2堆。13781528f(i,j)——从第i堆到第j堆的代价和。g(i,j)——从第i堆到第j堆的重量和。f(1,3)=15+28=43

（最优结果）

=f(2,3)+g(1,3)序号1

233级2级1小代价子母树最小代价子母树13781528f(i,j)最小代价子母树(续1)n=4n=3时：第二种归并方法，前2堆后1堆。n=4时：有3大类归并法。前1堆后3堆、前2堆后2堆、前3堆后1堆。因3堆有2种归并法，所以一共5小类归并法。前1堆第1种情况：78163115序号1

2341344f(1,4)=15+31+44=90=f(2,4)+g(1,4)w不变

=f(2,3)+g(2,4)+g(1,4)若f(2,4)越小，则f(1,4)就越小。13782028f(i,j)——从第i堆到第j堆的代价和。g(i,j)——从第i堆到第j堆的重量和。f(1,3)=20+28=48

=f(1,2)+g(1,3)序号1

233级2级1级4级3级2级1级最小代价子母树(续1)n=4n=3时：第二种归并方法，前2最小代价子母树(续2)n=4n=4时：前1堆的第2种情况。781624311344序号1

234f(1,4)=24+31+44=99=f(2,4)+g(1,4)w不变

=f(3,4)+g(2,4)+g(1,4)若f(2,4)越小，则f(1,4)就越小。n=4时：前2堆情况。781624201344序号1

234f(1,4)=20+24+44=88=f(1,2)+f(3,4)+g(1,4)若f(1,2)+f(3,4)越小，f(1,4)就越小4级3级2级1级3级2级1级最小代价子母树(续2)n=4n=4时：前1堆的第2种情况最小代价子母树(续3)n=4n=4时：前3堆的第1种情况。781620281344n=4时：前3堆的第2种情况。序号1

234f(1,4)=20+28+44=92=f(1,3)+g(1,4)w不变

=f(1,2)+g(1,3)+g(1,4)若f(1,3)越小，则f(1,4)就越小。781615281344序号1

234f(1,4)=15+28+44=87最优

=f(1,3)+g(1,4)w不变

=f(2,3)+g(1,3)+g(1,4)若f(1,3)越小，则f(1,4)就越小。4级3级2级1级4级3级2级1级最小代价子母树(续3)n=4n=4时：前3堆的第1种情况最小代价子母树(续4)n=4将n=4归纳为3大类情况：f(1,4)=min

{f(2,4),f(1,2)+f(3,4),f(1,3)}

+g(1,4)

前1堆前2堆前3堆将n=4计算式推广，对于任意的n(n>1)，归纳出如下公式：f(1,n)=min{f(2,n),f(1,2)+f(3,n),f(1,3)+f(4,n),...,f(1,n-1)}

+

g(1,n)

前1堆前2堆前3堆......前n-1堆上式称为动态方程，即用方程给出的动态规划算法。很多动态规划算法不能用方程形式给出，只能是描述性的。最小代价子母树(续4)n=4F(1,n)在(13,7,8,16,21,4,18)上的结果F(1,n)在(13,7,8,16,21,4,18)上的结果//w[1...n]:n堆沙子的质量序列//g[1...n;1...n]:g[i,j]=//f[1…n:1…n]:f[I,j]表示第i层从第j个位置开始i堆沙子的最小归并代价,并约定f[1,i]=0proceduremincpt(w)begin

计算g[i,j]=g[j,i]=f[i,j]←0(1≤i≤n,1≤j≤n);fori←2tondo//i表示层次,也是归并沙子的堆数,在上图中,表示行号

forj←1ton-i+1do//表示列号

beginmin←f[i-1,j];

fork←i-1step-1untill1doifmin>f[k,j]+f[i-k,j+k]then//min{f(1,n-1),f(1,2)+f(3,n),f(1,3)+f(4,n)…min←f[k,j]+f[i-k,j+k];f[i,j]←g[j,i+j-1]+min;end;return(f[n,1]);endp;//w[1...n]:n堆沙子的质量序列递推求解中的交叠子问题

递推求解中的交叠子问题（非最优化问题）实例：计算裴波那契数的递归版本。递推式：n>1，F(n)=F(n-1)+F(n-2)F(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(5)分为两个子问题F(4)和F(3)，F(4)包含了F(3)。动态规划法：自底向上计算依次计算F(0),F(1),F(2),...,F(n)一次，各次计算结果存入数组，最后一个元素就是F(n)。用一个单循环即可简单实现。递推求解中的交叠子问题递推求解中的交叠子问题（非最优化问单起点最短路径问题

单起点最短路径问题（区别于完全最短路径问题）概念：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点的最短路径，此即单起点（单源）最短路径问题。完全最短路径问题要求找到从每个顶点到其他所有顶点之间的最短路径。分段：顶点集分为k个不相交子集Vd,1≤d≤k,k≥2,级内顶点不相邻。任一条边(u,v)，u∈Vd，v∈Vd+m，m≥1。令|V1|=|Vk|=1。从源点到收点依次编号V1V2V3V4V512345678910分级k=1k=2k=3k=4k=5图示求解过程：红色数字为实例求解结果（最优性原则）本例：带权有向图源点收点计算方向841210819171316单起点最短路径问题单起点最短路径问题（区别于完全最短路径对于一个有k级的动态规划,需要列出从s到t的每一条路上的k-2次判定结果.其中第i级判定是利用最优化原理确定Vi+1中的哪一个顶点在可能得到的最佳线路上.设D(i,j)是从顶点集Vi中的点j到t的一条最小耗费路线,cost(i,j)是这条路线的耗费.由后向前推算,得:cost(i,j)=min{C(j,l)+cost(i+1,l)}C(j,l):表示顶点集Vi中的顶点j到顶点集Vi+1中的点l的耗费cost(i+1,l):表示顶点集Vi+1中的点l到目标点t的耗费对于一个有k级的动态规划,需要列出从s到t的每一条路上的k-cost(3,5)=min(4+cost(4,8),8+cost(4,9))=min(4+8,8+4)=12//第三层中,顶点5到终点的耗费cost(3,6)=min(9+cost(4,8),6+cost(4,9))=min(9+8,6+4)=10//取顶点9cost(3,7)=min(5+cost(4,8),4+cost(4,9))=min(5+8,4+4)=8cost(2,2)=min(10+cost(3,5),9+cost(3,6))=min(10+12,9+10)=19cost(2,3)=min(6+12,7+10,10+8)=17cost(2,4)=min(3+10,8+8)=13//取顶点6cost(1,1)=min(4+19,2+17,3+13)=16//取顶点4cost(3,5)=min(4+cost(4,8),8+co由cost(1,1)=3+cost(2,4)记下结点4由cost(2,4)=3+cost(3,6)记下结点6由cost(3,6)=6+cost(4,9)记下结点9即D(1,1)=4,D(2,4)=6,D(3,6)=9,D(4,9)=10所以得到线路:1,4,6,9,10由cost(1,1)=3+cost(2,4)记下结点4//最短路径算法输入:图的顶点编号表,各顶点的邻接表,边的耗费函数C(i,j)表.输出:从s到t的一条最小耗费路线及其耗费cost(1,s),即cost(1)procdureFGRAPHbeginfori←1tondocost[i]←0;forj←n-1step-1to1do begin 设顶点r使(j,r)∈E,且C(j,r)+cost[r]最小;

//耗费时间(n+E)

cost[j]←C(j,r)+cost[r]; D[j]←r;//记下最短路径经历的顶点

End;p[1]←1;

//找最小耗费路线p[k]←n;forj←2tok-1do p[j]←D[p[j-1]];endp;//最短路径算法最优二叉查找树

最优二叉查找树（最优BST）前面我们已经讲过BST的相关算法及特性，本节介绍什么是最优BST，以及用动态规划算法来构造BST。最优BST概念问题的提出：基于统计先验知识，我们可统计出一个数表（集合）中各元素的查找概率，理解为集合各元素的出现频率。比如中文输入法字库中各词条（单字、词组等）的先验概率，针对用户习惯可以自动调整词频——所谓动态调频、高频先现原则，以减少用户翻查次数。这就是最优二叉查找树问题：查找过程中键值比较次数最少，或者说希望用最少的键值比较次数找到每个关键码（键值）。为解决这样的问题，显然需要对集合的每个元素赋予一个特殊属性——查找概率。最优BST：最优BST整棵树的平均键值比较次数最小。BST好处是查找效率高，平均查找效率属于logn型，最坏为线性（完全不平衡）。最优二叉查找树最优二叉查找树（最优BST）举例说明：解最优BST问题的蛮力策略（穷举法）

举例说明：解最优BST问题的蛮力策略（穷举法）已知：4个键{a1,a2,a3,a4}，出现概率依次为{0.1,0.2,0.4,0.3}要求：构造包含这4个键的最优BST。策略：穷举生成包含4个键的全部BST，共14种。然后计算每个BST的

平均键值比较次数，从中选择比较次数最小的作为最优BST。包含n个键的BST总数等于第n个卡塔兰数：BST的平均键值比较次数的计算：（统计平均）它以4n/n1.5速度→(+∞)包含4个键的两种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算法原理

动态规划法生成最优BST算法原理问题：n个键，查找概率，构成最优BST，表示为，求这棵树的平均查找次数C[1,n]

（耗费最低）。换言之，如何构造这棵最优BST，使得C[1,n]最小。分段求解：（自顶向下分析：规模减小）

动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解由其直接前趋实例解计算得到。对于最优BST问题，利用减一技术和最优性原则，如果前n-1

个节点构成最优BST，加入一个节点an

后要求构成规模n

的最优BST。按n-1,n-2,...,2,1递归，问题可解。自底向上计算：C[1,2]→C[1,3]→...→C[1,n]。为不失一般性用C[i,j]表示由构成的BST的耗费。其中

1≤i≤j≤n。这棵树表示为。从中选择一个键作根节点，它的左子树为，右子树为。要求选择的k使得整棵树的平均查找次数C[i,j]最小。左右子树递归执行此过程。（根的生成过程）动态规划法生成最优BST算法原理动态规划法生成最优B动态规划法生成最优BST算法原理（续）akpk最优BST最优BST根层：L(ak)=1k-1=i：左子树缩为单节点。k+1=j：右子树缩为单节点。k<i：左子树为空树。k>j：右子树为空树。1≤i≤j≤n自顶向下分析递推计算式动态规划法生成最优BST算法原理（续）akpk最优最优根层：举例说明：动态规划法生成最优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过程举例说明：动态规划法举例说明：动态规划法生成最优BST过程（续1）

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

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

主表C

和

根表R

描述如下：举例说明：动态规划法生成最优BST过程（续2）举例说明：动动态规划算法：主表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]动态规划算法：主表C和根表K各阶段计算结果用主表C和根动态规划法算例的计算结果图本例计算结果：akpk最优BST最优BSTa10.1a30.4a40.30.2a2j=01234i=112332233333445根表R[i,j]根表可知，4个键的最优根下标为3即a3键。它的左子树为a1a2键，右子树为a4键。左子树是什么结构呢？再看根表，a1a2构成的最优子树根是a2。因为a1<a2，所以1键是2键的左节点。最终结果图动态规划法算例的计