《算法设计方法》PPT课件.ppt

《《算法设计方法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《算法设计方法》PPT课件.ppt（61页珍藏版）》请在三一办公上搜索。

1、第十一章 算法设计方法,11.1 分治法11.2 动态规划11.3 贪心法11.4 回朔法11.5 分枝限界法,11.1 分治法,对于一个输入规模为n的问题，用某种方法把输入分割成k个子集（1kn），从而产生k个子问题，k个子问题解决后，再用某种方法组合成原来问题的解。,分治法：分而治之,一、排序算法中的分治法,选择排序 将n个元素放在一个数组中，先通过n-1次比较选出其中的最小元素，与第1个元素交换 再在剩下的n-1个元素中选出最小的元素，与第2个元素交换.,T(n)=O(n2),归并排序,void MSort(RcdType SR,RcdType/将TR2s.m和TR2m+1.t归并到TR

2、1s.t/Msort,T(n)=n logn-n+1,快速排序,从输入序列中随机的抽取一个元素a，以a为界，把全体元素分成：S1 S2 S3 小于a 等于a 大于a 若S1、S3排好序了，则全体元素就有序了，而S1、S3的排序又可以用这种方法,void Qsort(SqList/对高子表递归排序/Qsort,T(n)=O(nlog2n),该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题;,分治法选用,11.2 动态规划,历史不会重演,1

3、0,F(n)=,1if n=0 or 1F(n-1)+F(n-2)if n 1,递归算法的伪代码:F(n)1if n=0 or n=1 then return 12elsereturn F(n-1)+F(n-2),考虑Fibonacci序列F(n),11,计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,12,计算F(7),计算F(2)重复8次!,F7,F6,F5,F5,F4,F3,F3

4、,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,13,The execution of F(7),计算 F(3)重复 5 次!,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,14,计算 F(7),多次重复计算!如何避免?,F7,F6,F5,F

5、5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,15,改进的想法,备忘录 当 F1(i)被计算后,保存它的值 当再次计算F1(i)时,只需要从内存中取出即可,F1(n)1 if vn 0 then2 vn F1(n-1)+F1(n-2)3 return vn,Main()1 v0=v1 12 for i 2 to n do3 vi=-14 output F1(n),16,再计算F(7),v0v1v2v3v4v5v6v7

6、,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,F(i)=Fi,17,再计算F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,18,再计算F(7),v0v1v2

7、v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,19,再计算F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,20,再计算F(7),v0v1

8、v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,21,再计算F(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,22,F1,F0,再计算F

9、(7),v0v1v2v3v4v5v6v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,23,F1,F0,F2,F1,F0,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,v0v1v2v3v4v5v6v7,24,F1,F0,F2

10、,F1,F0,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,v0v1v2v3v4v5v6v7,25,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F1,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,v0v1v2v3v4v5v6v7,26,F1,F0,

11、F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F1,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,v0v1v2v3v4v5v6v7,27,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,v0v1v2v3v4v5v6v7,28,F1,F

12、2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F0,F1,F4,v0v1v2v3v4v5v6v7,29,新的实现节约了大量的时间,我们能够做得更好吗?,注意到使用备忘录虽然可以减少重复计算,但是仍然需要函数调用以及参数,这些会浪费许多时间.事实上,计算F(i),我们只需要计算F(i-1)&F(i-2)改进的想法以自底向上的方式,即由简单到复杂开始计算依次计算F(2)(已知F(0)=F(1)=1),F(3),

13、F(4),F2(n)1 F0 12 F1 13 for i 2 to n do4Fi Fi-1+Fi-25 return Fn,30,递归 vs 动态规划,递归:F(n)1if n=0 or n=1 then return 12elsereturn F(n-1)+F(n-2),动态规划:F2(n)1 F0 12 F1 13 for i 2 to n do4Fi Fi-1+Fi-25 return Fn,太慢!,有效!时间复杂度仅为O(n),31,方法的总结,写出一个递归公式,这个公式给出了问题与其子问题的解之间的关系E.g.F(n)=F(n-1)+F(n-2).用表(通常用数组)记录子问题的解

14、,以便保存和以后的检索 以从最简单问题的解填起,以自底向上的方式填表这就保证了,当我们求解一个子问题的时候,所有与子相关的子子问题,都可以从表中直接取用,而不必重新计算,由于20世纪40年代末期,还没有出现计算,这个动态填表的方法称为动态规划.,32,动态规划,动态规划算法常用来求解最优化问题，设计一个动态规划算法通常有以下四个步骤找出最优解的结构；递归定义一个最优解的值；以自底向上的方式（从最简单问题开始入手）计算出最优解的值；根据计算最优解的值的信息，构造一个最优解。,11.3 贪心法,某些问题，有多个输入，一些约束条件 满足约束条件的一个解称为一个可能的解 最佳解是使目标函数最大/小的一

15、个可能解,贪心法也是一个多步决策法，每一步是当前看来最好的选择，构成问题的一个可能解的一部分（局部最优）并使目标函数的值变化最大其决策过程是以某些最优化量为依据的。,背包问题,问题：给定n种不同的物体和一个背包，物体i的总重量为wi，总价值为pi，背包的容量为M，如何装入物体，使背包的总重量不超过M而价值最大。（假设每种物体可以任意分割）,形式化描述：M0,wi0,pi0,1in,找一个n元向量(x1,x2,xn),约束条件 目标函数,贪心策略1：每次选择价值最大的物体全部装进背包 这样目标函数增加最快 当一种物体不能全部放进背包时，选择一个适当的0 xi1,使物体装满背包，剩下的xi置0。最

16、优化量度为pi,n=3,M=40,w=(28,15,24),p=(35,25,24),x1=1,x2=4/5,x3=0 wixi=28+12=40 pixi=35+4/5*25=55,贪心策略2：让背包尽可能的多装物体 每次选择重量最轻的物体全部装进背包 当一种物体不能全部放进背包时，选择一个适当的0 xi1,使物体装满背包，剩下的xi置0。最优化量度为wi,n=3,M=40,w=(28,15,24),p=(35,25,24),x3=1,x2=1,x1=1/28 wixi=24+15+28*1/28=40 pixi=24+25+35*1/28=50.25,贪心策略3：每次选择单位重量价值最大的

17、物体全部装进背包 当一种物体不能全部放进背包时，选择一个适当的0 xi1,使物体装满背包，剩下的xi置0。最优化量度为pi/wi,贪心法不一定能产生最佳解，需要证明其能够找到最佳解,n=3,M=40,w=(28,15,24),p=(35,25,24),x2=1,x1=25/28,x3=0 wixi=15+28*25/28=40 pixi=25+25/28*35=56.25,哈夫曼树构造算法(1)根据给定的n个权值W1,W2,.,Wn 构成n棵二叉树的集合F=T1,T2,.,Tn;其中每棵二叉树Ti只有一个权为Wi的根结点,左右子树均空(2)在F中选取两棵根结点权值最小的树作为左右子树，设为Ti

18、，Tj,构造一棵新的二叉树Tk，且Ti、Tj根结点的权值之和为 新的二叉树Tk的根结点的权值(3)把Ti,Tj从F中删去，把Tk插入到F中(4)重复(2),(3)直到F中只含有一棵树为止,此树即为哈夫曼树,n=2,Huffman树一定是带权路径长度最短的二叉树（最优树）假设有n-1个叶结点的Huffman树是最优树,设一棵Huffman树 T 有 n 个叶结点(n=2)，并假设w0w1wn-1记 V 是频率为 w0 和 w1 的两个字符的父结点那么w0、w1是树 T 中最深的结点 T 中结点 V 换为一个叶结点 V(权等于w0+w1)，得到另一棵树 T 根据归纳假设，T具有最小的外部路径长度

19、把 V展开为V（w0+w1），T还原为 T，则 T 也应该是带权路径长度最小的 定理成立,普里姆算法Prim 设N=（V，E）为连通网 用TE表示N上最小生成树边的集合(1)从V中选一顶点u0加入U，TE=(2)对所有uU，vV-U，（u，v）E,找一条代价最小的边（u0，v0）加入TE,并把v0加入U(3)重复(2)，直到U=V为止,则（V，TE）为N的最小生成树,11.4 回溯法,进行系统搜索的一种方法尽可能的利用剪枝技术,42,回溯(Backtracking),介绍 假如你要在许多不同的选择中做一系列的决策,那么你没有足够的信息来帮助做出选择每个决策都将产生一些新的选择一些决策的序列(可

20、能不只一个)也许就是问题的解 回溯算法系统的尝试搜索各种决策序列,直到找到一个令你满意的决策序列,43,术语,有3个节点被用到,一棵由节点构成的树.,回溯算法可以看作是为了找某个特定的叶子节点而进行系统搜索的一种方法,44,术语(Terminology),在一棵树中,非叶子节点是其他一个或更多节点的父节点(它的子节点)树中的每个节点(除了根节点)都有一个父节点,通常 我们都从下画树.根节点在顶部,45,回溯的思想 回溯是穷举方法的一个改进,它在所有可行的选择中，系统地搜索问题的解.它假定解可以由向量形式(x1,x2,xn)来表示,其中xi的值表示在第i次选择所作的决策值,并以深度优先的方式遍历

21、向量空间,逐步确定xi 的值，直到解被找到.回溯法列举出解空间中所有可能的情形来确保解的正确性,46,假设我们已经确定部分解的集合(x1,x2,xi),在此基础上通过增加解元素 xi+1来扩展解,确定xi+1的值后,我们要测试(x1,x2,xi+1)是否仍是可行解.回溯算法的基本步骤如下 1.定义问题的解空间.这个空间必须包含一个问题的最优解.解的空间 如果Si 是 xi的范围,那么 S1 S2.Sn 是问题的解空间,47,通常这个解空间是非常巨大的,所以搜索一个目标解的代价是很难想象的.为了使回溯算法更有效率,我们必须缩小搜索空间.2.组织好解空间以便使搜索更容易 典型的组织方式是利用图或树

22、的结构.3.以深度优先方式搜索解空间，利用剪枝函数来避免搜索进入不可能得到解的子空间.,48,解空间树(Solution Space Tree),start,?,?,dead end,dead end,?,?,dead end,dead end,?,success!,dead end,49,解空间的组织,任何时候,在构造问题解的时候,都包含做出一系列的决策,如果我们将做出的决策画出来,这个图就象一棵树.建立一个树型结构,使得树叶对应解空间的一个解,而内部节点的一个分支,对应一个决策,这样,便可以将解空间组织为一棵解空间树.回溯法可以很容易地被用来搜索一个集合的所有子集合或是排列.,50,当我们

23、要解决的问题是要求一个使问题最优的n个元素的子集,问题的解空间常可以组织成一棵子集树构造所有的子集 n个元素的集合有多少个子集?如果每个 Si 的大小是 k,对每个 xiSi,共有 kn 个子集子集树,51,1.货箱装载问题,问题 给定n个货箱,货箱i 重为 wi.船可以装载的货箱总重量为 W.货箱装载问题是在不使船翻的前提下装载尽可能多的货箱.解空间 假设解可以由向量(x1,x2,xn)表示,xi0,1,xi=1 表示货箱 i 被装上船,xi=0表示货箱 i 不装上船.,52,货箱装载问题可以形式地描述如下:解空间树 有 2n 个叶子的子集树在第 j层，节点的展开由 xj+1的值决定.,Su

24、btree:n=4,1,0,x2,0,1,0,x1,x3,x4,1,54,约束函数 令 cw(i)表示到第 i层的当前重量,记为 则约束函数为 剪枝 若，则停止搜索第 i层及其下面的层,否则，继续搜索.,对 n=4,w=8,6,2,3,W=12进行回溯,1,x1,1,0,1,x2,0,x4,x3,8,14,8,1,0,1,0,1,0,C(t),活动节点,10,13,10,11.5 分支限界,基于广度优先搜索的一种穷举算法尽可能的利用剪支技术,57,与回溯法一样，分支限界是搜索一个解空间，而这个解空间通常组织成一棵树。常见的树结构为子集树和排列树。回溯以深度优先搜索一棵树，而分支限界常常以广度优

25、先或最小耗费优先的方法搜索这棵树。解空间树.分支限界法常用于解最优化问题.确定所求问题的上下界在每个节点使用限界函数来屏蔽节点或是扩展节点.然后,使用目前为止最好的解来帮助剪枝,直到所有顶点被遍历或是被剪掉.,58,Ideas,分支限界法也可以说是对回溯法的一个改进.假如我们在考虑一个最小化问题时:我们的想法是使所有的可能目标函数值必须维持在上界(目前为止最好的解的目标函数值)与下界之间.如果在某一数量的决策之后（转移操作），我们到达一个节点，在这个节点上我们得到的下界大于或等于上界，那么就没有必要在扩展这个节点既不需在延伸这个分支。对于最大化问题规则正好相反,59,首先，分支限界是对最优化问

26、题可行解进行剪枝的一个方法。将搜索集中在有希望得到解的分支上。也就是说，在基于上下界和可以得到最优解的基础上,扩展分支,理由是发展这样的分支可以得到更好的上下界，从而可以剪去更多的分支总之，不要单纯以DFS或BFS来进行搜索，而要结合起来进行搜索.,60,分之限界需要的步骤如下:1.对所求的问题定义一个解空间。这个解空间至少包含这个问题的最优解。2.对解空间进行组织，以便能更好的搜索。比较常见组织方式有图或是一棵树。3.以广度优先搜索的方式搜索解空间，使用限界函数来避免那些不能得到解的子空间。,61,分支限界是有系统的搜索一个解空间的另一个方法。首先在扩展节点的扩展方法上，它不同于回溯。每个活节点变成扩展节点只有一次。当一个节点变成扩展节点时，我们展开从它可到达的所有节点。其中那些不能得到可行解的节点去掉（成为死节点）,把剩下来的节点加到活节点的表中，然后，从这个表中选一个节点作为下一个扩展节点。,