本文共 10417 字，大约阅读时间需要 34 分钟。

一、分治法

1.设计思想

  将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

2.典型情况

3.求解步骤

（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同

（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。

 

（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。 

4.常见求解问题

    排序：归并排序 快速排序

    组合：棋牌覆盖 循环赛日程安排问题

    几何：最近点对

（1）归并排序

void MergeSort(int r[ ], int r1[ ], int s, int t)     {        if (s= =t) r1[s]=r[s];             else {             m=(s+t)/2;            Mergesort(r, r1, s, m);    //归并排序前半个子序列            Mergesort(r, r1, m+1, t);   //归并排序后半个子序列            Merge(r1, r, s, m, t);      //合并两个已排序的子序列         }    }

void Merge(int r[ ], int r1[ ], int s, int m, int t)    {         i=s; j=m+1; k=s;        while (i<=m && j<=t)        {               if (r[i]<=r[j]) r1[k++]=r[i++];   //取r[i]和r[j]中较小者放入r1[k]            else r1[k++]=r[j++];         }        if (i<=m) while (i<=m)            //若第一个子序列没处理完，则进行收尾处理            r1[k++]=r[i++];         else  while (j<=t)          //若第二个子序列没处理完，则进行收尾处理                    r1[k++]=r[j++];     }

 

（2）快速排序

 

void QuickSort(int r[ ], int first, int end)  {     if (first

int Partition(int r[ ], int first, int end)     {          i=first; j=end;         //初始化          while (i

（3）棋盘覆盖

void chessBoard(int tr, int tc, int dr, int dc, int size)   {      if (size == 1) return;      int t = tile++,  // L型骨牌号        s = size/2;  // 分割棋盘      // 覆盖左上角子棋盘      if (dr < tr + s && dc < tc + s)         // 特殊方格在此棋盘中         chessBoard(tr, tc, dr, dc, s);      else {// 此棋盘中无特殊方格         // 用 t 号L型骨牌覆盖右下角         board[tr + s - 1][tc + s - 1] = t;         // 覆盖其余方格      chessBoard(tr, tc, tr+s-1, tc+s-1, s);}      // 覆盖右上角子棋盘      if (dr < tr + s && dc >= tc + s)         // 特殊方格在此棋盘中         chessBoard(tr, tc+s, dr, dc, s);      else {// 此棋盘中无特殊方格         // 用 t 号L型骨牌覆盖左下

board[tr + s - 1][tc + s] = t;         // 覆盖其余方格         chessBoard(tr, tc+s, tr+s-1, tc+s, s);}        // 覆盖左下角子棋盘      if (dr >= tr + s && dc < tc + s)         // 特殊方格在此棋盘中         chessBoard(tr+s, tc, dr, dc, s);      else {// 用 t 号L型骨牌覆盖右上角         board[tr + s][tc + s - 1] = t;         // 覆盖其余方格         chessBoard(tr+s, tc, tr+s, tc+s-1, s);}      // 覆盖右下角子棋盘                if (dr >= tr + s && dc >= tc + s)         // 特殊方格在此棋盘中         chessBoard(tr+s, tc+s, dr, dc, s);      else {// 用 t 号L型骨牌覆盖左上角         board[tr + s][tc + s] = t;         // 覆盖其余方格         chessBoard(tr+s, tc+s, tr+s, tc+s, s);}   }

（4）循环赛日程安排

void GameTable(int k, int a[ ][ ])     {          // n=2k(k≥1)个选手参加比赛，        //二维数组a表示日程安排，数组下标从1开始         n=2;       //k=1，2个选手比赛日程可直接求得         //求解2个选手比赛日程，得到左上角元素         a[1][1]=1; a[1][2]=2;            a[2][1]=2; a[2][2]=1;         for (t=1; t

temp=n; n=n*2;           //填左下角元素        for (i=temp+1; i<=n; i++ )            for (j=1; j<=temp; j++)                a[i][j]=a[i-temp][j]+temp;                //左下角元素和左上角元素的对应关系       //填右上角元素       for (i=1; i<=temp; i++)                  for (j=temp+1; j<=n; j++)              a[i][j]=a[i+temp][(j+temp)% n];       //填右下角元素      for (i=temp+1; i<=n; i++)          for (j=temp+1; j<=n; j++)             a[i][j]=a[i-temp][j-temp];    }}

 

 

（5）最近点对

 

 

double cpair2(S){      n=|S|;      if (n < 2) return ;1、m=S中各点x间坐标的           中位数;      构造S1和S2；      //S1={p∈S|x(p)<=m},      S2={p∈S|x(p)>m}2、d1=cpair2(S1);      d2=cpair2(S2);3、dm=min(d1,d2);

4、设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；      P2是S2中距分割线l的距离在dm之内所有点组成的集合；      将P1和P2中点依其y坐标值排序；      并设X和Y是相应的已排好序的点列；5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；      当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；      设dl是按这种扫描方式找到的点对间的最小距离；6、d=min(dm,dl);      return d;  }

 

 

二、动态规划法

 

 

1.设计思想

    动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。

2.特征

 

（1）能够分解为相互重叠的若干子问题；

 

（2）满足最优性原理（也称最优子结构性质）：该问题的最优解中也包含着其子问题的最优解。

 

3.阶段

 

动态规划法设计算法一般分成三个阶段：

（1）分段：将原问题分解为若干个相互重叠的子问题；

（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；

（3）求解：利用递推式自底向上计算，实现动态规划过程。 

4.常见求解问题

图问题：TSP  多短图最短路径

组合问题：0/1背包  最长公共子序列

查找问题：最优二叉查找树

（1）TSP

1．for (i=1; i

（2）多段图最短路径

1．初始化：数组cost[n]初始化为最大值，数组path[n]初始化为-1；    2．for (i=n-2; i>=0; i--)        2.1 对顶点i的每一个邻接点j，根据式6.7计算cost[i];        2.2 根据式6.8计算path[i];    3．输出最短路径长度cost[0];    4. 输出最短路径经过的顶点：        4.1  i=0        4.2 循环直到path[i]=n-1            4.2.1 输出path[i];            4.2.2  i=path[i];

（3）0/1背包

int KnapSack(int n, int w[ ], int v[ ])   {     for (i=0; i<=n; i++)   //初始化第0列       V[i][0]=0;     for (j=0; j<=C; j++)   //初始化第0行       V[0][j]=0;     for (i=1; i<=n; i++)   //计算第i行，进行第i次迭代       for (j=1; j<=C; j++)          if (j
   
    0; i--)         {           if (V[i][j]>V[i-1][j]) {             x[i]=1;             j=j-w[i];          }          else x[i]=0;        }return V[n][C];    //返回背包取得的最大价值}
   

 

（4）最长公共子序列

 

 

int CommonOrder(int m, int n, int x[ ], int y[ ], int z[ ])   {      for (j=0; j<=n; j++)   //初始化第0行         L[0][j]=0;      for (i=0; j<=m; i++)   //初始化第0列         L[i][0]=0;      for (i=1; i<=m; i++)         for (j=1; j<=n; j++)            if (x[i]= =y[j]) { L[i][j]=L[i-1][j-1]+1; S[i][j]=1; }           else if (L[i][j-1]>=L[i-1][j]) { L[i][j]=L[i][j-1]; S[i][j]=2; }                  else {L[i][j]=L[i-1][j]; S[i][j]=3; }      i=m; j=n; k=L[m][n];      for (i>0 && j>0)     {         if (S[i][j]= =1) { z[k]=x[i]; k--; i--; j--; }        else if (S[i][j]= =2) j--;               else i--;     }     return L[m][n];  }

（5）最优二叉查找树

double OptimalBST(int n, double p[ ], double C[ ][ ], int R[ ][ ] )   {       for (i=1; i<=n; i++)  //按式6.17和式6.18初始化       {          C[i][i-1]=0;          C[i][i]=p[i];          R[i][i]=i;       }       C[n+1][n]=0;        for (d=1; d

 

三、贪心法

 

1.设计思路

 

    贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。

    这种局部最优选择并不总能获得整体最优解（Optimal Solution），但通常能获得近似最优解（Near-Optimal Solution）。

2.满足性质

（1）贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

（2）最优子结构性质

3.常见求解问题

图问题：TSP 图着色 最小生成树

组合问题：背包 多机调度 活动安排

（1）TSP

最近邻点：

1． P={ };        2． V=V-{u0}; u=u0;   //从顶点u0出发   3． 循环直到集合P中包含n-1条边          3.1  查找与顶点u邻接的最小代价边(u, v)并且v属于集合V；          3.2  P=P+{(u, v)};          3.3  V=V-{v};          3.4  u=v;   //从顶点v出发继续求解

最短链接：

1．P={ };         2．E'=E;     //候选集合，初始时为图中所有边    3．循环直到集合P中包含n-1条边          3.1 在E'中选取最短边(u, v);          3.2  E'=E'-{(u, v)};          3.3 如果 (顶点u和v在P中不连通 and 不产生分枝)                 则P=P+{(u, v)};

 

（2）图着色

 

1．color[1]=1;  //顶点1着颜色1    2．for (i=2; i<=n; i++)  //其他所有顶点置未着色状态              color[i]=0;    3．k=0;        4．循环直到所有顶点均着色          4.1  k++;  //取下一个颜色          4.2  for (i=2; i<=n; i++)   //用颜色k为尽量多的顶点着色                  4.2.1  若顶点i已着色，则转步骤4.2，考虑下一个顶点;                  4.2.2  若图中与顶点i邻接的顶点着色与顶点i着颜色k不冲突，                            则color[i]=k;    5．输出k;

 

（3）最小生成树 Kruskal算法

 

1. 初始化：U=V；  TE={ }；       2. 循环直到T中的连通分量个数为1            2.1 在E中寻找最短边(u，v);          2.2 如果顶点u、v位于T的两个不同连通分量，则                2.2.1 将边(u，v)并入TE；                2.2.2 将这两个连通分量合为一个；          2.3  E=E-{(u，v)}；

（4）背包

1．改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；2．将数组x[n]初始化为0；  //初始化解向量3．i=1;      4．循环直到(w[i]>C)       4.1 x[i]=1;     //将第i个物品放入背包       4.2 C=C-w[i];       4.3 i++;5. x[i]=C/w[i];

（5）活动安排

int ActiveManage(int s[ ], int f[ ], bool a[ ], int n)    {  //各活动的起始时间和结束时间存储于数组s和f中且        //按结束时间的非减序排列         a[1]=1;        j=1; count=1;        for (i=2; i<=n; i++)         {            if (s[i]>=f[j]) {              a[i]=1;              j=i;              count++;           }           else a[i]=0;        }        return count;     }

 

（6）多机调度

 

1．将数组t[n]由大到小排序，对应的作业序号存储在数组p[n]中；2．将数组d[m]初始化为0；3．for (i=1; i<=m; i++)     3.1 S[i]={p[i]};   //将m个作业分配给m个机器     3.2 d[i]=t[i];   4.  for (i=m+1; i<=n; i++)     4.1  j=数组d[m]中最小值对应的下标；  //j为最先空闲的机器序号     4.2  S[j]=S[j]+{p[i]};   //将作业i分配给最先空闲的机器j     4.3  d[j]=d[j]+t[i];      //机器j将在d[j]后空闲

 

四、回溯法

1.算法思想

    回溯法是对蛮力搜索算法的一种改进，它是一种系统地对问题的解空间进行搜索的算法，在搜索过程中，对解空间进行归约和修剪，使得其效率高于蛮力算法。

    回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件（可行解），或者是否超出目标函数（最优解）的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。

2.解空间树

 

两种典型的解空间树：

（1）子集树（Subset Trees）：当所给问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。在子集树中，|S1|=|S2|=…=|Sn|=c，即每个结点有相同数目的子树，通常情况下c=2，所以，子集树中共有2n个叶子结点，因此，遍历子集树需要Ω(2n)时间。

（2）排列树（Permutation Trees）：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，|S1|=n，|S2|=n-1，…，|Sn|=1，所以，排列树中共有n!个叶子结点，因此，遍历排列树需要Ω(n!)时间。

3.常见求解问题

图问题：图着色  哈密顿回路

组合问题：八皇后 批处理作业调度

（1）图着色

void GraphColor(int n, int c[ ][ ], int m)      //所有数组下标从1开始   {         for (i=1; i<=n; i++ )     //将数组color[n]初始化为0        color[i]=0;        k=1;       while (k>=1)       {          color[k]=color[k]+1;          while (color[k]<=m)          if Ok(k) break;          else color[k]=color[k]+1;   //搜索下一个颜色          if (color[k]<=m && k= =n) //求解完毕，输出解          {               for (i=1; i<=n; i++)                   cout<

（2）哈密顿回路

void Hamiton(int n, int x[ ], int c[ ][ ])     //所有数组下标从1开始    {       for (i=1; i<=n; i++)   //初始化顶点数组和标志数组       {          x[i]=0;          visited[i]=0;       }       k=1; visited[1]=1; x[1]=1;  //从顶点1出发      while (k>=1)      {         x[k]=x[k]+1;   //搜索下一顶点         while (x[k]<=n)         if (visited[x[k]]= =0 && c[x[k-1]][x[k]]= =1)              break;         else x[k]=x[k]+1;        if (x[k]<=n && k= =n && c[x[k]][1]= =1) {             for (k=1; k<=n; k++ )                      cout<

（3）八皇后问题

void Queue(int n)   {       for (i=1; i<=n; i++)    //初始化          x[i]=0;       k=1;       while (k>=1)       {            x[k]=x[k]+1;     //在下一列放置第k个皇后            while (x[k]<=n && !Place(k))             x[k]=x[k]+1;     //搜索下一列            if (x[k]<=n && k= =n) {   //得到一个解，输出            for (i=1; i<=n; i++)                   cout<

 

（4）批处理作业调度

 

void BatchJob(int n, int a[ ], int b[ ], int &bestTime)  {  //数组x存储具体的作业调度，下标从1开始；   //数组sum1存储机器1的作业时间，   //sum2存储机器2的作业时间，下标从0开始   for (i=1; i<=n; i++)   {      x[i]=0;      sum1[i]=0;      sum2[i]=0;   }   sum1[0]=0; sum2[0]=0;    //初始迭代使用   k=1; bestTime=∞;   while (k>=1)   {       x[k]=x[k]+1;       while (x[k]<=n)       if (Ok(k)) {           sum1[k]=sum1[k-1]+a[x[k]];          sum2[k]=max(sum1[k], sum2[k-1])+b[x[k]];          if (sum2[k]
   
    sum2[k])                bestTime=sum2[k];         x[k]=0;         //重置x[k]，回溯         k=k-1;     }  }bool Ok(int k)     //作业k与其他作业是否发生冲突（重复）{   for (i=1; i