Doris232 发表于 2021-7-10 15:32

经典优化算法之分治法(Divide-and-Conquer Algorithm)

欲下载本文相关代码,请关注微信公众号“数据魔术师”,在后台回复关键字“分治法”。
1.目录

1.1分治法基本介绍
1.2分治法通俗解释
1.3分治法严谨定义
1.4分治法的流程
1.5分治法的经典例子
1.6总结
2.分治法基本介绍

分治分治,即分而治之。分治,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……   
直接说就是将一个难以直接解决的大问题,分割成一些规模比较小的相同的小问题,以便各个击破,分而治之。
3.分治法通俗解释

3.1栗子

有这样一个非常经典的问题 .
问题:有100枚硬币,其中1枚重量与众不同,是假币,略轻一些。如果用天平秤,请问至少称几次一定能找到这枚假币。
假如我们用传统的逐枚比较法的话,显然至少需要比较50次。 流程如下:


而假如我们采用分治法的话,称量流程如下:
1.将100硬币分成3份,33,33,34。
2.称量1、2份,若天平平衡,则假币必在另外34枚中。若不平衡,假币在轻的那33枚里。
3.将34枚分为11/11/12枚(或将33枚分成11*3)。
4.称量两组11枚的硬币,若平衡,假币在12枚里(或另外的11枚)若不平衡,假币在轻的11里。
5.将11(或12)枚分成3/4/4(或4/4/4),称量4/4,方法同上。
6.将剩下的3(或4)分为1/1/1(或1/1),称量1/1,若平衡,则剩下的一枚是假币,若不平衡,轻的是假币。 若还剩4枚,出现1/1平衡,剩下2枚则称量,显然轻的是假币。
这种方法只需要5次就能解决这个问题。
3.2栗子分析

我们来看我们刚刚使用的“分治法”。
1.观察可以看到1-2,3-4,5-6步除了硬币的枚数改变了,其他的步骤完全一样。
2.观察发现这是一个子问题的分解过程,100—33-11-3,将一个大问题分解为了容易解决的小问题。
3.可以发现小问题是相互独立的。每一个33枚硬币和其他的并不相互影响。
方便起见,我们用较简单的二分法流程图来具体看一下:
可以发现这和程序设计中的递归很类似,自顶而下的解决问题;
4.分治法严谨定义

4.1分治算法主定理

分治算法通常遵守一种通用模式:即:在解决规模为n的问题时,总是先递归地求解a个规模为n/b的子问题,然后在
时间内将子问题的解合并起来,其中a,b,d>0a,b,d 是一些特定的整数。分治算法的运行时间可以通过公式:
来计算。
4.1.1分治算法的时间复杂度

一般的,对于a,b,d>0且有
成立,
则:




4.1.2 举例

我们用比较熟悉的归并排序来分析:
首先有
对于我们熟悉的归并排序符合主定理的第二种情况,有

5.分治算法的流程





5.1流程Divide-and-Conquer!

划分问题:整个问题划分成多个无关联的子问题。   
递归求解:递归调用求解各个子问题。      
合并问题:合并子问题的解,形成原始问题的解。 我们用伪代码来具体分析~
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的解。5.2使用条件

1.该问题的规模缩小到一定的程度就可以容易地解决
2.该问题可以分解为若干个规模较小的相同问题。
3.利用该问题分解出的子问题的解可以合并为该问题的解;
4.该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。(非必需)
5.2.1对使用条件的分析

第1条随着问题规模的减少,问题自然会容易解决。条件2,3是分治的前提。即Divide-and-Conquer的必要条件。 第4条,对于存在公共子问题的问题,使用分治算法会存在重复计算的问题,使用动态规划较为合适。
5.2.1.1浅谈分治与动态规划

分治和动态规划有共通也有不同,我i们来看如下两个定义。
最优子结构:如果问题的一个最优解中包含了子问题的最优解,则该问题具有最优子机构。

重叠子问题:用来求解原问题的递归算法反复地解同样的子问题,而不是总是在产生新的子问题。对两个子问题来说,如果它们确实是相同的子问题,只是作为不同问题的子问题出现的话,则它们是重叠的。当子问题相互独立时,能且只能使用分治。存在重叠子问题时,动态规划是更好的算法。 In a word, 分治法 —— 各子问题独立;动态规划 —— 各子问题重叠。
算法导论: 动态规划要求其子问题既要独立又要重叠,这看上去似乎有些奇怪。虽然这两点要求听起来可能矛盾的,但它们描述了两种不同的概念,而不是同一个问题的两个方面。如果同一个问题的两个子问题不共享资源,则它们就是独立的。对两个子问题俩说,如果它们确实是相同的子问题,只是作为不同问题的子问题出现的话,是重叠的,则它们是重叠的。
6.分治算法的经典例子

6.1 归并排序





6.1.1问题描述:给定n个乱序数字,要求从小到大排序后输出。

6.1.2思路分析:

逐条对应:
1.比较两个数字大小很容易。
2.将n个数字排序和将n/2个数字排序问题相同
3.不存在重叠子问题。
因而用分治法是很有效果的。 思路如下:      
1.分割:将这个序列分割成一个个已经排好序的子序列(即子序列里只有一个数)
2.比较。
3.归并:将一个个有序的子序列合并成排好序的序列。
6.1.3coding time

我们用递归的方法来解决。
//首先来看函数主体,实现了分割的部分
void mergesort(int a[],int n,int left,int right)
{
    if(left+1<right)
    {
      int mid=(left+right)/2;
      mergesort(a,n,left,mid);
      mergesort(a,n,mid,right);
      merge(a,n,left,mid,right);
    }
}
//下面来写自己的merge函数!
//L,R是辅助数组!
void merge(int a[],int n,int left,int mid,int right)
{
    int n1=mid-left,n2=right-mid;
    for(int i=0;i<n1;i++)
      L=a;//储存左数列
    for(int i=0;i<n2;i++)
      R=a;//储存右数列
    L=R=INF;
    int i=0,j=0;
    for(int k=left;k<right;k++)//合并
    {
      if(L<=R)
            a=L;
      else
            a=R;
    }
}代码如下
#include<bits/stdc++>
using namespace std;
const int maxn=500000,INF=0x3f3f3f3f;
int L,R;
void merge(int a[],int n,int left,int mid,int right)
{
    int n1=mid-left,n2=right-mid;
    for(int i=0;i<n1;i++)
      L=a;
    for(int i=0;i<n2;i++)
      R=a;
    L=R=INF;
    int i=0,j=0;
    for(int k=left;k<right;k++)
    {
      if(L<=R)
            a=L;
      else
            a=R;
    }
}
void mergesort(int a[],int n,int left,int right)
{
    if(left+1<right)
    {
      int mid=(left+right)/2;
      mergesort(a,n,left,mid);
      mergesort(a,n,mid,right);
      merge(a,n,left,mid,right);
    }
}
int main()
{
    int a,n;
    cin>>n;
    for(int i=0;i<n;i++)
      cin>>a;
    mergesort(a,n,0,n);
    for(int i=0;i<n;i++)
    {
      if(i)
            cout<<" ";
      cout<<a;
    }
    cout<<endl;
    return 0;
}6.1.4优缺点分析

优点:用分治算法主定理可得时间复杂度为O(nlogn),相同元素的顺序不会颠倒,是稳定排序。
缺点:需要辅助数组,所需空间复杂度为O(n)。
6.2求最大连续和

6.2.1问题描述:

给出一个长度为n的序列A1,A2,A3·····An,求最大连续和。如序列(6,-1 , 5, 4,-7), 该序列中的最大和是6 +( - 1)+ 5 + 4 = 14。
6.2.2思路分析:

基本思路是使用枚举法,三重嵌套循环,时间复杂度为n的三次方
我们来用分治法解决这个问题
1.划分问题:将序列分成元素个数尽可能相等的两半。
2.递归求解:分别求出位于左半和右半的最佳序列。
3.合并问题:求出起点位于左半,终点位于右半的最大连续和序列,和子问题最优解比较。
6.2.3coding time!

int maxsum(int l,int r)
{
    if(l==r)return a;
    int m=(l+r)/2;
    int Max=max(maxsum(l,m),maxsum(m+1,r));//(分解)情况1:完全在左区间,或者完全在右区间

    //(合并)情况2:横跨左右两个区间
    int suml=a,t=0;
    for(int i=m;i>=l;i--)
      suml=max(suml,t+=a);
    int sumr=a;t=0;
    for(int i=m+1;i<=r;i++)
      sumr=max(sumr,t+=a);

    return max(Max,suml+sumr);//取两种情况中最大的。


}6.3汉诺塔问题

6.3.1问题描述:

如下图所示,从左到右有A、B、C三根柱子,其中A柱子上面有从小叠到大的n个圆盘,现要求将A柱子上的圆盘移到C柱子上去,期间只有一个原则:一次只能移到一个盘子且大盘子不能在小盘子上面,求移动的步骤和移动的次数。


6.3.2思路分析:

考虑最简单情况n=2,三根柱子分别为A、B、C,此时,在A上有2片金片(假设从小到大依次为1,2)。那么我们的解决步骤可以归结为如下:
1,先把A上1号金片移至B。
2,再把A上2号金片移至C。
3,再把B上1号金片移至C。 考虑n增大的情况: 1,先把A上从1到n-1号金片移至B。
2,再把A上64号金片移至C。
3,再把B上从1到n-1号金片移至C。
可以看到递归的影子,要解决n个,先解决n-1个,可以分治为n=2的最简单情况并加以解决。
6.3.3coding time!

#include <iostream>
void move(int,char,char,char);
int main()
{   
   int m;
   cin>>m;
   move(m,'A','B','C');
}
/*XYZ分别代表三根柱子*/

void move(int m,char x,char y,char z)
{   
    if(m==1)   
    {      
      cout<<x<<"->"<<z<<endl"; //如果只有一个金片了,那么我们直接将其从X移至Z即可。      
      return;   
    }   
    move(m-1,x,z,y); //先将m-1个金片从X移至Y。   
    cout<<x<<"->"<<z<<endl);//每次递归时,我们总是将1号金片移至Z。   
    move(m-1,y,x,z); //再将整体代换的m-1个金片从Y移至Z
}7.总结

分治法实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序。 一定是先找到最小问题规模时的求解方法,然后考虑随着问题规模增大时的求解方法找到求解的递归函数式后(各种规模或因子),设计递归程序即可。
<hr/>文案 && 代码:李博骁
审核:邓发珩 && 贺兴
指导老师: 秦时明岳(华中科技大学管理学院)
如对文中内容有疑问,欢迎交流。PS:部分资料来自网络。
如有需求,可以联系:
秦虎老师(professor.qin@qq.com)
李博骁    (华中科技大学管理学院本科一年级 : 1642940680@qq.com)

邓发珩 (华中科技大学管理学院本科二年级:2638512393@qq.com、个人公众号:程序猿声)
贺兴      (华中科技大学管理学院本科四年级:hexing15@gmail.com)

JoshWindsor 发表于 2021-7-10 15:41

分而治之求最大子序列和如何返回最大子序列的首尾位置?

APSchmidt 发表于 2021-7-10 15:41

找假币的案例,那个算法更像是二分查找法,排除法

闲鱼技术01 发表于 2021-7-10 15:51

“再将整体代换的m-1个金片从Y移至Z” 难道就我一个人想问 不是一次只能移动一个盘子???

acecase 发表于 2021-7-10 15:52

一次性移动一个盘子的条件在约束解决问题过程,但是不影响分割问题。

RedZero9 发表于 2021-7-10 15:55

建议添加,快速幂、地毯填补、循环比赛日程表、        求逆序对数目 等拓展题目以供读者进一步训练与思考。
页: [1]
查看完整版本: 经典优化算法之分治法(Divide-and-Conquer Algorithm)