第六章基本算法设计策略分治法讲义.ppt

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个元素，则一次比较可得到最大和最小；； 如果把集合分成两个子集合，由两组最大元比较得到最大元，两组最小元比较得到最小元。递归的应用这个算法！ 2．FFT 卷积： 多项式的积： 及 ，并且 ， 则 DFT定义：序列 的离散傅氏变换为 ?该变换的逆变换为： 令 ，则上式可写为 ： 其它的一个重要性质：时域卷积对应于频域积。 多项式的积 两个多项式的积： 其中 此即卷积运算； 序列运算可用蝶形表示： 对于以下的8个的情形， 这一描述复杂并且不直观。 这一变换基于运算中的性质： 从算法分析角度： 于是：分别考虑对其奇数项和偶数项作傅氏变换： 则 从而，可以将对N个量的傅氏变换变成为对两个规模更小的序列（在小为一半）的变换。这样，将变换的量大大减小。 实际计算时，注意到对另外一半 时： 复杂度 应用：大数乘法 利用FFT计算积A=1634，B=9827 即 对A与B进行逐一做积 进行反变换： 舍入成整数 ： 数表示成 ： 注意到可能的截断误差，使用数论变换更为适合 数论变换 考虑在模F的域上的变换： 其中 ， 为在模F域上的逆。 一般取F：Mersenne数 或Fermat数 这样即可免去误差。 缺陷：无直接的物理意义。 数论变换 取Fermat数F=257， 找到为 反数论变换后得 活动安排问题 例： 一个实例 例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。 Dijkstra算法的迭代过程： 60 30 50 10 5 {1,2,4,3,5} 4 60 3 {1,2,4,3} 3 90 50 4 {1,2,4} 2 60 2 {1,2} 1 100 30 ∞ 10 - {1} 初始 dist[5] dist[4] dist[3] dist[2] u S 迭代 * 令 ，则得 从而快速傅氏变换的复杂性度为 贪婪法 以当前的信息为基础做出最佳决策 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 假定