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

1、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从而，仅需3次乘法即可完成该算法即STARSSEN矩阵乘法的来源 极大极小同时查找数组中的最大最小元用分治法处理上述问题：假设集合中只需1个元素，那么它既是最大值也是最小值；假设

2、有2个元素，那么一次比较可得到最大和最小；假设把集合分成两个子集合，由两组最大元比较得到最大元，两组最小元比较得到最小元。递归的运用这个算法！2FFT卷积：多项式的积： 及 ，并且 ，那么DFT定义：序列 的离散傅氏变换为该变换的逆变换为： 令 ，那么上式可写为 ：其它的一个重要性质：时域卷积对应于频域积。 多项式的积两个多项式的积：其中此即卷积运算； 序列运算可用蝶形表示： 对于以下的8个的情形， 这一描画复杂并且不直观。 这一变换基于运算中的性质：从算法分析角度：于是：分别思索对其奇数项和偶数项作傅氏变换：那么 从而，可以将对N个量的傅氏变换变成为对两个规模更小的序列在小为一半的变换。这样

3、，将变换的量大大减小。 实践计算时，留意到对另外一半 时：复杂度 令，那么得从而快速傅氏变换的复杂性度为运用：大数乘法利用FFT计算积A=1634，B=9827即对A与B进展逐一做积进展反变换：舍入成整数 ：数表示成 ： 即16057318 留意到能够的截断误差，运用数论变换更为适宜思索在模F的域上的变换：其中 ， 为在模F域上的逆。普通取F：Mersenne数 或Fermat数这样即可免去误差。缺陷：无直接的物理意义。数论变换数论变换取Fermat数F=257， 找到为反数论变换后得贪婪法以当前的信息为根底做出最正确决策 Huffman编码 例：分数分解 给定分数 分解为 其中算法：找到最接

4、近的数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;算法但上面算法给出的结果为该算法非最优的：背包问题假定有一个包可放N个物品，每个物品重值，包可以放的分量为W。使在不超重的情况下装物品有最大的价值。例：背包可包容分量：为W=100；物品分量价值180202301534014运用贪婪法，那么只能放入一个物品：即物品1，价值20；显然，最优解为物品2和物品3：价值29假设允许分数的，那么可以找到最优解。该问题是NP完全问题！物品分量价值单价160

5、200.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出发得到的最短途径：一个更好的选择：活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪婪算法有效求解的很好例子。该问题要求高

6、效地安排一系列争用某一公共资源的活动。贪婪算法提供了一个简单、美丽的方法使得尽能够多的活动能兼容地运用公共资源。设有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加工处置。各作业所需的处置时间分别为2,14,4,16,6,5,3。按算法greed

7、y产生的作业调度如以下图所示，所需的加工时间为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的最小生成树的P

8、rim算法的根本思想是：首先置S=1，然后，只需S是V的真子集，就作如下的贪婪选择：选取满足条件iS，j V-S，且cij最小的边，将顶点j添加到S中。这个过程不断进展到S=V时为止。.在这个过程中选取到的一切边恰好构成G的一棵最小生成树。利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T一直包含G的某棵最小生成树中的边。因此，在算法终了时，T中的一切边构成G的一棵最小生成树。 例如，对于右图中的带权图，按Prim算法选取边的过程如下图。例：算法改良在上述Prim算法中，还该当思索如何有效地找出满足条件iS,jV-S，且权cij最小的边(i,j)。实现这个目的的较简单的方法是设置2个

9、数组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算法顺序得到的最小生成树上的边如下图。阐明有关阐明：关于集合的一些根本运算可用于实现Kruskal算法。按权的递增顺序查看等价于对优先队列执行deleteMin运算。可以用堆实现这个优先队