分治算法_分治算法例题 - CSDN
精华内容
参与话题
  • java数据结构算法

    千人学习 2019-12-05 11:01:40
    稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、...分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法...
  • 分治算法

    2019-10-10 19:54:37
    分治算法的核心思想   分治算法的核心思想就是四个字,分而治之,也就是将原来的问题划分成n个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解.   看起来有点像...

    分治算法的核心思想

      分治算法的核心思想就是四个字,分而治之,也就是将原来的问题划分成n个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解.
      看起来有点像递归,不过要知道分治算法是一种处理问题的思想,递归是一种编程技巧.看起来像是因为分治算法一般都比较适合用递归去实现

    分治算法递归实现步骤

    ① 分解:将原问题分解问一系列的子问题;
    ② 解决:递归地求解各个子问题,若子问题足够小,则直接求解。
    ③ 合并:将子问题的结果合并为原问题。

    分治算法的适用条件

    ① 原问题与分解的小问题之间具有相同的模式
    ② 原问题分解成子问题可以独立求解,子问题之间没有相关性,这一点是分治算法跟动态规划的明显区别。
    ③ 具有分解终止条件,即当问题足够小可以直接求解
    ④ 可以将子问题合并成原问题,而这个合并操作复杂度不能太高,否则起不到减小算法整体复杂度的效果。

    应用-如何变成求出一组数据的有序对个数或者逆序对个数?

      其实这个问题就是求一组数据的逆序对个数,比如我们有n个数据,我们期望从小到大排列,那么完全有序的数据的有序度是n(n-1)/2,逆序度是0;相反,倒序排列的数据的有序度为0,逆序度是n(n-1)/2.所以一般就是通过计算有序对或者逆序对个数来表示数据的有序度或者逆序度的。那么如何求逆序对个数呢
      最简单的办法就是拿每个数字跟后边的数字比较,看看有几个比自己小。这样把每个数字都考察一遍之后,将比自己小的数字个数加起来求和就得到逆序对个数了,这种办法效率比较低,时间复杂度O(n^2).
      更高效的办法就是使用分治算法,分治算法就是把数组A分为A1和A2凉拌,分别计算A1和A2的你虚度个数K1和K2,然后再计算A1和A2之间的逆序对个数K3,这样以来数组A的逆序度就是K1+K2+K3.那么如何计算A1和A2之间的逆序度?你能否想到归并排序呢?
      归并排序算法那中有一个关键操作就是将两个有序小数组,合并成一个有序的大数组。其实这个合并的过程中,我们就刻印计算这两个小数组的逆序对个数。每次合并我们都计算逆序对个数,把这些计算出来的逆序对个数求和,就是这个数组的逆序对个数了。
    如图:
    在这里插入图片描述

    private int num = 0; // 全局变量或者成员变量
    
    public int count(int[] a, int n) {
      num = 0;
      mergeSortCounting(a, 0, n-1);
      return num;
    }
    
    private void mergeSortCounting(int[] a, int p, int r) {
      if (p >= r) return;
      int q = (p+r)/2;
      mergeSortCounting(a, p, q);
      mergeSortCounting(a, q+1, r);
      merge(a, p, q, r);
    }
    
    private void merge(int[] a, int p, int q, int r) {
      int i = p, j = q+1, k = 0;
      int[] tmp = new int[r-p+1];
      while (i<=q && j<=r) {
        if (a[i] <= a[j]) {
          tmp[k++] = a[i++];
        } else {
          num += (q-i+1); // 统计 p-q 之间,比 a[j] 大的元素个数
          tmp[k++] = a[j++];
        }
      }
      while (i <= q) { // 处理剩下的
        tmp[k++] = a[i++];
      }
      while (j <= r) { // 处理剩下的
        tmp[k++] = a[j++];
      }
      for (i = 0; i <= r-p; ++i) { // 从 tmp 拷贝回 a
        a[p+i] = tmp[i];
      }
    }
    
    
    展开全文
  • 分治算法详解(超详细)

    千次阅读 2019-09-20 23:06:48
    分治算法详解 ...

    分治算法详解

                                                          

     

                                                      分治算法详解

     

    一、基本概念

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

        任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于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:对于大数问题的思考(1)
     
     
    下面采用分治法的逻辑看看是否可行,在这里我们举例 3的2000次方,由于整形最多20亿,毋庸置疑这里已经超过了界限!为了方便说明是否可以分治 以及如何分治,请看这样一个算式:
     
      123 345 678 * 3 = 370 037 034       在这里我们可以这样写:
     
    123 * 3 = 369      345 * 3 = 1035      678 * 3 = 2034          组合在一起是    369 1035 2034。
     
    看到这个结果,与原结果相比较,你发现了什么?其实早就在古代我们的老祖宗就发明了算盘的这个计算工具,回想一下他的计算方式,逢10进1,也就是我们通常所说的10进制表示法!
    在这里,我们可以想得到 1000进制吧,也就是逢1000往上位进1,那么每个位上最大的也只能是999,而没有1000了。 利用这个思想,我们来看看上面的算式!
     
                                                  369                                  1035                               2034
                                                  369+1                                035+2                             034
                                           (加1,得370)                       (进1,保留037)               (进2,保留034)
                                      
                                          那么最后的结果也就是 370 037 034 发现结果刚好一样,这就是我们所谓的1000进表示法
     
     
     值得说明一下:为何1000进制表示出来的数和10进制表示出来的数是一样的,其实不仅如此,100进制  1000进制 乃至10000进制,表示的最后结果都是一样的,不知道你发现了没?
     举个例子:10进制的199,用100进制表示也是1 99,10进制的1099 用1000进制表示也是 1 099(注意这个0不能略去)以此类推!
     
     
    好了,回到正题,上面那个算式通过拆分为3个数的思想,这就体现了分治法的思想,
       首先他满足第一条件:分解到一定小规模的时候可以解决
                         第二条件:每个小规模都具有最佳子结构(在变量范围内,可以用来表示)
                         第三条件:每个小问题可以通过合并在一起形成大问题的解
                         第四条件:每个小问题相互独立
     
     这几点他都满足了,当然可以利用分治思想了!接下来看我们的题目 3的2000次方,在这里我们采用10000进制数组表示法!!该函数源码如下:
     
    1. void RandomBigNumFun(int low,int high) //传递参数为底数和指数
    2. {
    3. unsigned int temp[1024] = {0}; //初始化一个数组,用来存放10000进制的数据
    4. temp [0] = low; //初始化第一个元素为需要的值!
    5. int flag = -1; //标记变量,用来指示是否需要往上一位进位,同事保存进多少
    6. unsigned int m_count = 1; //技术变量,计算数组中被占用了多少个元素
    7. int _index,index; //两个循环变量
    8. for(_index = 0;_index <high-1; ++_index) //循环high-1次 因为本身temp[0]= low,
    9. {
    10. for(index = 0; index < m_count ; ++index) //循环m_count次,其实原本可以把整个数组循环完
    11. { //只不过耗时了,因为实际有值的地方只有m_count个
    12. temp[ index ] *= low;
    13. if(flag != -1) //检测下一位是否溢出,需要向自己进位
    14. {
    15. temp[index] += flag;
    16. flag = -1; //进位之后别忘记把标记在设置为-1
    17. }
    18. if(temp[index] > 9999) //判断是否需要向上一位进位
    19. {
    20. flag = temp[index]/10000 ;
    21. temp[index] %= 10000;
    22. }
    23. }
    24. if(flag != -1)
    25. {
    26. temp[index] += flag;
    27. ++m_count;
    28. flag = -1;
    29. }
    30. if(m_count > 1023)
    31. {
    32. printf("数据过大而数组过小,请重置存放数组的大小");
    33. exit(0);
    34. }
    35. }
    36. for(index = m_count-1;index >=0;--index) //这里值得说明,如果该位上是1,则要输出0001,因为是一万进制
    37. {
    38. if(temp[index] < 10)
    39. cout<<"000"<<temp[index];
    40. else if(temp[index] < 100)
    41. cout<<"00"<<temp[index];
    42. else if(temp[index] < 1000)
    43. cout<<"0"<<temp[index];
    44. else
    45. cout<<temp[index];
    46. }
    47. }

    其实上述函数需要传递参数进去,这里就传3和2000进去,运行结果如下(大得难以想象):
     
    如有不懂的地方,欢迎在我的博客留言!!
     
     
    对于大数问题的思考(2):
     
    上述所讲是大数的乘方形式出现,接下来演示大数相乘的计算方法,例如:27392361983108271361039746313 乘以 37261038163103818366341087632113
    呵呵,当然在这里我不会写这么大一个数组,我只会举一个简单的例子  如 234 * 456 = ????
     
    有人可能会问:博主,这样的直接计算就可以算出来,还需要分治吗? 在这里我主要讲一种通用的算法思想,那么无论遇见多大的数字,都可以这样来写!
     
    算法前的分析:在这里我们若把456拆分为4,5,6,然后分别去乘以234,结果是什么样勒?答案如下:
     
                                            234
                                    x      456
                              ____________________
                                          1404
                                        1170
                                        936 
                                ------------------------------------
                                          106704
     
    这样的结构大家都清楚,可是我们需要怎么用程序来保留这个结果勒,不妨设一个二维数组来保存结果,数组的第一行保留1404,第二行保留1170,第三行保留936,
    由于不能直接存储,我们需要对存放的位置做一下计算:数组该有多少行,该有多少列?
    在这里我们需要知道,两个三位数的乘积,结果最多为6位数,一个2位一个6位相乘,结果最多为2+6=8位,所以这里数组该有6列,而对于行数,则由被乘数决定,所以这里为3行!!、
     temp [3] [6]  =  {
                                 0  0  1  4  0  4
                                 0  1  1  7  0  0
                                 0  9  3  6  0  0
                             }
    每列依次往下加 1 0  6 7  0  4;所得刚好为我们要的答案,好了,废话不多说,这里直接看代码!!
    1. #include <iostream>
    2. using namespace std;
    3. inline int Translate(char str)
    4. {
    5. return (str - 48);
    6. }
    7. int _tmain(int argc, _TCHAR* argv[])
    8. {
    9. char NumStr1 [3] = {'2','3','4'};
    10. char NumStr2 [3] = {'4','5','6'};
    11. int temp[3][6] = {0};
    12. signed int flag = -1;
    13. int Temp_x = 0;
    14. int Temp_y ;
    15. int _index,index;
    16. for(_index = 2;_index >= 0 ;--_index) //这里的两重循环是分别赋值到二维数组里面
    17. {
    18. Temp_y = 5 - Temp_x;
    19. for(index = 2;index >= 0;--index,--Temp_y)
    20. {
    21. temp[Temp_x][Temp_y] = Translate(NumStr2[_index]) * Translate(NumStr1[index]);
    22. if(flag != -1)
    23. {
    24. temp[Temp_x][Temp_y] += flag;
    25. flag = -1;
    26. }
    27. if(temp[Temp_x][Temp_y] >= 10)
    28. {
    29. flag = temp[Temp_x][Temp_y]/10;
    30. temp[Temp_x][Temp_y] %= 10;
    31. }
    32. }
    33. if(flag != -1)
    34. {
    35. temp[Temp_x][Temp_y] += flag;
    36. flag = -1;
    37. }
    38. ++ Temp_x;
    39. }
    40. int temp_sum[6]={0};
    41. flag = -1;
    42. for(int j=5;j >= 0;-- j) //接下来这个循环是加每一列的数组到最后的结果数组里面
    43. {
    44. for(int i=2;i>=0;--i)
    45. temp_sum[j] += temp[i][j];
    46. if(flag != -1)
    47. {
    48. temp_sum[j] += flag;
    49. flag = -1;
    50. }
    51. if( temp_sum[j] >= 10)
    52. {
    53. flag = temp_sum[j] /10;
    54. temp_sum[j] %= 10;
    55. }
    56. }
    57. flag = -1;
    58. for(int i = 0;i !=6;++ i) //这里是输出结果
    59. cout<<temp_sum[i];
    60. cout<<endl;
    61. system("pause");
    62. return 0;
    63. }

     
    运行结果如下所示:

     
    所得结果跟我们预想的一样 ,但是这个程序有个小bug,因为两个三位数相乘,不一定是6位数,也许是5位数,所以输出的时候记得判断下第一个是否为0!
    看到这里,读者可以自己改编以上程序为一个函数,求任意两个数字的乘积,只是那样的话需要动态创建数组了!
     
    2:递归与分治的结合(汉诺塔问题)
    关于递归,他也可看做是属于分治思想的一种体现,递归问题到处可见,可他始终是一个重难点,在这里我主要说一下递归中的汉诺塔这个经典的问题!
     
    至于什么是汉诺塔,如果有不知道的可以百度,在这里我不累述,直接在程序中说明:
     
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. static int count = -1;
    4. void move(char x,char y); // 对move函数的声明
    5. void hanoi(int n,char one,char two,char three) ;// 对hanoi函数的声明\
    6. int main()
    7. {
    8. int m;
    9. printf("请输入一共有多少个板子需要移动:");
    10. scanf("%d",&m);
    11. printf("以下是%d个板子的移动方案:\n",m);
    12. hanoi(m,'A','B','C');
    13. system("pause");
    14. return 0;
    15. }
    16. void hanoi(int n,char one,char two,char three) // 定义hanoi函数
    17. // 将n个盘从one座借助two座,移到three座
    18. {
    19. if(n==1)
    20. move(one,three);
    21. else
    22. {
    23. hanoi(n-1,one,three,two); //首先把n-1个从one移动到two
    24. move(one,three); //然后把最后一个n从one移动到three
    25. hanoi(n-1,two,one,three); //最后再把n-1个从two移动到three
    26. }
    27. }
    28. void move(char x,char y) // 定义move函数
    29. {
    30. count++;
    31. if( !(count%5) )
    32. printf("\n");
    33. printf("%c移动至%c ",x,y);
    34. }

     
    如果输入5个板子,则移动的方案为:
     
     
     
     
     
     
    结果所示便为移动过程,至于内部是怎么实现的,读者可自己下来画出示意图,便一目了然!!
     
    2:二分搜索法(二分查找) ,利用分治思想缩小范围!
     
    二分法的思想说来比较简单,就是利用上下限不停的缩小查找的界限,当缩小到一定范围内的时候,就可以解决,这个算法也十分常见,在这里我不在累述了
     
     
     
    1. #include <iostream>
    2. using namespace std;
    3. int binary_sreach(int *array,int len,int elem);
    4. int main(int argc, char* argv[])
    5. {
    6. int a[7] = {1,2,3,6,8,9,99};
    7. cout<<binary_sreach(a,7,6);
    8. system("pause");
    9. return 0;
    10. }
    11. int binary_sreach(int *array,int len,int elem)
    12. {
    13. int low = 0;
    14. int high = len - 1;
    15. int middle;
    16. while (low <= high)
    17. {
    18. middle = (low + high)/2;
    19. if(array[middle] == elem)
    20. return middle;
    21. else if(array[middle] > elem)
    22. high = middle;
    23. else
    24. low = middle;
    25. }
    26. return -1;
    27. }
    运行结果也可想而知是3,二分法其实也就这么简单,这里也明显利用了分治的思想!!
     
     分治法是一个非常重要的算法思想,在各种程序设计大赛上经常采用分治思想解答,这里只是列举了一些经典问题的解法,具体问题还需要具体分析,以后我会持续更新,每次遇见就记录下来给大家分享!
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
    展开全文
  • 五大常用算法之一:分治算法

    万次阅读 多人点赞 2019-06-18 20:58:55
    分治算法 一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单...

    分治算法
    一、基本概念

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

    任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于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、找到求解的递归函数式后(各种规模或因子),设计递归程序即可。

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

    一、基本概念

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

        任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。


    二、基本思想及策略

        分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

        分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

        如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。


    三、分治法适用的情况

    分治法所能解决的问题一般具有以下几个特征:

    1) 该问题的规模缩小到一定的程度就可以容易地解决

    2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。

    3) 利用该问题分解出的子问题的解可以合并为该问题的解;

    4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

    第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;

    第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;、

    第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。

    第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好


    四、可使用分治法求解的一些经典问题
     
    (1)二分搜索
    (2)大整数乘法
    (3)Strassen矩阵乘法
    (4)棋盘覆盖
    (5)合并排序
    (6)快速排序
    (7)线性时间选择
    (8)最接近点对问题
    (9)循环赛日程表
    (10)汉诺塔


    五、分治法的基本步骤

    分治法在每一层递归上都有三个步骤:

    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、找到求解的递归函数式后(各种规模或因子),设计递归程序即可。


    八、算法举例

    回文

    这里的回文是指资格字符串,它从头到尾读与从尾到头读的内容是一致的,比如说doggod,无论从左到右耗时从右到左都是一样的。

    def isPal(s):
        if len(s) <= 1:
            return True
        else:
            return s[0]==s[-1] and isPal(s[1:-1])
    
    s = 'doggod'
    result = isPal(s)
    print result
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    可以看出算法就是利用递归不断的处理更小的子问题。

    二分查找

    二分查找也是典型的分治算法的有应用。二分查找需要一个默认的前提,那就是查找的数列是有序的。 
    二分查找的思路比较简单: 
    1) 选择一个标志i将集合分为二个子集合 
    2) 判断标志L(i)是否能与要查找的值des相等,相等则直接返回 
    3) 否则判断L(i)与des的大小 
    4) 基于判断的结果决定下步是向左查找还是向右查找 
    5) 递归记性上面的步骤

    def binarySearch(L,e,low,high):
        if high == low:
            return L[low] == e 
        mid = (low+high)//2
        if L[mid]==e:
            return True
        elif L[mid]>e:
            if low == mid:
                return False
            else:
                return binarySearch(L,e,low, mid-1)
        else:
            return binarySearch(L,e,mid+1,high)
    
    def search(L,e):
        result = binarySearch(L,e,0,len(L)-1)
        print result   
    
    L = range(10);
    e = 7
    
    search(L,e)    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23


    九、总结

        分治算法的一个核心在于子问题的规模大小是否接近,如果接近则算法效率较高。

        分治算法和动态规划都是解决子问题,然后对解进行合并;但是分治算法是寻找远小于原问题的子问题(因为对于计算机来说计算小数据的问题还是很快的),同时分治算法的效率并不一定好,而动态规划的效率取决于子问题的个数的多少,子问题的个数远小于子问题的总数的情况下(也就是重复子问题多),算法才会很高效。


    展开全文
  • 分治算法总结

    千次阅读 2020-03-31 10:58:56
    在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解...
  • 分治法 ( Divide And Conquer ) 详解

    万次阅读 多人点赞 2019-03-29 15:57:01
    在这篇 blog 中,我首先会介绍一下分治法的范式,接着给出它的递归式通式,最后我会介绍三种方法(代入法,递归树,和主方法)求解递归式
  • 五大常用算法(一) - 分治算法

    千次阅读 2018-10-16 10:39:38
    分治算法 基本思想 分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)...
  • 比如有一个List L = [(0,1), (1, 0), (0, 1), (1, 1), (1, 2), (3, 1), (3, 1), (2, 2), (2, 3), (3, 2), (2, 3), (4, 3), (3, 4), (4, 4), (4, 5), ...另外用**分治法**的话,给出一组数字,如何寻找他的一对数组呢?
  • 以下哪种排序算法用到了分治思想

    千次阅读 2017-03-25 15:58:49
    答案:B知识点分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法...
  • 分治算法例子集锦

    万次阅读 2015-03-07 13:25:33
    分治算法例子集锦
  • 分治算法会用到递归,递归函数的复杂度都普遍高于非递归函数,请问分治算法使用递归的意义是什么,对分治的复杂度有什么影响呢
  • 分治算法(divide and conquer)

    万次阅读 2013-12-09 12:07:44
    正如名字divide and conquer所言,分治算法分为两步,一步是divide,一步是conquer。 Divide:Smaller Problems are solved recursively except base cases. Conquer:The solution to the original problem is then...
  • 分治算法,字面上的解释是“分而治之”,分治算法主要是三点:1.将一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题—-“分”2.将最后子问题可以简单的直接求解—-“治”3.将所有子...
  • 算法8.分治算法计算a^n

    万次阅读 2017-01-07 13:31:25
    设a为一给定实数,设计一个分治算法,用于计算an (n为自然数),并分析其计算时间复杂度,要求该算法的计算效率高于蛮力算法。 1. 算法设计思路 1.当n为偶数的时候,an可以分治为(a^2/n)*(a^2/n) 2.当n为奇数的时候...
  • 算法是什么,即是按照一定的步骤,一步步去解决某个问题,解决问题的方法步骤就称为算法,例如数学中我们学过的做一个运算,解一个方程,等等,都需要有一个清晰的思路,一步步地去完成。可以说算法就在身边。算法和...
  • 二分查找(分治算法

    千次阅读 2014-04-09 15:50:12
    把一个大问题分解为2个相对较小的问题,分别解决2
  • 求解最大值与最小值-分治算法

    万次阅读 2018-05-25 22:00:47
    概述无论是最好、最坏或者平均情况,该MaxMin分治算法所用的比较次数都是3n/2-2。而实际中,任何一种以元素比较为基础的找最大值最小值元素的算法,其元素比较次数的下界为3n/2-2。因此,从此种情况上分析,该算法是...
  • 计算x^n,用普通的算法就是x乘n次的话,时间复杂度就是O(n)   利用分治法 x ^ n = x^(n/2) *x(n/2) ( n是偶数)  = x^((n-1)/2)*x^((n-1)/2)*x (x是奇数)   这样的话 T(n) = O(1) if x = 1  = T(n/2)+O...
  • 分治算法主定理

    千次阅读 2016-07-08 13:16:58
    分治算法主定理分治算法通常遵守一种通用模式:即:在解决规模为nn的问题时,总是先递归地求解aa个规模为nb\frac{n}{b}的子问题,然后在O(nd)O(n^d)时间内将子问题的解合并起来,其中a,b,d>0a,b,d > 0是一些特定的...
1 2 3 4 5 ... 20
收藏数 66,561
精华内容 26,624
关键字:

分治算法