第六章基本算法设计策略——分治法

1、VI、基本算法设计策略基本策略分治法贪婪法动态规划法搜索策略6.16.1分治法分治法 快速排序算法的设计与分析快速变换:FFT及快速数论变换例：整数相乘N位整数相乘需要 次乘法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)(2NO从而，仅需3次乘法即可完成该算法即STARSSEN矩阵乘法的来源 qqprpzyxwxzqwypzyxwr)(1010)10)(10()(2422极大极小

2、同时查找数组中的最大最小元 用分治法解决上述问题： 如果集合中只有1个元素，则它既是最大值也是最小值； 如果有2个元素，则一次比较可得到最大和最小； 如果把集合分成两个子集合，由两组最大元比较得到最大元，两组最小元比较得到最小元。递归的应用这个算法！1) 2(, 0) 1 (222)(TTnTnTnT223)(nnT2FFT卷积：多项式的积： 及 ，并且 ，则DFT定义：序列 的离散傅氏变换为miiixaxA0)(niiixbxB0)(nmkkkxcxBxAxC0)()()(kjjkjkbac01, 0,Niix 102NnNjnkenxkX 该变换的逆变换为： 令 ，则上式可写为 ：其它的一

3、个重要性质：时域卷积对应于频域积。 1021NkNjnkNekXnxNjNeW210101NknkNNnknNWkXNnxWnxkX多项式的积两个多项式的积：其中此即卷积运算；10)(njjjxaxA10)(mjjjxbxB20)()()(mnjjjxcxBxAxCjkkjkjbac0 序列运算可用蝶形表示： 对于以下的8个的情形， 这一描述复杂并且不直观。 这一变换基于运算中的性质：从算法分析角度：于是：分别考虑对其奇数项和偶数项作傅氏变换：则 从而，可以将对N个量的傅氏变换变成为对两个规模更小的序列（在小为一半）的变换。这样，将变换的量大大减小。 1NNWknNNnNnnkNNnknNWn

4、xWnxWnxkX)12(120120210122nkNNnNnnkNEWnxWnxkX2/120120222knNNnNnnkNOWnxWnxkX2/1201202 12 1210kXWkXWnxkXOkNENnknN实际计算时，注意到对另外一半 时：2Nk knNNnNnnkNNnnknNNnnNNknNNnnkNNWnxWnxWnxWWnxWnxkNX)12(12012021010210)2( 122) 1(2210)2(kXWkXWnxkNXOkNENnnkNN复杂度 0)2(2)2(2)(TNNTNTmN212 ) 1()2 (mmmT令，则得从而快速傅氏变换的复杂性度为)log(N

5、NO应用：大数乘法利用FFT计算积A=1634，B=9827即)0 , 0 , 0 , 0 , 1 , 6 , 3 , 4(710aaa)0 , 0 , 0 , 0 , 9 , 8 , 2 , 7(710bbb2121)82exp(8iiWiW71. 071. 08iAiAiAAiAiAiAA54.842.52216.358.2616.358.22284.842.51476543210)81.1503. 2 ,71,19. 097.11, 4 ,19. 097.11,71,81.1503. 2 ,26(iiiiiiB对A与B进行逐一做积进行反变换：舍入成整数 ：数表示成 ： iiibac)64

6、.10376.128,1216,32.3828.30,24,32.3828.30,1216,64.10376.128,364(iiiiiiC)32. 0,01. 9 ,13.62,12.77,32.79,99.79,86.28,88.27(c)0 , 9 ,62,77,79,80,29,28(c7010iiic 即16057318 注意到可能的截断误差，使用数论变换更为适合)0 , 9 ,62,77,79,80,29,28(c)0 , 9 ,62,77,79,80,31, 8(c)0 , 9 ,62,77,79,83, 1 , 8(c)0 , 9 ,62,77,87, 3 , 1 , 8(c)

7、0 , 9 ,62,85, 7 , 3 , 1 , 8(c)0 , 9 ,70, 5 , 7 , 3 , 1 , 8(c)0 ,16, 0 , 5 , 7 , 3 , 1 , 8(c) 1 , 6 , 0 , 5 , 7 , 3 , 1 , 8(c考虑在模F的域上的变换：其中 ， 为在模F域上的逆。一般取F：Mersenne数 或Fermat数这样即可免去误差。缺陷：无直接的物理意义。10110NknkNnknkXNnxnxkX)(mod1FN1N12 ppM122ttF数论变换数论变换 取Fermat数F=257， 找到为 反数论变换后得)257(mod4166411611616416411

8、111416641161161641641111141664116116164164111114166411611616416411111444444414444414144414441444141414444444144441111444144414441111149423528423630353025202820211471812615105124211815121412107654963642328T)0 , 0 , 0 , 0 , 1 , 6 , 3 , 4(710aaa)0 , 0 , 0 , 0 , 9 , 8 , 2 , 7(710bbb4, 8N)(mod1FN)28,111,

9、65, 4 ,43,113,52,26()31,34,24, 6 ,104,30,81,14(88bTaT)31,81,18,24,103,49,100,107()(88bTaT)0 , 9 ,62,77,79,80,29,28(c)257(mod6419341)257(mod3222581贪婪法贪婪法以当前的信息为基础做出最佳决策 Huffman编码 例：分数分解 给定分数 qpnkkkqp11121分解为 其中nkkk211513152701512175算法：找到最接近的数i=1Label2: If p=1 then k(i)=q stop1/k(i)=largest reciprocal

10、 less than p/qp/q=p/q-1/k(i)goto label2;算法但上面算法给出的结果为513115830121158该算法非最优的：iOiwiv背包问题假定有一个包可放N个物品，每个物品重值，包能够放的重量为W。使在不超重的情况下装物品有最大的价值。例：背包可容纳重量：为W=100；物品重量价值180202301534014 使用贪婪法，则只能放入一个物品：即物品1，价值20；显然，最优解为物品2和物品3：价值29如果允许分数的，则可以找到最优解。该问题是NP完全问题！物品重量价值单价160200.333220100.5340120.3435110.314使用贪婪法：价值：

11、物品1、3，重量100，价值为32；单价：物品2、1，重量80，价值为30；最优值：物品2、3、4，重量95，价值33例：TSP假定旅行商要访问N个城市，每个城市都有到其它城市的路，要找一个最短的路径。E12111012- ABCDEA-1091512B10-111311C911-1110D151311-12算法：在剩下的城市中找最近的点做为下一个目标；使用贪婪法，从A出发得到的最短路径：ADBECA 15131110958151311109cost一个更好的选择：AEDCBA1212111110561212111110cost 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是

12、可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si m时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。一个实例 例如，设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别

13、为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,

14、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算法中，还应当考虑如何有效地找出满足条件iS,jV-S，

15、且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。 在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。 用这个办法实现的Prim算法所需的计算时间为O(n2)。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算法顺序得到的最小