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

VI、基本算法设计策略基本策略分治法贪婪法动态规划法搜索策略§6.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极大极小•同时查找数组中的最大最小元•用分治法解决上述问题：•如果集合中只有1个元素，则它既是最大值也是最小值；•如果有2个元素，则一次比较可得到最大和最小；；•如果把集合分成两个子集合，由两组最大元比较得到最大元，两组最小元比较得到最小元。递归的应用这个算法！1)2(,0)1(222)(TTnTnTnT223)(nnT2．FFT卷积：多项式的积：及，并且，则DFT定义：序列的离散傅氏变换为miiixaxA0)(niiixbxB0)(nmkkkxcxBxAxC0)()()(kjjkjkbac01,,0]},[{Niix102NnNjnkenxkX该变换的逆变换为：令，则上式可写为：其它的一个重要性质：时域卷积对应于频域积。1021NkNjnkNekXnxNjNeW21010][1][][][NknkNNnknNWkXNnxWnxkX多项式的积两个多项式的积：其中此即卷积运算；10)(njjjxaxA10)(mjjjxbxB20)()()(mnjjjxcxBxAxCjkkjkjbac0序列运算可用蝶形表示：对于以下的8个的情形，这一描述复杂并且不直观。这一变换基于运算中的性质：从算法分析角度：于是：分别考虑对其奇数项和偶数项作傅氏变换：则从而，可以将对N个量的傅氏变换变成为对两个规模更小的序列（在小为一半）的变换。这样，将变换的量大大减小。1NNWknNNnNnnkNNnknNWnxWnxWnxkX)12(120120210]12[]2[][][nkNNnNnnkNEWnxWnxkX2/1201202]2[]2[][knNNnNnnkNOWnxWnxkX2/1201202]12[]12[][][][][][10kXWkXWnxkXOkNENnknN实际计算时，注意到对另外一半时：2NkknNNnNnnkNNnnknNNnnNNknNNnnkNNWnxWnxWnxWWnxWnxkNX)12(12012021010210)2(]12[]2[)1(][][][]2[][][][]2[10)2(kXWkXWnxkNXOkNENnnkNN复杂度0)2(2)2(2)(TNNTNTmN212)1()2(mmmT令，则得从而快速傅氏变换的复杂性度为)log(NNO应用：大数乘法利用FFT计算积A=1634，B=9827即)0,0,0,0,1,6,3,4(710aaa)0,0,0,0,9,8,2,7(710bbb2121)82exp(8iiWiW71.071.08iAiAiAAiAiAiAA54.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.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(c7010iiic即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)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数这样即可免去误差。缺陷：无直接的物理意义。10110][][][][NknkNnknkXNnxnxkX)(mod1FN1N12ppM122ttF数论变换数论变换•取Fermat数F=257，找到为•反数论变换后得)257(mod4166411611616416411111416641161161641641111141664116116164164111114166411611616416411111444444414444414144414441444141414444444144441111444144414441111149423528423630353025202820211471812615105124211815121412107654963642328T)0,0,0,0,1,6,3,4(710aaa)0,0,0,0,9,8,2,7(710bbb4,8N)(mod1FN)28,111,65,4,43,113,52,26()31,34,24,6,104,30,81,14(88bTaT)31,81,18,24,103,49,100,107())((88bTaT)0,9,62,77,79,80,29,28(c)257(mod6419341)257(mod3222581贪婪法以当前的信息为基础做出最佳决策Huffman编码例：分数分解给定分数qpnkkkqp11121分解为其中nkkk211513152701512175算法：找到最接近的数i=1Label2:Ifp=1thenk(i)=qstop1/k(i)=largestreciprocallessthanp/qp/q=p/q-1/k(i)gotolabel2;算法但上面算法给出的结果为513115830121158该算法非最优的：iOiwiv背包问题假定有一个包可放N个物品，每个物品重值，包能够放的重量为W。使在不超重的情况下装物品有最大的价值。例：背包可容纳重量：为W=100；物品重量价值180202301534014使用贪婪法，则只能放入一个物品：即物品1，价值20；显然，最优解为物品2和物品3：价值29如果允许分数的，则可以找到最优解。该问题是NP完全问题！物品重量价值单价160200.333220100.5340120.3435110.314使用贪婪法：价值：物品1、3，重量100，价值为32；单价：物品2、1，重量80，价值为30；最优值：物品2、3、4，重量95，价值33例：TSP假定旅行商要访问N个城市，每个城市都有到其它城市的路，要找一个最短的路径。E12111012-ABCDEA-1091512B10-111311C911-1110D151311-12算法：在剩下的城市中找最近的点做为下一个目标；使用贪婪法，从A出发得到的最短路径：ADBECA15131110958151311109cost一个更好的选择：AEDCBA1212111110561212111110cost•活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。•设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题例：待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011s[i]130535688212f[i]4567891011121314图示•算法greedySelector的计算过程如右图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。说明•若被检查的活动i的开始时间si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。•贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。单源最短路径•给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1、算法基本思想•Dijkstra算法是解单源最短路径问题的贪心算法。•其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。•初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。•算法描述一个实例•例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。•Dijkstra算法的迭代过程：迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10∞301001{1,2}2602{1,2,4}450903{1,2,4,3}3604{1,2,4,3,5}510503060计算复杂性：对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n2)时间。算法的其余部分所需要时间不超过O(n2)。多机调度问题•多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。•约定，每个作业均可在任何一台机器上