分治算法

简介: 一、基本概念   在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

一、基本概念

   在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……

    任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。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)是该分治法中的合并子算法,用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。


五、分治法的复杂性分析

    一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:

 T(n)= k T(n/m)+f(n)

    通过迭代法求得方程的解:

    递归方程及其解只给出n等于m的方幂时T(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)Strassen矩阵乘法
(4)棋盘覆盖
(5)合并排序
(6)快速排序
(7)线性时间选择

(8)最接近点对问题
(9)循环赛日程表
(10)汉诺塔

七、依据分治法设计程序时的思维过程

    实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序。
1、一定是先找到最小问题规模时的求解方法
2、然后考虑随着问题规模增大时的求解方法
3、找到求解的递归函数式后(各种规模或因子),设计递归程序即可。

七、应用示例

  1. /*分治法——归并排序  
  2.  * 二路归并排序的分治策略是:  
  3. (1)划分:将待排序序列r1, r2, …, rn划分为两个长度相等的子序列r1, …, rn/2和rn/2+1, …, rn;  
  4. (2)求解子问题:分别对这两个子序列进行排序,得到两个有序子序列;  
  5. (3)合并:将这两个有序子序列合并成一个有序序列。  
  6.  */    
  7. public class MergeSort {    
  8.     
  9.     /**  
  10.      * @param args  
  11.      */    
  12.     public static void main(String[] args) {    
  13.         int a[] = { 2134564399377810 };// 这里对8个元素进行排序     
  14.         int low = 0, high = 7;// 初始化low和high的值,即数组的起始和终止的坐标     
  15.         // 辅助数组b,作为临时数组     
  16.         int b[] = new int[a.length];    
  17.         //输出排序前的数组     
  18.         System.out.print("排序前:");    
  19.         for (int i = 0; i <= high; i++) {    
  20.             System.out.print(a[i] + " ");    
  21.         }    
  22.         // 归并排序     
  23.         mergerSort(a, low, high, b);    
  24.         //输出排序后的数组     
  25.         System.out.print("排序后:");    
  26.         for (int i = 0; i <= high; i++) {    
  27.             System.out.print(a[i] + " ");    
  28.         }    
  29.     }    
  30.     
  31.     /**  
  32.      * 分治和归并  
  33.      *   
  34.      * @param a  
  35.      * @param low  
  36.      * @param high  
  37.      * @param b  
  38.      */    
  39.     public static void mergerSort(int a[], int low, int high, int b[]) {    
  40.         int mid = 0;    
  41.         if (low < high) {    
  42.             mid = (high + low) / 2;// 分治位置,即将数组拆分的位置     
  43.             mergerSort(a, low, mid, b);    
  44.             mergerSort(a, mid + 1, high, b);    
  45.             merger(a, low, mid, high, b);// 归并     
  46.         }    
  47.     }    
  48.     
  49.     /**  
  50.      * 合并两个有序子序列  
  51.      *   
  52.      * @param a  
  53.      * @param low  
  54.      * @param mid  
  55.      * @param high  
  56.      * @param b  
  57.      *            辅助数组  
  58.      */    
  59.     public static void merger(int[] a, int low, int mid, int high, int b[]) {    
  60.     
  61.         int i = low;    
  62.         int j = mid + 1;    
  63.         int p = 0;    
  64.         // 合并两个有序数组 子序列1 a[low..mid] 子序列2 a[mid+1..high]     
  65.         while (i <= mid && j <= high) {    
  66.             b[p++] = (a[i] <= a[j]) ? a[i++] : a[j++];    
  67.         }    
  68.         // 如果子序列1没有合并完则直接复制到复制数组中去     
  69.         while (i <= mid) {    
  70.             b[p++] = a[i++];    
  71.         }    
  72.         // 如果子序列2没有合并完则直接复制到复制数组中去     
  73.         while (j <= high) {    
  74.             b[p++] = a[j++];    
  75.         }    
  76.         // 把辅助数组的元素复制到原来的数组中去     
  77.         for (p = 0, i = low; i <= high; i++, p++) {    
  78.             a[i] = b[p];    
  79.         }    
  80.     }    
相关文章
|
2月前
|
人工智能 自然语言处理 算法
当prompt策略遇上分治算法,南加大、微软让大模型炼成“火眼金睛”
【2月更文挑战第24天】当prompt策略遇上分治算法,南加大、微软让大模型炼成“火眼金睛”
35 2
当prompt策略遇上分治算法,南加大、微软让大模型炼成“火眼金睛”
|
2月前
|
算法
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-分治算法
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-分治算法
30 0
|
2月前
|
存储 缓存 算法
【数据结构与算法】【小白也能学的数据结构与算法】递归 分治 迭代 动态规划 无从下手?一文通!!!
【数据结构与算法】【小白也能学的数据结构与算法】递归 分治 迭代 动态规划 无从下手?一文通!!!
|
4天前
|
算法 开发者 Python
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
24 8
|
6天前
|
算法 Python
算法不再难!Python分治法、贪心、动态规划实战解析,轻松应对各种算法挑战!
【7月更文挑战第8天】掌握Python算法三剑客:分治、贪心、动态规划。分治如归并排序,将大问题拆解递归解决;贪心策略在每步选最优解,如高效找零;动态规划利用子问题解,避免重复计算,解决最长公共子序列问题。实例展示,助你轻松驾驭算法!**
17 3
|
4天前
|
算法 Python
Python算法高手进阶指南:分治法、贪心算法、动态规划,掌握它们,算法难题迎刃而解!
【7月更文挑战第10天】探索Python算法的精华:分治法(如归并排序)、贪心策略(如找零钱问题)和动态规划(解复杂问题)。通过示例代码揭示它们如何优化问题解决,提升编程技能。掌握这些策略,攀登技术巅峰。
|
5天前
|
算法 程序员 Python
算法小白到大神的蜕变之路:Python分治法、贪心、动态规划,一步步带你走向算法巅峰!
【7月更文挑战第9天】探索算法之旅,以Python解锁编程高手之路。分治法如二分查找,将复杂问题拆解;贪心算法解决活动选择,每次选取局部最优;动态规划求斐波那契数列,避免重复计算,实现全局最优。每一步学习,都是编程能力的升华,助你应对复杂挑战,迈向算法大师!
12 1
|
5天前
|
存储 算法 Python
Python算法界的秘密武器:分治法巧解难题,贪心算法快速决策,动态规划优化未来!
【7月更文挑战第9天】Python中的分治、贪心和动态规划是三大关键算法。分治法将大问题分解为小问题求解,如归并排序;贪心算法每步选局部最优解,不保证全局最优,如找零钱;动态规划存储子问题解求全局最优,如斐波那契数列。选择合适算法能提升编程效率。
15 1
|
5天前
|
存储 算法 Python
震撼!Python算法设计与分析,分治法、贪心、动态规划...这些经典算法如何改变你的编程世界!
【7月更文挑战第9天】在Python的算法天地,分治、贪心、动态规划三巨头揭示了解题的智慧。分治如归并排序,将大问题拆解为小部分解决;贪心算法以局部最优求全局,如Prim的最小生成树;动态规划通过存储子问题解避免重复计算,如斐波那契数列。掌握这些,将重塑你的编程思维,点亮技术之路。
14 1
|
5天前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。