基本算法设计策略分治法

VI、基本算法设计策略基本策略分治法贪婪法动态规划法搜索策略6.16.1分治法分治法快速排序算法的设计与分析快速变换:FFT及快速数论变换例：整数相乘N位整数相乘需要O(N2)次乘法4837*5261=4837=48*100+37=100*w+x5261=52*100+61=100*y+z4837*5261=(100*w+x)*(100*y+z)=10000wy+100(wz+xy)+xz(w+x)(y+z)=wy+(wz+xy)+xz)z?y)(x?w(r?wy?p?xz?q?q?)q?p?r(10?p10)?z?y10)(x?w10(2242从而，仅需3次乘法即可完成该算法即STARSSEN矩阵乘法的来源极大极小?同时查找数组中的最大最小元用分治法解决上述问题：如果集合中只有1个元素，则它既是最大值也是最小值；如果有2个元素，则一次比较可得到最大和最小；如果把集合分成两个子集合，由两组最大元比较得到最大元，两组最小元比较得到最小元。递归的应用这个算法！?nn?T(n)?T?T?2?22?T(1)?0,T(2)?1?3T(n)?n?222FFT卷积：多项式的积：ikA(x)?ax及B(x)?A(x)B(x)?c x，(x)?bi?kix，并且Cminm?nk?0i?0i?0ajbk?j则ck?j?0k?xi,i?0,?,N?1DFT定义：序列的离散傅氏变换为?X k?xne?n?0N?1?jnk2?N?jnk 2?N该变换的逆变换为：x?n?X k eN?11Nk?0令WN?e?j2?N，则上式可写为：knXk?xnWNn?0N?11xn?N?XkWk?0N?1?nkN其它的一个重要性质：时域卷积对应于频域积。多项式的积两个多项式的积：A(x)?ajxj?0n?1jB(x)?bjxj?0m?1jC(x)?A(x)B(x)?c x?jjj?0n?m?2a其中cj?kbj?kk?0j此即卷积运算；序列运算可用蝶形表示：对于以下的8个的情形，这一描述复杂并且不直观。W?1这一变换基于运算中的性质：从算法分析角度：NNN?1n?0?12knNn?0NN(2n?1)kXk?xnW?x2n?W?x2n?1?W?N?122nkNn?0于是：分别考虑对其奇数项和偶数项作傅氏变换：E2nknkX k?x2n?W?x2n?W?N?N/2n?0n?0N?12N?12X k?x2n?1?W?x2n?1?W?On?0N?12N?122nkNn?0knN/2则knEkOXk?xnW?X k?W?X k?NNn?0N?1从而，可以将对 N个量的傅氏变换变成为对两个规模更小的序列（在小为一半）的变换。这样，将变换的量大大减小。N实际计算时，注意到对另外一半k?时：2NX?k?xnW?2n?0N?12n?0N?12n?0N?1N(?k)n2Nknn?xnW W?xnW?(?1)?Nn?0N?1nNN?1kn2NNn?02nk(2n?1)k?x2n?W?x2n?1?W?N?NNEkOX?k?xnW?X k?W?X k?N2n?0N?1N(?k)n2N复杂度NN?T(N)?2T()?22?T(2)?0?m，则得令N?2T(2)?(m?1)2mm?1从而快速傅氏变换的复杂性度为O(Nlog N)应用：大数乘法利用FFT计算积A=1634，B=9827b?b?(7,2,8,9,0,0,0,0)a a?a?(4,3,6,1,0,0,0,0)b0170172i11W?exp()?i8822?0.71?0.71i即W8?AAAAAAA0?14?2?2i?2.58?3.16 i?6?2.58?3.16 i?2?2i?5.42?8.54 iA1?5.42?8.84 i234567B?(26,2.03?15.81 i,?1?7i,11.97?0.19i,4,11.97?0.19i,?1?7i,2.03?1.8 i)a对A与B进行逐一做积ci?i?biC?(364,?128.76?103.64i,16?12i,30.28?38.32i,24,30.28?38.32i,16?12i,?12.76?1.6 i)进行反变换：c?(27.88,28.86,79.99,79.32,77.12,62.13,9.01,?0.32)舍入成整数：c?(28,29,80,79,77,62,9,0)数表示成：ic?10?ii?07c?(28,29,80,79,77,62,9,0)c?(8,31,80,79,77,62,9,0)c?(8,1,83,79,77,62,9,0)c?(8,1,3,87,77,62,9,0)c?(8,1,3,7,85,62,9,0)c?(8,1,3,7,5,70,9,0)c16057318?(8,1,3,7,5,0,16,0)c?(8,1,3,7,5,0,6,1)截断误差，使用数论变换更为适合即注意到可能的数论变换考虑在模F的域上的变换：Xk?xn?n?0N?1k?0N?1knxn?NN?1?Xk?nk其中?1(modF)，N为在模F域上的逆。p2?1一般取F：Mersenne数Mp?t或Fermat数2?1F1t?2?这样即可免去误差。缺陷：无直接的物理意义。数论变换?NN?8,?4?(mod F)取Fermat数F=257，找到为?1a a?a?(4,3,6,1,0,0,0,0)017b b?b?(7,2,8,9,0,0,0,0)017?14?193?64(mod257)?18?225?32(mod 257)11?14?2?14?314?T?48?14?5?14?614?7?14?112344111111111111?45674444?141664?1?4?16?64?46101214?441444?116?1?16116?1?16?6912151821444444?164?164?1?6416?4?(mod257)?1220281?11?11?11?1?141414?101520253035?1?416?64?14?1664444444?12183036421?16?1161?16?116441444?1421283542491?64?16?4?164164444444?反数论变换后得T a(14,?81,30,104,6,24,?34,?31)8Tb?(26,?52,?113,43,4,65,111,?28)8(T a)(T b)?(107,100,?49,103,24,18,81,?31)88c?(28,29,80,79,77,62,9,0)贪婪法贪婪法以当前的信息为基础做出最佳决策Huffman编码例：分数分解给定分数p分解为其中qp111q?k?1k2kn1?k2?kn25?113?1557?1112?5?70k算法算法：找到最接近的数i=1Label2:If p=1 then k(i)=q stop1/k(i)=largest reciprocal less than p/qp/q=p/q-1/k(i)goto label2;该算法非最优的：但上面算法给出的结果为811?15230811?1535背包问题假定有一个包可放 N个物品，每个物品Oi重wi值vi，包能够放的重量为 W。使在不超重的情况下装物品有最大的价值。例：背包可容纳重量：为 W=100；物品123重量803040价值201514使用贪婪法，则只能放入一个物品：即物品1，价值20；显然，最优解为物品2和物品3：价值29如果允许分数的，则可以找到最优解。该问题是NP完全问题！物品1234重量60204035价值20101211单价0.3330.50.30.314使用贪婪法：价值：物品1、3，重量100，价值为32；单价：物品2、1，重量80，价值为30；最优值：物品2、3、4，重量95，价值33例：TSP假定旅行商要访问N个城市，每个城市都有到其它城市的路，要找一个最短的路径。算法：在剩下的城市中找最近的点做为下一个目标；AABCD-10915B10-1113C911-11D151311-E12111012E12111012-使用贪婪法，从 A出发得到的最短路径：910111315A?C?E?B?D?Acos t?9?10?11?13?15?5一个更好的选择：1011111212A?B?C?D?E?Acost?10?11?11?12?12?5活动安排问题?活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。?设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i都有一个要求使用该资源的起始时间 si和一个结束时间fi,且sim时，首先将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，且u?U，v?V-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在 G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。?MST的证明.Prim算法?设G=(V,E)是连通带权图，V=1,2,n。?构造G的最小生成树的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，j V-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。.?在这个过程中选取到的所有边恰好构成G的一棵最小生成树。?利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。?例如，对于右图中的带权图，按Prim算法选取边的过程如图所示。例：算法改进?在上述Prim算法中，还应当考虑如何有效地找出满足条件i?S,j?V-S，且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。?在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。?用这个办法实现的Prim算法所需的计算时间2为O(n)。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=?(n2)时，Kruskal算法比Prim算法差，但当e=o(n2)时，Kruskal算法却比Prim算法好得多。