《数据结构-算法设计方法讲义.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构-算法设计方法讲义.优秀PPT.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第十一章第十一章 算法设计方法算法设计方法11.111.1 分治法分治法11.211.2 动态规划动态规划11.311.3 贪心法贪心法11.411.4 回溯法回溯法11.511.5 分枝限界法分枝限界法11.1 11.1 分治法分治法对对于一个于一个输输入入规规模模为为n的的问题问题，用某种方法把，用某种方法把输输入入分割分割成成k个子集（个子集（1kn），从而），从而产产生生a个子个子问问题题，a个子个子问题问题解决后，再用某种方法解决后，再用某种方法组组合合成原成原来来问题问题的解。的解。分治法：分治法：分而治之分而治之一、一、排序算法中的分治法排序算法中的分治法选择选择排序排序 将n个
2、元素放在一个数组中，先通过n-1次比较选出其中的最小元素，与第1个元素交换 再在剩下的n-1个元素中选出最小的元素，与第2个元素交换 .规规模模为为n的的问题问题规规模模为为1的的问题问题规规模模为为n-1的的问题问题归并归并排序排序void MSort(RcdType SR,RcdType&TR1,int s,int t)void MSort(RcdType SR,RcdType&TR1,int s,int t)/将将将将SRs.tSRs.t归并排序为归并排序为归并排序为归并排序为TR1s.tTR1s.t if(s=t)TR1s=SRs;if(s=t)TR1s=SRs;else else m
3、=(s+t)/2;m=(s+t)/2;/将将将将SRs.tSRs.t平分为平分为平分为平分为SRs.mSRs.m和和和和SRm+1.tSRm+1.t Msort(SR,TR2,s,m,);Msort(SR,TR2,s,m,);/递归地将递归地将递归地将递归地将SRs.mSRs.m归并为有序的归并为有序的归并为有序的归并为有序的TR2s.mTR2s.m Msort(SR,TR2,m+1,t);Msort(SR,TR2,m+1,t);/递归地将递归地将递归地将递归地将SRm+1.tSRm+1.t归并为有序的归并为有序的归并为有序的归并为有序的TR2m+1.tTR2m+1.t Merge(TR2,T
4、R1,s,m,t);Merge(TR2,TR1,s,m,t);/将将将将TR2s.mTR2s.m和和和和TR2m+1.tTR2m+1.t归并到归并到归并到归并到TR1s.tTR1s.t /Msort/Msort快速排序快速排序从从输输入序列中随机的抽取一个元素入序列中随机的抽取一个元素a，以以a为为界，把全体元素分成：界，把全体元素分成：S1 S2 S3 小于小于a 等于等于a 大于大于a 若若S1、S3排好序了，排好序了，则则全体元素就有序了，全体元素就有序了，而而S1、S3的排序又可以用的排序又可以用这这种方法种方法void Qsort(SqList&L,int low,int high)
5、void Qsort(SqList&L,int low,int high)/对依次表对依次表对依次表对依次表L L中的子表中的子表中的子表中的子表L.rlow.highL.rlow.high作快速排序作快速排序作快速排序作快速排序 if(lowhigh)/if(lowhigh)/长度大于长度大于长度大于长度大于1 1 pivotloc=Partition(L,low,high);pivotloc=Partition(L,low,high);/将将将将L.rlow.highL.rlow.high一分为二一分为二一分为二一分为二 Qsort(L,low,pivotloc-1);Qsort(L,lo
6、w,pivotloc-1);/对低子表递归排序，对低子表递归排序，对低子表递归排序，对低子表递归排序，pivotlocpivotloc是枢轴位置是枢轴位置是枢轴位置是枢轴位置 Qsort(L,pivotloc+1,high);Qsort(L,pivotloc+1,high);/对高子表递归排序对高子表递归排序对高子表递归排序对高子表递归排序 /Qsort/Qsort想一想，想一想，在数据结构中还有哪些算法接受了在数据结构中还有哪些算法接受了分治法？分治法？二、分治法二、分治法应应用其他用其他实实例：例：折半折半(二分二分)查查找找线线性性时间选择时间选择(依次依次统计统计)给定线性序集中给定线
7、性序集中n个元素和一个整数个元素和一个整数k（1kn），请找出），请找出这这n个元素中第个元素中第k小的元素小的元素把这n个元素放在集合S中，从S中随机地选出一个元素a，以a为界，把全体元素分成：S1 S2 S3 小于a 等于a 大于a 再依据S1、S2、S3中元素个数在某个子集中找寻int select1(int k,int *S)if(length(S)=k)return(select1(k,S1);else if (length(S1)+length(S2)=k)return(a);else return(select1(k-length(S1)-length(S2),S3);该问题的规
8、模缩小到确定的程度就可以简洁地该问题的规模缩小到确定的程度就可以简洁地解决解决该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题利用该问题分解出的子问题的解可以合并为该利用该问题分解出的子问题的解可以合并为该问题的解问题的解该问题所分解出的各个子问题是相互独立的，该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题即子问题之间不包含公共的子问题 分治法选用分治法选用11.2 动态规划动态规划动态规动态规划方法涉及多划方法涉及多级级决策决策过过程中的最程中的最优优化化问题问题。求解的求解的问题问题分成很多分成很多级级或很多个子或很多个子问题问题（子
9、（子问题问题往往不是相往往不是相互独立的），然后按依次求解各子互独立的），然后按依次求解各子问题问题。前一子前一子问题问题的解的解为为后一子后一子问题问题的求解供的求解供应应了有用的信息。了有用的信息。在求解任一子在求解任一子问题时问题时，保留那些有可能达到最，保留那些有可能达到最优优的局部解，的局部解，丢丢弃其它局部解。弃其它局部解。依次解决各子依次解决各子问题问题，最，最终终一个子一个子问题问题的解就是初始的解就是初始问题问题的解。的解。最佳原最佳原则则：不不论论前面的状前面的状态态和策略如何，和策略如何，后面的最后面的最优优策略只取决于前一次策略所策略只取决于前一次策略所产产生的状生的状
10、态态。定义n阶方阵序列：v0v1v2641132Floyd算法算法最最长长公共子序列公共子序列给定序列X=x1,x2,xm，Z=z1,z2,zk，Z是X的子序列是指存在一个递增的下标序列i1,i2,ik，使得对于全部j=1,2,k有：zj=xij。X=A，B，C，B，D，A，B,Z=B，C，D，B,Z是序列X的子序列,递增下标序列为2，3，5，7问题：给定2个序列X和Y，当序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子公共子序列序列。请找出X和Y的最最长长公共子序列公共子序列。最最长长公共子序列的最佳原公共子序列的最佳原则则设序列X=x1,x2,xm和Y=y1,y2,yn的最长
11、公共子序列为Z=z1,z2,zk，则：(1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。(2)若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。Xm-1=x1,x2,xm-1,Yn-1=y1,y2,yn-1X=A，B，C，B，D，A，BY=B，D，C，A，B，AZ=?B，D，A，BB，C，A，BB，C，B，A动态规划方法的选用找出最佳原则，并刻划其结构特征递归地定义最佳解值以自底向上的方式计算出最佳解依据计算最佳解时得到的信息，构造最佳解11.3 11.3 贪心法贪心法贪心法贪心法某些
12、问题，有多个输入，一些约束条件 满足约束条件的一个解称为一个可能的解 最佳解是使目标函数最大/小的一个可能解贪心法也是一个多步决策法，每一步是当前看来最好的选择，构成问题的一个可能解的一部分（局部最优）并使目标函数的值变更最大其决策过程是以某些最优化量为依据的。背包背包问题问题问题：给定n种不同的物体和一个背包，物体i的总重量为wi，总价值为pi，背包的容量为M，如何装入物体，使背包的总重量不超过M而价值最大。（假设每种物体可以随意分割）形式化描述：M0,wi0,pi0,1in找一个n元向量(x1,x2,xn),约束条件 目标函数贪心策略1：每次选择价值最大的物体全部装进背包 这样目标函数增加
13、最快 当一种物体不能全部放进背包时，选择一个适当的0 xi1,使物体装满背包，剩下的xi置0。最优化量度为pi贪心策略2：让背包尽可能的多装物体 每次选择重量最轻的物体全部装进背包 当一种物体不能全部放进背包时，选择一个适当的0 xi1,使物体装满背包，剩下的xi置0。最优化量度为wi贪心策略3：每次选择单位重量价值最大的物体全部装进背包 当一种物体不能全部放进背包时，选择一个适当的0 xi=2)，并假设w0w1wn-1记 V 是频率为 w0 和 w1 的两个字符的父结点那么w0、w1是树 T 中最深的结点 T 中结点 V 换为一个叶结点 V(权等于w0+w1)，得到另一棵树 T 依据归纳假设
14、，T具有最小的外部路径长度 把 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 11.4 回溯法回溯法回溯法回溯法回溯法是一种避开不必要搜寻的穷举式搜寻方法，适用于解一些组合数相当大的问题。解能用一个n元式(x1,x2,.,xn)来表示（解向量）其中xiSi，要
15、求解向量满足判定函数B(x1,x2,.,xn)或使判定函数B(x1,x2,.,xn)的值极大或微小回溯法在问题的解空间树中，按深度优先策略，从根结点动身搜寻解空间树。算法搜寻至解空间树的随意一点时，先推断该结点是否包含问题的解。假如确定不包含，则跳过对子树的搜寻，逐层向其祖先结点回溯；否则，进入该子树，接着按深度优先策略搜寻。每个n元组的子组（对应部分解）(x1,x2,.,xi)应满足确定的约束条件。若已有满足约束条件的部分解，添加xi+1Si+1，检查(x1,x2,.,xi,xi+1)是否满足约束条件，若满足接着添加xi+2Si+2，若全部xi+1Si+1都不满足约束条件，就去掉xi，回溯到
16、(x1,x2,.,xi-1)，再添加尚未考虑过的xi，如此反复，直到找到一个解或全部解为止。42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65618 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41789101112131415161723451x1=1x1=2x1=3x1=4x2=234444444443333333x3=3x4=422222222211111111133333344444111111222224皇
17、后皇后问题问题的解空的解空间间扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个全部儿子已经产生的结点称做死结点深度优先的问题状态生成法：假如对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜寻之后，将R重新变成扩展结点，接着生成R的下一个儿子（假如存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它始终是扩展结点回溯法：为了避开生成那些不行能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些事实上不行能产生所需解的活结
18、点，以削减问题的计算量。具有限界函数的深度优先生成法称为回溯法11.5 11.5 分枝限界法分枝限界法分枝限界法分枝限界法分枝限界法与回溯类似，也是对状态空间树进行搜寻，分枝限界法更适合求满足约束条件的最优解，它运用更有效的约束函数来限制搜寻过程，更好地朝着状态空间树上有最佳解的分枝推动，以便尽快地找出一个最佳解。依据从一个活结点动身到达一个解结点的计算量为函数值，（1）对任何结点x，在找到解结点之前，以x为根的子树上必需产生的结点总数-生成结点最少的分枝限界法（2）从x到最近一个解结点的长度-只生成从根到最接近它的一个解结点的分枝限界法判定函数很难找到，只能用估值函数来代替 分支限界法常以广
19、度优先或以最小耗费（最大效益）优先的方式搜寻问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其全部儿子结点。在这些儿子结点中，导致不行行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程始终持续到找到所需的解或活结点表为空时为止。人有了学问，就会具备各种分析实力，明辨是非的实力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富学问，培育逻辑思维实力；通过阅读文学作品，我们能提高文学鉴赏水平，培育文学情趣；通过阅读报刊，我们能增长见识，扩大自己的学问面。有很多书籍还能培育我们的道德情操，给我们巨大的精神力气，鼓舞我们前进。