分治算法详解课件.ppt

分治,1,将要求解的较大规模的问题分割成k个更小规模的子问题。,算法总体思想,n,T(n/m),T(n/m),T(n/m),T(n/m),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。, ,2,算法总体思想,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。, ,3,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=, ,4,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。,5,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,6,divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 ,分治法的基本步骤,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,7,分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件,分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。分析：,该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。,8,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。,据此容易设计出二分搜索算法：template int BinarySearch(Type a, const Type,算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。,9,分治法求数组最大值,给定n个元素a0:n-1，现要在这n个元素中找出最大值x。,思路：将数组一分为二求前半部分的最大值位置，求后半部分最大值位置（分的过程）求前后两部分最大值位置。（合的过程）,10,合并排序,基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。,void MergeSort(Type a, int left, int right) if (leftright) /至少有2个元素 int i=(left+right)/2; /取中点 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); /合并到数组b copy(a, b, left, right); /复制回数组a ,复杂度分析T(n)=O(nlogn) 渐进意义下的最优算法,11,合并排序,算法mergeSort的递归过程可以消去。,12,合并排序,最坏时间复杂度：O(nlogn)平均时间复杂度：O(nlogn)辅助空间：O(n),13,棋盘覆盖,在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,14,棋盘覆盖,当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。,15,棋盘的识别,首先，子棋盘的规模是一个必要的信息，有了这个信息，只要知道左上角的方格在原棋盘中的行、列号就可以标识这个子棋盘了；其次子棋盘中残缺方格或“伪”残缺方格直接用它们在原棋盘中的行、列号标识。 tr表示棋盘左上角方格的行号； tc表示棋盘左上角方格的列号 dr表示特殊方格所在的行号 dc表示特殊方格所在的列号， size表示方形棋盘行数或列数。,16,棋盘数据结构,用二维数组Board来模拟棋盘，Board11是棋盘的左上角方格。title表示L 型骨牌的编号，其初始值为0。覆盖残缺棋盘所需要的三格板数目为：(size*size -1)/3。将这些 三格板编号为1到(size*size-1)/3，则将覆盖残缺棋盘的三格板编号存储在数组Board的对应位置，这样输出数组内容就是问题的解。如果是一个4 4的棋盘，特殊方格为(2,1)，那么程序的输出为对于如图8-6(a)所示的棋盘，其结果为8-6(b)所示的棋盘。其中特殊方格为0，相同数字的为同一骨牌。,17,棋盘覆盖,void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角,boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s ,复杂度分析T(n)=O(4k) 渐进意义下的最优算法,18,循环赛日程表,设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。,按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,19,本题方法有很多，递归是其中一种比较容易理解的方法。图8所示是k=3时的一个可行解，它是4块拼起来的。左上角是k=2时的一组解，左下角是左上角每个数加4得到，而右上角、右下角分别由左下角、左上角复制得到的。,20,#include using namespace std;int table100100;void Creattable(int r1,int c1,int r2,int c2,int size) int i,j; int halfsize=size/2; if(size1) /递归创建左上角的赛程表 Creattable(0,0,halfsize,halfsize,halfsize); else table00=1; for(i=0;i=halfsize ,21,