基本算法设计策略

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,VI、基本算法设计策略,基本策略,分治法,贪婪法,动态规划法,搜索策略,6.1分治法,快速排序算法的设计与分析,快速变换:FFT及快速数论变换,例：整数相乘,N位整数相乘需要 次乘法,4837*5261=,4837=48*100+37=100*w+x,5261=52*100+61=100*y+z,4837*5261=(100*w+x)*(100*y+z)=10000wy+100(wz+xy)+xz,(w+x)(y+z)=wy+(wz+xy)+xz,从而，仅需3次乘法即可完成,该算法即STARSSEN矩阵乘法的来源,极大极小,同时查找数组中的最大最小元,用,分治法,解决上述问题：,如果集合中只有1个元素，则它既是最大值也是最小值；,如果有2个元素，则一次比较可得到最大和最小；,如果把集合分成两个子集合，由两组最大元比较得到最大元，两组最小元比较得到最小元。递归的应用这个算法！,2FFT,卷积：,多项式的积：,及 ，并且 ，,则,DFT定义：序列 的离散傅氏变换为,该变换的逆变换为：,令 ，则上式可写为 ：,其它的一个重要性质：时域卷积对应于频域积。,多项式的积,两个多项式的积：,其中,此即卷积运算；,序列运算可用蝶形表示：,对于以下的8个的情形，,这一描述复杂并且不直观。,这一变换基于运算中的性质：,从算法分析角度：,于是：分别考虑对其奇数项和偶数项作傅氏变换：,则,从而，可以将对,N,个量的傅氏变换变成为对两个规模更小的序列（在小为一半）的变换。这样，将变换的量大大减小。,实际计算时，注意到对另外一半 时：,复杂度,令,，则得,从而快速傅氏变换的复杂性度为,应用：大数乘法,利用FFT计算积A=1634，B=9827,即,对A与B进行逐一做积,进行反变换：,舍入成整数 ：,数表示成 ：,即16057318,注意到可能的截断误差，使用,数论变换,更为适合,考虑在模F的域上的变换：,其中 ， 为在模,F,域上的逆。,一般取F：Mersenne数,或Fermat数,这样即可免去误差。,缺陷：,无直接的物理意义,。,数论变换,数论变换,取Fermat数F=257， 找到为,反数论变换后得,贪婪法,以当前的信息为基础做出最佳决策,Huffman编码,例：分数分解,给定分数,分解为,其中,算法：找到最接近的数,i=1,Label2: If p=1 then k(i)=q stop,1/k(i)=largest reciprocal less than p/q,p/q=p/q-1/k(i),goto label2;,算法,但上面算法给出的结果为,该算法非最优的：,背包问题,假定有一个包可放N个物品，每个物品,重,值,，,包能够放的重量为W。使在不超重的情况下装物品有最大的价值。,例：背包可容纳重量：为W=100；,物品,重量,价值,1,80,20,2,30,15,3,40,14,使用贪婪法，则只能放入一个物品：即物品1，价值20；,显然，最优解为物品2和物品3：价值29,如果允许分数的，则可以找到最优解。,该问题是NP完全问题！,物品,重量,价值,单价,1,60,20,0.333,2,20,10,0.5,3,40,12,0.3,4,35,11,0.314,使用贪婪法：,价值：物品1、3，重量100，价值为32；,单价：物品2、1，重量80，价值为30；,最优值：,物品2、3、4，重量95，价值,33,例：TSP,假定旅行商要访问N个城市，每个城市都有到其它城市的路，,要找一个最短的路径。,E,12,11,10,12,-,A,B,C,D,E,A,-,10,9,15,12,B,10,-,11,13,11,C,9,11,-,11,10,D,15,13,11,-,12,算法：在剩下的城市中找最近的点做为下一个目标；,使用贪婪法，从A出发得到的最短路径：,一个更好的选择：,活动安排问题,就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间f,i,且s,i,m时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(,nlogn,)。,一个实例,例如，设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,3。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。,最小生成树性质,用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质：,设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。,MST的证明.,Prim算法,设G=(V,E)是连通带权图，V=1,2,n。,构造G的最小生成树的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：,选取满足条件i,S，j,V-S，且cij最小的边，将顶点j添加到S中,。这个过程一直进行到S=V时为止。.,在这个过程中选取到的所有边恰好构成G的一棵最小生成树。,利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。,例如，对于右图中的带权图，按Prim算法选取边的过程如图所示。,例：,算法改进,在上述Prim算法中，还应当考虑如何有效地找出满足条件iS,jV-S，且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。,在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。,用这个办法实现的Prim算法所需的计算时间为O(,n,2,)。,3、Kruskal算法,Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。,将所有的边按权从小到大排序,。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法,连接两个不同的连通分支,：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的,同一个连通分支,中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。,例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如图所示。,说明,有关说明：,关于集合的一些基本运算可用于实现Kruskal算法。,按权的递增顺序查看等价于对优先队列执行deleteMin运算。可以用堆实现这个优先队列。,对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型并查集UnionFind所支持的基本运算。,算法复杂性：,当图的边数为e时，Kruskal算法所需的计算时间是O(,eloge,)。当e=,(,n,2,),时，Kruskal算法比Prim算法差，但当e=,o(,n,2,),时，Kruskal算法却比Prim算法好得多。,