《第十一章算法设计方法说课材料》由会员分享，可在线阅读，更多相关《第十一章算法设计方法说课材料（61页珍藏版）》请在金锄头文库上搜索。
1、第十一章 算法设计方法,11.1 分治法 11.2 动态规划 11.3 贪心法 11.4 回朔法 11.5 分枝限界法,11.1 分治法,对于一个输入规模为n的问题，用某种方法把输入分割成k个子集（1kn），从而产生k个子问题，k个子问题解决后，再用某种方法组合成原来问题的解。,分治法：分而治之,一、排序算法中的分治法,选择排序 将n个元素放在一个数组中， 先通过n-1次比较选出其中的最小元素，与第1个元素交换 再在剩下的n-1个元素中选出最小的元素，与第2个元素交换 .,T(n)=O (n2),归并排序,快速排序,从输入序列中随机的抽取一个元素a， 以a为界，把全体元素分成： S1 S2 S
2、3 小于a 等于a 大于a 若S1、S3排好序了，则全体元素就有序了， 而S1、S3的排序又可以用这种方法,void Qsort(SqList /对高子表递归排序 /Qsort,T(n)=O(nlog2n),该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题; 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题;,分治法选用,11.2 动态规划,历史不会重演,10,F(n) =,1if n = 0 or 1 F(n-1) + F(n-2)if n 1,递归算法的伪代码: F(n) 1i
3、f n=0 or n=1 then return 1 2elsereturn F(n-1) + F(n-2),考虑Fibonacci序列F(n),11,计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,12,计算F(7),计算F(2)重复8次!,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,
4、F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,13,The execution of F(7),计算 F(3) 重复 5 次!,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,14,计算 F(7),多次重复计算! 如何避免?,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,
5、F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,15,改进的想法,备忘录 当 F1(i)被计算后,保存它的值 当再次计算F1(i)时,只需要从内存中取出即可,F1(n) 1 if vn 0 then 2 vn F1(n-1)+F1(n-2) 3 return vn,Main() 1 v0 = v1 1 2 for i 2 to n do 3 vi = -1 4 output F1(n),16,再计算F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F
6、2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,F(i)=Fi,17,再计算F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,18,再计算F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F
7、5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,19,再计算F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,20,再计算F(7),v0 v1 v2 v3 v4
8、v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,21,再计算F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,22,F1,F0,再
9、计算F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,23,F1,F0,F2,F1,F0,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,v0 v1 v2 v3 v4 v5
10、v6 v7,24,F1,F0,F2,F1,F0,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,v0 v1 v2 v3 v4 v5 v6 v7,25,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F1,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,v0
11、 v1 v2 v3 v4 v5 v6 v7,26,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F1,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,v0 v1 v2 v3 v4 v5 v6 v7,27,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F
12、0,F2,F1,F4,F4,v0 v1 v2 v3 v4 v5 v6 v7,28,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,再计算F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F0,F1,F4,v0 v1 v2 v3 v4 v5 v6 v7,29,新的实现节约了大量的时间,我们能够做得更好吗?,注意到 使用备忘录虽然可以减少重复计算,但是仍然需要函数调用以及参数,这些会浪费许多时间 . 事实上,计算F(i),我们只需要计算F(i-1) 其中每棵二
13、叉树Ti只有一个权为Wi的根结点, 左右子树均空 (2)在F中选取两棵根结点权值最小的树作为左右子树， 设为Ti，Tj, 构造一棵新的二叉树Tk， 且Ti、Tj根结点的权值之和为 新的二叉树Tk的根结点的权值 (3)把Ti ,Tj从F中删去，把Tk插入到F中 (4)重复(2),(3)直到F中只含有一棵树为止, 此树即为哈夫曼树,n = 2, Huffman树一定是带权路径长度最短的二叉树（最优树） 假设有n-1个叶结点的Huffman树是最优树,设一棵Huffman树 T 有 n 个叶结点(n=2)， 并假设w0w1wn-1 记 V 是频率为 w0 和 w1 的两个字符的父结点 那么w0、 w1是树 T 中最深的结点 T 中结点 V 换为一个叶结点 V(权等于w0 + w1) ， 得到另一棵树 T 根据归纳假设，T具有最小的外部路径长度 把 V展开为V（ w0 + w1 ）， T还原为 T， 则 T 也应该是带权路径长度最小的 定理成立,普里姆算法Prim 设N=（V，E）为连通网 用TE表示N上最小生成树边的集合 (1)从V中选一顶点u0加入U，TE= (2)对所有uU，vV-U，（u，v）E,找一条代价最小的边（u0，v0）加入TE,并把v0加入U (3)重复(2)，直到U=V为止, 则（V，TE）为N的最小生成树,11.4 回溯法,进行系统搜索的一种方法 尽可
