五大常用算法之一：分治算法
2023-06-25 14:21:27
分治法是计算机科学中非常重要的算法。字面上的解释是“分而治之”，即将一个复杂的问题分为两个或两个以上相同或相似的子问题，然后将子问题分为更小的子问题。。。直到最后一个子问题可以简单地直接解决，原始问题的解决方案就是子问题的解决方案的结合。这一技能是许多高效算法的基础，如排序算法( 快速排序， 傅立叶变换(傅立叶快速变换)...
计算机可以解决的任何问题所需的计算时间都与其规模有关。问题规模越小，越容易直接解决，解决问题所需的计算时间越少。例如，当n=1时，n个元素的排序不需要任何计算。n=2时，只要进行一次比较，就可以排序。n=3.只需做3次比较，..而且当n比较大的时候，问题就不那么容易处理了。有时候很难直接解决一个大问题。
二、基本思想和策略
分治法的设计理念是将一个难以直接解决的大问题分为一些小问题，以便每个问题都能被打破，分而治之。
治疗策略是：对于n的问题，如果问题可以很容易地解决（如小n）直接解决，否则分解为k小子问题，这些子问题相互独立，与原始问题形式相同，递归解决这些子问题，然后解决原始问题。这种算法设计策略被称为分裂治疗。
如果原问题可以分为k个子问题，1<k≤n，而且这些子问题都可以解决，可以利用这些子问题来解决原始问题，所以这种分治法是可行的。分治法产生的子问题往往是原问题的较小模式，便于使用递归技术。在这种情况下，反复应用分治手段可以使子问题与原问题类型一致，但其规模不断缩小，最终使子问题缩小到容易直接解决。这自然导致了递归过程的产生。分治和递归就像一对孪生兄弟，经常同时应用于算法设计，从而产生了许多高效的算法。
三、分治法使用场景分治法能解决的问题一般具有以下特点：
1) 当这个问题的规模缩小到一定程度时，很容易解决
2) 这个问题可以分为几个小问题，即具有最优子结构性质的问题。
3) 利用问题分解的子问题的解决方案可以合并为问题的解决方案；
4) 问题所分解的子问题是相互独立的，即子问题之间不包含公共子问题。
第一个特征是大多数问题都能满足，因为计算问题的复杂性通常会随着问题规模的增加而增加；
第二个特征是应用分治法的前提，它也能满足大多数问题，反映递归思想的应用；、
第三条特征是关键。分治法能否使用完全取决于问题是否具有第三条特征。如果第一条和第二条特征没有第三条特征，可以考虑使用贪婪法或动态规划法。
第四条其特点涉及分治法的效率。如果每个子问题都是不独立的，分治法应该做很多不必要的工作，反复解决公共子问题。虽然分治法可以在这个时候使用，但最好使用动态规划法。
四、分治法的基本步骤每层递归分治法有三个步骤：
step1 分解：将原问题分解为几个小、独立、与原问题形式相同的子问题；
step2 解决方案：如果子问题规模小，易于解决，则直接解决，否则各子问题将逐一解决
step3 合并：将各子问题的解合并为原问题的解。
其一般算法设计模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 将P分解为小子问题 P1 ,P2 ,…,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ Pi的递归解决方案
6. T ← MERGE(y1，y2，...yk) △ 合并子问题
7. return(T)
|P|表示问题P的规模；n0是一个阈值，表示当问题P的规模不超过n0时，问题很容易直接解决，无需继续分解。ADHOC(P)用于直接解决小规模问题P的分治法中的基本子算法。因此，当P的规模不超过n0时，直接使用算法ADHOC(P)求解。算法MERGE(y1，y2，..yk)该分治法中的合并子算法用于P1的子问题 ,P2 ,..，PK对应的解y1，y2，..，yk合并为P解。
五、分析治法的复杂性
分治法将规模为n的问题分为k，规模为n／解决m的子问题。设置分解阀值n0=1，adhoc解决规模为1的问题需要一个单位时间。然后将原问题分解为k个子问题，并将k个子问题与merge合并为原问题(n)单位时间。用T(n)这意味着分治法解决问题所需的计算时间为|P|=n：
T（n）= k T(n/m)+f(n)
通过迭代法获得方程解：
递归方程及其解只给n等于m的方米(n)但是，如果你认为T，(n)当n等于m的方幂足够光滑时，T就足够光滑了(n)T的值可以估计(n)增长速度。通常假设T(n)它是单调上升的，所以当mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。
六、一些可以用分治法解决的经典问题
(1)二分搜索
(2)大整数乘法
(3)Strasen矩阵乘法
(4)棋盘覆盖
（5） 合并排序
（6） 快速排序
(7)线性时间选择
(8)最接近点对问题
(9)循环赛时间表
（10）汉诺塔
七、一些经典问题求解代码 1）二分搜索
二分搜索又称二分搜索、折半搜索，是一种高效的搜索方法。
二分搜索要求：
线性表为有序表，以向量为表的存储结构。
二分搜索的基本思想:首先确定待搜索记录的范围，然后逐渐缩小范围，直到找到或找不到记录的位置。
二分搜索步骤：
1、首先确定中间位置：
middle = (left+right)/2;
2、key值和data[middle].相比之下，key值。若相等，则搜索成功并返回该位置，否则必须确定新的搜索范围，并继续进行二分搜索，具体方法如下：
- 假如data[middle].key大于key，因为data是有序的线性表，可以看出data[middle...right].key大于key，所以如果表中有关键字等于key的节点，则必须在位置middle左侧的子表中。
- 反之， data[middle].key小于key， 因此，如果表中有等于key得到节点的关键词，则必须在位置midle右侧的子表中。下一次搜索是为了找到新的区域。
实现java代码：
1 public static void main(String[] args) { 2 int[] a = {1，2，3，4，5，6，7，8; 3 int pos =bSearch(a, 0, a.length-1, 1); 4 System.out.println(pos); 5 } 6 7 8 public static int bSearch(int[] data,int left,int right,int key){ 9 //获得中间位置100 int middle = (left+right)/2;11 //比较key值如等，返回当前位置，否则，确认新的搜索空间12 if(data[middle] == key){13 return middle;14 }else if(data[middle] >key){15 return bSearch(data, left, middle-1, key);16 }else{17 return bSearch(data, middle+1, right, key);18 }19 }
2）汉诺塔
在汉诺塔游戏中，有三个分别命名为A、B、C得到一个不同尺寸的塔座，从小到大，每个原盘中间都有一个小孔。起初，所有的圆盘都在A塔座上，其中最大的圆盘在底部，然后是第二个，以此类推.
游戏的目的是将所有的圆盘从塔座A移动到塔座B;塔座C用于防止临时圆盘，游戏规则如下：
1、一次只能移动一个圆盘
2、任何时候都不能在较小的圆盘上压一个较大的圆盘.
3、除第二条限制外，任何塔顶的圆盘都可以移动到其他塔顶.
解决汉诺塔问题的思想：
在解决汉诺塔问题时，事实上，我们并不关心圆盘1应该移动到哪个塔，而是关心底部的圆盘4。当然，我们不能直接移动圆盘4，但圆盘4最终将从塔A移动到塔B.根据游戏规则，移动圆盘4前的情况必须如下图所示
我们仍将分析如何将前三个圆盘从A移动到C，然后从A移动到B，前三个圆盘从C移动到B.
但上述步骤可以重复使用！例如，如果将三个圆盘从A移动到C，则应先将前两个圆盘从A移动到B，然后将圆盘3从A移动到C，最后将前两个圆盘从B移动到C.
最后，我们只需要处理一个圆盘从一个塔座移动到另一个塔座的问题.
实现java代码：
1 public class Moved { 2 private static int count = 1; 3 public static void main(String[] args) { 4 moved(4, “第一柱”， “第二柱”， "第三柱"); 5 } 6 7 /** 8 * 9 * @param i 圆盘数量10 * @param a 圆盘的初始位置塔座11 * @param b 将移动到塔座12的圆盘 * @param c 塔座13，辅助圆盘移动 */14 public static void moved(int i,String a,String b,String c){15 if(i == 1){16 disPaly(1, a, b);17 }else{18 ///将i-1的圆盘从A移动到C19 moved(i-1, a, c, b);20 //将圆盘i 从A移动到B21 disPaly(i, a, b);22 //将i-1的圆盘从C移动到A23 moved(i-1,c,b,a);24 }25 }26 27 public static void disPaly(int i,String a,String b){28 System.out.println("第"+count+“步骤：移动第”+i+"个塔从"+a+"到"+b);29 count++;30 }31 }
运行结果:
1 第一步:从第一根柱子到第三根柱子，移动第一个塔 2 第二步:从第一根柱子到第二根柱子，移动第二个塔 3 第三步:从第三根柱子到第二根柱子，移动第一个塔 4 第四步:从第一根柱子到第三根柱子，移动第三个塔 5 第五步:从第二根柱子到第一根柱子，移动第一个塔 6 第六步：从第二根柱子到第三根柱子，移动第二个塔 7 第七步:从第一根柱子到第三根柱子，移动第一个塔 8 第八步:从第一根柱子到第二根柱子，移动第四个塔 9 第九步:从第三根柱子到第二根柱子，移动第一个塔10 第10步:从第三根柱子到第一根柱子，移动第二个塔111 第11步：从第二根柱子到第一根柱子，移动第一个塔12步 第12步:从第三根柱子到第二根柱子，移动第三个塔13个 第13步:从第一根柱子到第三根柱子，移动第一个塔144： 第14步:从第一根柱子到第二根柱子，移动第二个塔15个柱子 第15步:从第三根柱子到第二根柱子，移动第一个塔
