分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题,1<k≤n ,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
分治法所能解决的问题一般具有以下几个特征:
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解;
4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。
分治法的基本步骤
分治法在每一层递归上都有三个步骤:
分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题合并:将各个子问题的解合并为原问题的解。
分享到:
相关推荐
分治法求最近点对问题,要求:1. 对于平面上给定的N个点,给出所有点对的最短距离,即,输入是平面上的N个点,输出是N点中具有最短距离的两点。 2. 要求随机生成N个点的平面坐标,应用蛮力法编程计算出所有点对的...
关于分治法的算法结课论文,讲述了分治法与递归的联系与区别。分治法是解题思路,而递归是实现的方法,可用递归,也可用非递归
是算法设计实验的题目,老师要求的是用分治法,而不是蛮力法求解!最终我将一个数组平分成两个小数组,分别求出各数组的两个最大及两个最小值,然后再分别组合4个最大值和四个最小值,最后再比较出大小,得出4个最大...
数据结构的分治法求解最大值,数据结构的分治法求解最大值
3. 要求随机生成N个点的平面坐标,应用分治法编程计算出所有点对的最短距离。 4. 分别对N=100,1000,10000,100000,统计算法运行时间,比较理论效率与实测效率的差异,同时对蛮力法和分治法的算法效率进行分析和比较...
分治法求01背包问题c语言 已调通
分治法-中位数 第一行: n,为x和y数组的元素个数 第二行: x数组的n个数,用空格分隔 第三行: y数组的n个数,用空格分隔
分治法求最大值和最小值 实验报告
资源位分治法求最近点对,包含几种算法,以及图形界面,是一套完整的工程。全部为java实现。
使用java编写 用分治法实现对于平面上最近点对的查找 使用Swing作为界面
分治法求两个大整数相乘C++实现。
算法分析与设计中的分治法,列出了16人的赛程及过程,如有需要可以改动
1、 深刻理解并掌握分治法的设计思想 2、 提高应用分治法设计算法的技能 1、 理解算法思想和问题要求 2、 编程实现题目要求 3、 上机输入和调试自己所编的程
分治法实现矩阵相乘
算法设计与分析课内实验——分治法求众数。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境)
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解求得原问题的解。与分治法不同的是,适合于动态规划法求解的问题,经分解求得的子问题往往不是互相独立...
求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。
利用分治法,解决对N个字中求第K大的数字的问题,效率比起逐个扫描有素提高
用分治法求最大子段和,适合刚接触数据结构的初学者
给定一个点数组,比较求解最近点对的一般算法和分治法的效率。测试过后相信你会对分治法有另一看法的。