五大常用算法之一：分治算法

　　分治法是计算机科学中非常重要的算法。字面上的解释是“分而治之”，即将一个复杂的问题分为两个或两个以上相同或相似的子问题，然后将子问题分为更小的子问题。。。直到最后一个子问题可以简单地直接解决，原始问题的解决方案就是子问题的解决方案的结合。这一技能是许多高效算法的基础，如排序算法( 快速排序， 傅立叶变换(傅立叶快速变换)...

　　计算机可以解决的任何问题所需的计算时间都与其规模有关。问题规模越小，越容易直接解决，解决问题所需的计算时间越少。例如，当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、首先确定中间位置：

　　　　middle = (left+right)/2;

　　　　2、key值和data[middle].相比之下，key值。若相等，则搜索成功并返回该位置，否则必须确定新的搜索范围，并继续进行二分搜索，具体方法如下：

1. 　　假如data[middle].key大于key，因为data是有序的线性表，可以看出data[middle...right].key大于key，所以如果表中有关键字等于key的节点，则必须在位置middle左侧的子表中。
2. 反之，　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     }

　　　　在汉诺塔游戏中，有三个分别命名为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步:从第三根柱子到第二根柱子，移动第一个塔