现在的位置: 首页 > 综合 > 正文

【回溯法】 0027算法笔记——【回溯法】回溯法与装载问题0028算法笔记——【回溯法】批作业调度问题和符号三角形问题0030算法笔记——【回溯法】最大团问题和图的m着色问题0031算法笔记——【回溯法】旅行员售货问题和圆排列问题0032算法笔记——【回溯法】电路板排列问题和连续邮资问题

2017年11月05日 ⁄ 综合 ⁄ 共 35380字 ⁄ 字号 小 中 大 ⁄ 评论关闭

0027算法笔记——【回溯法】回溯法与装载问题

分类： 算法2013-04-05
21:10 542人阅读 评论(0) 收藏 举报
回溯法装载问题算法笔记排列数子集树

     1、回溯法

     (1)描述:回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

     (2)原理: 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

      回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。

     (3)问题的解空间

     问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。

     显约束：对分量xi的取值限定。

     隐约束：为满足问题的解而对不同分量之间施加的约束。

     解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。

     注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。

      例1：n=3的0——1 背包问题的回溯法搜索过程。W=[16,15,15]  p=[45,25,25]  C=30 

     

     例2：旅行售货员问题。某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。


     (4)生成问题状态的基本方法

     扩展结点:一个正在产生儿子的结点称为扩展结点。
     活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点。
     死结点:一个所有儿子已经产生的结点称做死结点。
     深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）。

     宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点。
     回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。

     (5)回溯法的基本思想

     基本思想：

     用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。

     解题步骤：

     1)针对所给问题，定义问题的解空间；
     2)确定易于搜索的解空间结构；
     3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

    常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。

     递归回溯：

     回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。

[cpp] view
plaincopy

  1. void backtrack (int t)  
  2. {  
  3.     if (t>n)   
  4.         output(x); //已到叶子结点，输出结果  
  5.     else  
  6.     for (int i=f(n,t);i<=g(n,t);i++) {  
  7.         x[t]=h(i);  
  8.         if (constraint(t)&&bound(t))  
  9.             backtrack(t+1);  
  10.     }  
  11. }  

    f(n,t) ，g(n,t) ：表示当前扩展结点处未搜索过的子树的起始编号和终止编号。
    h(i)：表示在当前扩展结点处x[t]的第i个可选值。

    迭代回溯：

    采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。

[cpp] view
plaincopy

  1. void iterativeBacktrack ()  
  2. {  
  3.     int t=1;  
  4.     while (t>0) {  
  5.         if (f(n,t)<=g(n,t))   
  6.             for (int i=f(n,t);i<=g(n,t);i++) {  
  7.                 x[t]=h(i);  
  8.                 if (constraint(t)&&bound(t)) {  
  9.                     if (solution(t)) output(x);  
  10.                     else t++;  
  11.                 }  
  12.         }  
  13.         else t--;  
  14.     }  
  15. }  

    子集树与排列树：

    子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间称为子集树。例如，那个物品的0-1背包问题所相应的解空间树就是一颗子集树。这类子集问题通常有2^n个叶节点，其节点总个数为2^(n+1)-1。遍历子集树的任何算法均需要O(2^n)的计算时间。


     用回溯法遍历子集树的一般算法可描述如下：

[cpp] view
plaincopy

  1. void backtrack (int t)  
  2. {   
  3.     if (t>n) output(x);  
  4.     else  
  5.         for (int i=0;i<=1;i++) {  
  6.             x[t]=i;  
  7.             if (legal(t)) backtrack(t+1);  
  8.         }  
  9. }  

   排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶子节点。因此遍历排列树需要O(n!)的计算时间。


    用回溯法遍历排列树的一般算法可描述如下：

[cpp] view
plaincopy

  1. void backtrack (int t)  
  2. {   
  3.     if (t>n) output(x);  
  4.     else  
  5.         for (int i=t;i<=n;i++) {  
  6.             swap(x[t], x[i]);  
  7.             if (legal(t)) backtrack(t+1);  
  8.             swap(x[t], x[i]);  
  9.         }  
  10. }   

    2、装载问题

    问题描述：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且，装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有，找出一种装载方案。

     例如：当n=3,c1=c2=50,且w=[10,40,40]时，则可以将集装箱1和2装到第一艘轮船上，而将集装箱3装到第二艘轮船上；如果w=[20,40,40]，则无法将这3个集装箱都装上轮船。

   基本思路： 容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
    (1)首先将第一艘轮船尽可能装满；
    (2)将剩余的集装箱装上第二艘轮船。
    将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1。由此可知，装载问题等价于以下特殊的0-1背包问题。


    用回溯法设计解装载问题的O(2^n)计算时间算法。在某些情况下该算法优于动态规划算法。

    算法设计：

    用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。用可行性约束函数可剪去不满足约束条件的子树。在子集树的第j+1层的结点z处，用cw记当前的装载重量，即cw=，则当cw>c1时，以结点z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。（该约束函数去除不可行解，得到所有可行解）。

     可以引入一个上界函数，用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率。设z是解空间树第i层上的当前扩展结点。cw是当前载重量；bestw是当前最优载重量；r是剩余集装箱的重量，即r=。定义上界函数为cw+r。在以z为根的子树中任一叶结点所相应的载重量均不超过cw+r。因此，当cw+r<=bestw时，可将z的右子树剪去。

     递归回溯具体代码如下：

[cpp] view
plaincopy

  1. #include "stdafx.h"  
  2. #include <iostream>  
  3. using namespace std;   
  4.   
  5. template <class Type>  
  6. class Loading  
  7. {  
  8.     //friend Type MaxLoading(Type[],Type,int,int []);  
  9.     //private:  
  10.     public:  
  11.         void Backtrack(int i);  
  12.         int n,          //集装箱数  
  13.             *x,         //当前解  
  14.             *bestx;     //当前最优解  
  15.             Type *w,    //集装箱重量数组  
  16.             c,          //第一艘轮船的载重量  
  17.             cw,         //当前载重量  
  18.             bestw,      //当前最优载重量  
  19.             r;          //剩余集装箱重量  
  20. };  
  21.   
  22. template <class Type>  
  23. void  Loading <Type>::Backtrack (int i);  
  24.   
  25. template<class Type>  
  26. Type MaxLoading(Type w[], Type c, int n, int bestx[]);  
  27.   
  28. int main()  
  29. {     
  30.     int n=3,m;  
  31.     int c=50,c2=50;  
  32.   
  33.     int w[4]={0,10,40,40};  
  34.     int bestx[4];  
  35.   
  36.     m=MaxLoading(w, c, n, bestx);  
  37.   
  38.     cout<<"轮船的载重量分别为："<<endl;  
  39.     cout<<"c(1)="<<c<<",c(2)="<<c2<<endl;  
  40.   
  41.     cout<<"待装集装箱重量分别为："<<endl;  
  42.     cout<<"w(i)=";  
  43.     for (int i=1;i<=n;i++)  
  44.     {  
  45.         cout<<w[i]<<" ";  
  46.     }  
  47.     cout<<endl;  
  48.   
  49.     cout<<"回溯选择结果为："<<endl;  
  50.     cout<<"m(1)="<<m<<endl;  
  51.     cout<<"x(i)=";  
  52.   
  53.     for (int i=1;i<=n;i++)  
  54.     {  
  55.         cout<<bestx[i]<<" ";  
  56.     }  
  57.     cout<<endl;  
  58.   
  59.     int m2=0;  
  60.     for (int j=1;j<=n;j++)  
  61.     {  
  62.         m2=m2+w[j]*(1-bestx[j]);  
  63.     }  
  64.     cout<<"m(2)="<<m2<<endl;  
  65.   
  66.     if(m2>c2)  
  67.     {  
  68.         cout<<"因为m(2)大于c(2),所以原问题无解！"<<endl;  
  69.     }  
  70.     return 0;  
  71. }  
  72.   
  73. template <class Type>  
  74. void  Loading <Type>::Backtrack (int i)// 搜索第i层结点  
  75. {  
  76.     if (i > n)// 到达叶结点  
  77.     {    
  78.         if (cw>bestw)  
  79.         {  
  80.             for(int j=1;j<=n;j++)   
  81.             {  
  82.                 bestx[j]=x[j];//更新最优解  
  83.                 bestw=cw;   
  84.             }  
  85.         }   
  86.         return;  
  87.     }  
  88.   
  89.     r-=w[i];   
  90.     if (cw + w[i] <= c) // 搜索左子树  
  91.     {   
  92.         x[i] = 1;  
  93.         cw += w[i];  
  94.         Backtrack(i+1);  
  95.         cw-=w[i];      
  96.     }  
  97.   
  98.     if (cw + r > bestw)  
  99.     {  
  100.         x[i] = 0;  // 搜索右子树  
  101.         Backtrack(i + 1);    
  102.     }  
  103.     r+=w[i];   
  104. }  
  105.   
  106. template<class Type>  
  107. Type MaxLoading(Type w[], Type c, int n, int bestx[])//返回最优载重量  
  108. {  
  109.     Loading<Type>X;  
  110.     //初始化X  
  111.     X.x=new int[n+1];  
  112.     X.w=w;  
  113.     X.c=c;  
  114.     X.n=n;  
  115.     X.bestx=bestx;  
  116.     X.bestw=0;  
  117.     X.cw=0;  
  118.     //初始化r  
  119.     X.r=0;  
  120.   
  121.     for (int i=1;i<=n;i++)  
  122.     {  
  123.         X.r+=w[i];  
  124.     }  
  125.   
  126.     X.Backtrack(1);  
  127.     delete []X.x;  
  128.     return X.bestw;  
  129. }  

     迭代回溯具体代码如下：

[cpp] view
plaincopy

  1. #include "stdafx.h"  
  2. #include <iostream>  
  3. using namespace std;   
  4.   
  5. template<class Type>  
  6. Type MaxLoading(Type w[ ], Type c, int n, int bestx[ ]);  
  7.   
  8. int main()  
  9. {     
  10.     int n=3,m;  
  11.     int c=50,c2=50;  
  12.     int w[4]={0,10,40,40};  
  13.     int bestx[4];  
  14.   
  15.     m=MaxLoading(w, c, n, bestx);  
  16.   
  17.     cout<<"轮船的载重量分别为："<<endl;  
  18.     cout<<"c(1)="<<c<<",c(2)="<<c2<<endl;  
  19.   
  20.     cout<<"待装集装箱重量分别为："<<endl;  
  21.     cout<<"w(i)=";  
  22.     for (int i=1;i<=n;i++)  
  23.     {  
  24.         cout<<w[i]<<" ";  
  25.     }  
  26.     cout<<endl;  
  27.   
  28.     cout<<"回溯选择结果为："<<endl;  
  29.     cout<<"m(1)="<<m<<endl;  
  30.     cout<<"x(i)=";  
  31.   
  32.     for (int i=1;i<=n;i++)  
  33.     {  
  34.         cout<<bestx[i]<<" ";  
  35.     }  
  36.     cout<<endl;  
  37.   
  38.     int m2=0;  
  39.     for (int j=1;j<=n;j++)  
  40.     {  
  41.         m2=m2+w[j]*(1-bestx[j]);  
  42.     }  
  43.     cout<<"m(2)="<<m2<<endl;  
  44.   
  45.     if(m2>c2)   
  46.     {  
  47.         cout<<"因为m(2)大于c(2),所以原问题无解！"<<endl;  
  48.     }  
  49.     return 0;  
  50. }  
  51.   
  52.   
  53. template <class Type>  
  54. Type MaxLoading(Type w[],Type c,int n,int bestx[])//迭代回溯法，返回最优载重量及其相应解，初始化根结点  
  55. {  
  56.     int i=1;//当前层，x[1:i-1]为当前路径  
  57.     int *x=new int[n+1];  
  58.   
  59.     Type bestw=0,      //当前最优载重量  
  60.          cw=0,         //当前载重量  
  61.          r=0;          //剩余集装箱重量  
  62.   
  63.     for (int j=1;j<=n;j++)  
  64.     {  
  65.         r+=w[j];  
  66.     }  
  67.   
  68.     while(true)//搜索子树  
  69.     {       
  70.         while(i<=n &&cw+w[i]<=c)//进入左子树  
  71.         {  
  72.             r-=w[i];  
  73.             cw+=w[i];  
  74.             x[i]=1;  
  75.             i++;  
  76.         }  
  77.           
  78.         if (i>n)//到达叶结点  
  79.         {        
  80.             for (int j=1;j<=n;j++)  
  81.             {  
  82.                 bestx[j]=x[j];  
  83.             }  
  84.             bestw=cw;  
  85.         }  
  86.         else//进入右子树  
  87.         {            
  88.             r-=w[i];  
  89.             x[i]=0; i++;  
  90.         }  
  91.         while (cw+r<=bestw)  
  92.         { //剪枝回溯  
  93.             i--;     
  94.             while (i>0 && !x[i])  
  95.             {   
  96.                 r+=w[i];  
  97.                 i--;  
  98.             }     
  99.             //从右子树返回  
  100.             if (i==0)  
  101.             {  
  102.                 delete []x;  
  103.                 return bestw;  
  104.             }  
  105.             x[i]=0;  
  106.             cw-=w[i];  
  107.             i++;  
  108.         }   
  109.     }    
  110. }  

     程序运行结果如图：



 

0028算法笔记——【回溯法】批作业调度问题和符号三角形问题

分类： 算法2013-04-06
16:55 443人阅读 评论(3) 收藏 举报
回溯法批处理作业调度符号三角形算法笔记排列树

     1、批作业调度问题

     (1)问题描述

     给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。

     批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

      例：设n=3，考虑以下实例：


     这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。

     (2)算法设计

     批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。按照回溯法搜索排列树的算法框架，设开始时x=[1,2,……n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列构成。


     算法具体代码如下：

[cpp] view
plaincopy

  1. #include "stdafx.h"  
  2. #include <iostream>  
  3. using namespace std;   
  4.   
  5. class Flowshop  
  6. {  
  7.     friend int Flow(int **M,int n,int bestx[]);  
  8.     private:  
  9.         void Backtrack(int i);  
  10.   
  11.         int **M,    // 各作业所需的处理时间  
  12.             *x,     // 当前作业调度  
  13.             *bestx,    // 当前最优作业调度  
  14.   
  15.             *f2,    // 机器2完成处理时间  
  16.             f1,    // 机器1完成处理时间  
  17.             f,     // 完成时间和  
  18.   
  19.             bestf,    // 当前最优值  
  20.             n;  // 作业数  
  21.  };   
  22.   
  23. int Flow(int **M,int n,int bestx[]);  
  24.   
  25. template <class Type>  
  26. inline void Swap(Type &a, Type &b);  
  27.   
  28. int main()  
  29. {  
  30.     int n=3,bf;  
  31.     int M1[4][3]={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};  
  32.   
  33.     int **M=new int*[n+1];  
  34.   
  35.     for(int i=0;i<=n;i++)  
  36.     {  
  37.         M[i]=new int[3];  
  38.     }  
  39.     cout<<"M(i,j)值如下："<<endl;  
  40.   
  41.     for(int i=0;i<=n;i++)  
  42.     {  
  43.         for(int j=0;j<3;j++)  
  44.         {  
  45.             M[i][j]=M1[i][j];  
  46.         }  
  47.     }  
  48.   
  49.     int bestx[4];  
  50.     for(int i=1;i<=n;i++)  
  51.     {  
  52.         cout<<"(";  
  53.         for(int j=1;j<3;j++)  
  54.         cout<<M[i][j]<<" ";  
  55.         cout<<")";  
  56.     }  
  57.   
  58.     bf=Flow(M,n,bestx);  
  59.   
  60.     for(int i=0;i<=n;i++)  
  61.     {  
  62.         delete []M[i];  
  63.     }  
  64.     delete []M;  
  65.   
  66.     M=0;  
  67.   
  68.     cout<<endl<<"最优值是："<<bf<<endl;  
  69.     cout<<"最优调度是：";  
  70.   
  71.     for(int i=1;i<=n;i++)  
  72.     {  
  73.         cout<<bestx[i]<<" ";  
  74.     }  
  75.     cout<<endl;  
  76.     return 0;  
  77. }  
  78.   
  79. void Flowshop::Backtrack(int i)  
  80. {    
  81.     if (i>n)  
  82.     {  
  83.         for (int j=1; j<=n; j++)  
  84.         {  
  85.             bestx[j] = x[j];  
  86.         }  
  87.         bestf = f;  
  88.     }  
  89.    else  
  90.    {  
  91.         for (int j = i; j <= n; j++)  
  92.         {  
  93.             f1+=M[x[j]][1];  
  94.             //机器2执行的是机器1已完成的作业，所以是i-1  
  95.             f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];  
  96.   
  97.             f+=f2[i];  
  98.             if (f < bestf)//剪枝  
  99.             {  
  100.                 Swap(x[i], x[j]);  
  101.                 Backtrack(i+1);  
  102.                 Swap(x[i], x[j]);  
  103.             }  
  104.             f1-=M[x[j]][1];  
  105.             f-=f2[i];  
  106.         }  
  107.     }  
  108. }  
  109.   
  110. int Flow(int **M,int n,int bestx[])  
  111. {  
  112.     int ub=30000;  
  113.   
  114.     Flowshop X;  
  115.     X.n=n;  
  116.     X.x=new int[n+1];  
  117.     X.f2=new int[n+1];  
  118.   
  119.     X.M=M;  
  120.     X.bestx=bestx;  
  121.     X.bestf=ub;  
  122.   
  123.     X.f1=0;  
  124.     X.f=0;  
  125.   
  126.     for(int i=0;i<=n;i++)  
  127.     {  
  128.         X.f2[i]=0,X.x[i]=i;  
  129.     }  
  130.     X.Backtrack(1);  
  131.     delete []X.x;  
  132.     delete []X.f2;  
  133.     return X.bestf;  
  134. }  
  135.   
  136. template <class Type>  
  137. inline void Swap(Type &a, Type &b)  
  138. {   
  139.     Type temp=a;   
  140.     a=b;   
  141.     b=temp;  
  142. }  

    由于算法Backtrack在每一个节点处耗费O(1)计算时间，故在最坏情况下，整个算法计算时间复杂性为O(n!)。程序运行结果如下：


     2、符号三角形问题

    (1)问题描速

    下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。


    在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。

    (2)算法设计

    解向量：用n元组x[1:n]表示符号三角形的第一行。 当x[i]=1时表示符号三角形第一行的第i个符号为"+"；当i=0时，表示符号三角形第一行的第i个符号为"-"；1<=x<=n。由于x[i]是二值的，所以可以用一棵完全二叉树来表示解空间。
    可行性约束函数：在符号三角形的第一行前i个符号x[1:i]确定后，就确定了一个由i(i+1)/2个符号组成的符号三角形。下一步确定x[i+1]的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x[1:i+1]所相应的符号三角形。最终由x[1:n]所确定的符号三角形中包含"+"号个数与"-"个数同为n(n+1)/4。因此，当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4
。
    无解的判断：对于给定的n，当n*(n+1)/2为奇数时，显然不存在包含的"+"号个数与"-"号个数相同的符号三角形。此时，可以通过简单的判断加以处理。 

    程序的具体代码如下：

[cpp] view
plaincopy

  1. #include "stdafx.h"  
  2. #include <iostream>  
  3. using namespace std;   
  4.   
  5. class Triangle   
  6. {  
  7.     friend int Compute(int);  
  8.     private:  
  9.         void Backtrack(int i);  
  10.         int n,      //第一行的符号个数  
  11.             half,   //n*(n+1)/4  
  12.             count,  //当前"+"号个数  
  13.             **p;    //符号三角矩阵  
  14.         long sum;   //已找到的符号三角形数               
  15. };   
  16.   
  17. int Compute(int n);  
  18.   
  19. int main()  
  20. {  
  21.     for(int n=1;n<=10;n++)  
  22.     {  
  23.         cout<<"n="<<n<<"时，共有"<<Compute(n);  
  24.         cout<<"个不同的符号三角形。"<<endl;  
  25.     }  
  26.    return 0;  
  27. }  
  28.   
  29. void Triangle::Backtrack(int t)  
  30. {  
  31.     if ((count>half)||(t*(t-1)/2-count>half))   
  32.     {  
  33.         return;  
  34.     }  
  35.   
  36.     if (t>n)  
  37.     {  
  38.         sum++;  
  39.     }  
  40.     else  
  41.     {  
  42.         for (int i=0;i<2;i++)   
  43.         {  
  44.             p[1][t]=i;//第一行符号  
  45.             count+=i;//当前"+"号个数  
  46.   
  47.             for(int j=2;j<=t;j++)   
  48.             {  
  49.                 p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];  
  50.                 count+=p[j][t-j+1];  
  51.             }  
  52.             Backtrack(t+1);  
  53.             for (int j=2;j<=t;j++)  
  54.             {  
  55.                 count-=p[j][t-j+1];  
  56.             }  
  57.             count-=i;  
  58.         }  
  59.     }  
  60. }  
  61.   
  62. int Compute(int n)  
  63. {  
  64.     Triangle X;  
  65.     X.n=n;  
  66.     X.count=0;  
  67.     X.sum=0;  
  68.   
  69.     X.half=n*(n+1)/2;  
  70.     if(X.half%2==1)return 0;  
  71.     X.half=X.half/2;  
  72.   
  73.     int**p=new int*[n+1];  
  74.   
  75.     for(int i=0;i<=n;i++)  
  76.     {  
  77.         p[i]=new int[n+1];  
  78.     }  
  79.   
  80.     for(int i=0;i<=n;i++)    
  81.     {  
  82.         for(int j=0;j<=n;j++)  
  83.         {  
  84.             p[i][j]=0;  
  85.         }  
  86.     }  
  87.   
  88.     X.p=p;  
  89.     X.Backtrack(1);  
  90.     for(int i=0;i<=n;i++)  
  91.     {  
  92.         delete []p[i];  
  93.     }  
  94.     delete []p;  
  95.     p=0;  
  96.     return X.sum;  
  97. }  

     计算可行性约束需要O(n)时间，在最坏情况下有 O(2^n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2^n)。程序运行结果如图：



0030算法笔记——【回溯法】最大团问题和图的m着色问题

分类： 算法2013-04-10
11:13 390人阅读 评论(0) 收藏 举报
最大团问题图的m着色问题算法笔记回溯法剪枝函数

     1、最大团问题

     问题描述

     给定无向图G=(V, E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果U∈V，且对任意两个顶点u，v∈U有(u, v)∈E，则称U是G的完全子图(完全图G就是指图G的每个顶点之间都有连边)。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。

     如果U∈V且对任意u，v∈U有(u, v)不属于E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。

     对于任一无向图G=(V, E)，其补图G'=(V', E')定义为：V'=V，且(u, v)∈E'当且仅当(u, v)∈E。
     如果U是G的完全子图，则它也是G'的空子图，反之亦然。因此，G的团与G'的独立集之间存在一一对应的关系。特殊地，U是G的最大团当且仅当U是G'的最大独立集。

     例：如图所示，给定无向图G={V, E}，其中V={1,2,3,4,5}，E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。根据最大团(MCP)定义，子集{1,2}是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1,2,5}之中。{1,2,5}是G的一个最大团。{1,4,5}和{2,3,5}也是G的最大团。右侧图是无向图G的补图G'。根据最大独立集定义，{2,4}是G的一个空子图，同时也是G的一个最大独立集。虽然{1,2}也是G'的空子图，但它不是G'的独立集，因为它包含在G'的空子图{1,2,5}中。{1,2,5}是G'的最大独立集。{1,4,5}和{2,3,5}也是G'的最大独立集。


     算法设计

     无向图G的最大团和最大独立集问题都可以用回溯法在O(n2^n)的时间内解决。图G的最大团和最大独立集问题都可以看做是图G的顶点集V的子集选取问题。因此可以用子集树来表示问题的解空间。首先设最大团为一个空团，往其中加入一个顶点，然后依次考虑每个顶点，查看该顶点加入团之后仍然构成一个团，如果可以，考虑将该顶点加入团或者舍弃两种情况，如果不行，直接舍弃，然后递归判断下一顶点。对于无连接或者直接舍弃两种情况，在递归前，可采用剪枝策略来避免无效搜索。为了判断当前顶点加入团之后是否仍是一个团，只需要考虑该顶点和团中顶点是否都有连接。程序中采用了一个比较简单的剪枝策略，即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数，可停止继续深度搜索，否则继续深度递归当搜索到一个叶结点时，即可停止搜索，此时更新最优解和最优值。

     算法具体实现如下：

[cpp] view
plaincopy

  1. //最大团问题 回溯法求解  
  2. #include "stdafx.h"  
  3. #include <iostream>  
  4. #include <fstream>  
  5. using namespace std;  
  6.   
  7. const int N = 5;//图G的顶点数  
  8. ifstream fin("5d7.txt");     
  9.   
  10. class Clique  
  11. {  
  12.     friend int MaxClique(int **,int[],int);  
  13.     private:  
  14.         void Backtrack(int i);  
  15.         int **a,        //图G的邻接矩阵  
  16.             n,          //图G的顶点数  
  17.             *x,         //当前解  
  18.             *bestx,     //当前最优解  
  19.             cn,         //当前顶点数  
  20.             bestn;      //当前最大顶点数  
  21. };  
  22.   
  23. int MaxClique(int **a, int v[], int n);  
  24.   
  25. int main()  
  26. {  
  27.     int v[N+1];  
  28.     int **a = new int *[N+1];    
  29.     for(int i=1;i<=N;i++)      
  30.     {      
  31.         a[i] = new int[N+1];      
  32.     }   
  33.       
  34.     cout<<"图G的邻接矩阵为:"<<endl;  
  35.     for(int i=1; i<=N; i++)    
  36.     {    
  37.         for(int j=1; j<=N; j++)    
  38.         {    
  39.             fin>>a[i][j];        
  40.             cout<<a[i][j]<<" ";      
  41.         }    
  42.         cout<<endl;    
  43.     }  
  44.   
  45.     cout<<"图G的最大团解向量为："<<endl;  
  46.     cout<<"图G的最大团顶点个数为："<<MaxClique(a,v,N)<<endl;  
  47.   
  48.     for(int i=1;i<=N;i++)      
  49.     {      
  50.         delete[] a[i];     
  51.     }   
  52.     delete []a;  
  53.     return 0;  
  54. }  
  55.   
  56. // 计算最大团  
  57. void Clique::Backtrack(int i)  
  58. {  
  59.     if (i > n) // 到达叶结点  
  60.     {  
  61.         for (int j = 1; j <= n; j++)  
  62.         {  
  63.             bestx[j] = x[j];  
  64.             cout<<x[j]<<" ";  
  65.         }  
  66.         cout<<endl;  
  67.         bestn = cn;  
  68.         return;  
  69.     }  
  70.     // 检查顶点 i 与当前团的连接  
  71.     int OK = 1;  
  72.     for (int j = 1; j < i; j++)  
  73.     if (x[j] && a[i][j] == 0)  
  74.     {  
  75.         // i与j不相连  
  76.         OK = 0;  
  77.         break;  
  78.     }  
  79.   
  80.     if (OK)// 进入左子树  
  81.     {  
  82.         x[i] = 1;  
  83.         cn++;  
  84.         Backtrack(i+1);  
  85.         x[i] = 0;  
  86.         cn--;  
  87.     }  
  88.   
  89.     if (cn + n - i >= bestn)// 进入右子树  
  90.     {  
  91.         x[i] = 0;  
  92.         Backtrack(i+1);  
  93.     }  
  94. }  
  95.   
  96. int MaxClique(int **a, int v[], int n)  
  97. {  
  98.     Clique Y;  
  99.   
  100.     //初始化Y  
  101.     Y.x = new int[n+1];  
  102.     Y.a = a;  
  103.     Y.n = n;  
  104.     Y.cn = 0;  
  105.     Y.bestn = 0;  
  106.     Y.bestx = v;  
  107.     Y.Backtrack(1);  
  108.     delete[] Y.x;  
  109.     return Y.bestn;  
  110. }  

     程序运行结果如图：


     2、图的m着色问题

     问题描述

       给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

     四色猜想：四色问题是m图着色问题的一个特例，根据四色原理，证明平面或球面上的任何地图的所有区域都至多可用四种、颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。这个问题可转换成对一平面图的４－着色判定问题(平面图是一个能画于平面上而边无任何交叉的图)。将地图的每个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。多年来，虽然已证明用5种颜色足以对任一幅地图着色，但是一直找不到一定要求多于4种颜色的地图。直到1976年这个问题才由爱普尔，黑肯和考西利用电子计算机的帮助得以解决。他们证明了4种颜色足以对任何地图着色。


     算法设计

     考虑所有的图，讨论在至多使用m种颜色的情况下，可对一给定的图着色的所有不同方法。通过回溯的方法，不断的为每一个节点着色，在前面n-1个节点都合法的着色之后，开始对第n个节点进行着色，这时候枚举可用的m个颜色，通过和第n个节点相邻的节点的颜色，来判断这个颜色是否合法，如果找到那么一种颜色使得第n个节点能够着色，那么说明m种颜色的方案是可行的。

     用m种颜色为无向图G=(V,E)着色，其中，V的顶点个数为n，可以用一个n元组x=(x1,x2,…,xn)来描述图的一种可能着色，其中，xi∈{1, 2, …, m}，(1≤i≤n)表示赋予顶点i的颜色。例如，5元组(1, 2, 2, 3, 1)表示对具有5个顶点的无向图（a）的一种着色，顶点A着颜色1，顶点B着颜色2，顶点C着颜色2，如此等等。如果在n元组X中，所有相邻顶点都不会着相同颜色，就称此n元组为可行解，否则为无效解。容易看出，每个顶点可着颜色有m种选择，n个顶点就有mn种不同的着色方案，问题的解空间是一棵高度为n的完全m叉树，这里树高度的定义为从根节点到叶子节点的路径的长度。每个分支结点，都有m个儿子结点。最底层有mn个叶子结点。例如，表示用3种颜色为3个顶点的图着色的状态空间树。如图所示，对第i（i>=1）层上的每个顶点，从其父节点到该节点的边上的标号表示顶点i着色的颜色编号。


    算法具体实现代码如下：

[cpp] view
plaincopy

  1. //图的着色问题 回溯法求解  
  2. #include "stdafx.h"  
  3. #include <iostream>  
  4. #include <fstream>  
  5. using namespace std;  
  6.   
  7. const int N = 5;//图的顶点数  
  8. const int M = 3;//色彩数  
  9. ifstream fin("5d8.txt");   
  10.   
  11. class Color  
  12. {  
  13.     friend int mColoring(int, int, int **);  
  14.     private:  
  15.         bool Ok(int k);  
  16.         void Backtrack(int t);  
  17.         int n,      //图的顶点数  
  18.             m,      //可用的颜色数  
  19.             **a,    //图的邻接矩阵  
  20.             *x;     //当前解  
  21.         long sum;   //当前已找到的可m着色方案数  
  22. };  
  23.   
  24. int mColoring(int n,int m,int **a);  
  25.   
  26. int main()  
  27. {  
  28.     int **a = new int *[N+1];    
  29.     for(int i=1;i<=N;i++)      
  30.     {      
  31.         a[i] = new int[N+1];      
  32.     }   
  33.       
  34.     cout<<"图G的邻接矩阵为:"<<endl;  
  35.     for(int i=1; i<=N; i++)    
  36.     {    
  37.         for(int j=1; j<=N; j++)    
  38.         {    
  39.             fin>>a[i][j];        
  40.             cout<<a[i][j]<<" ";      
  41.         }    
  42.         cout<<endl;    
  43.     }  
  44.     cout<<"图G的着色方案如下："<<endl;  
  45.     cout<<"当m="<<M<<"时，图G的可行着色方案数目为："<<mColoring(N,M,a)<<endl;  
  46.     for(int i=1;i<=N;i++)      
  47.     {      
  48.         delete[] a[i];     
  49.     }   
  50.     delete []a;  
  51. }  
  52.   
  53. void Color::Backtrack(int t)  
  54. {  
  55.     if (t>n)  
  56.     {  
  57.         sum++;  
  58.         for (int i=1; i<=n; i++)  
  59.         cout << x[i] << " ";  
  60.         cout << endl;  
  61.     }  
  62.     else  
  63.     {  
  64.         for (int i=1;i<=m;i++) {  
  65.             x[t]=i;  
  66.             if (Ok(t)) Backtrack(t+1);  
  67.         }  
  68.     }  
  69. }  
  70.   
  71. bool Color::Ok(int k)// 检查颜色可用性  
  72. {  
  73.     for (int j=1;j<=n;j++)  
  74.     {  
  75.         if ((a[k][j]==1)&&(x[j]==x[k])) //相邻且颜色相同  
  76.         {  
  77.             return false;  
  78.         }  
  79.     }  
  80.     return true;  
  81. }  
  82.   
  83. int mColoring(int n,int m,int **a)  
  84. {  
  85.     Color X;  
  86.   
  87.     //初始化X  
  88.     X.n = n;  
  89.     X.m = m;  
  90.     X.a = a;  
  91.     X.sum = 0;  
  92.     int *p = new int[n+1];  
  93.     for(int i=0; i<=n; i++)  
  94.     {  
  95.         p[i] = 0;  
  96.     }  
  97.     X.x = p;  
  98.     X.Backtrack(1);  
  99.     delete []p;  
  100.     return X.sum;  
  101. }  

     图m可着色问题的解空间树中内结点个数是。对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是。程序运行结果如图：


0031算法笔记——【回溯法】旅行员售货问题和圆排列问题

分类： 算法2013-05-06
15:47 261人阅读 评论(0) 收藏 举报
回溯法旅行员售货问题圆排列问题算法笔记排列树

     1、旅行员售货问题

    问题描述

     某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。



    问题分析

     旅行售货员问题的解空间是一棵排列树。对于排列树的回溯法与生成1,2,……n的所有排列的递归算法Perm类似。开始时x=[1,2,……n],则相应的排列树有x[1:n]的所有排列构成。

     在递归算法Backtrack中，当i=n时，当前扩展节点是排列树的叶节点的父节点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在，则找到一条旅行员售货回路。此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回流的费用bestc。如果是，则必须更新当前最优值bestc和当前最优解bestx。

     当i<n时，当前扩展节点位于排列树的第i-1层。图G中存在从顶点x[i-1]到顶点x[i]的边时，x[1:i]构成图G的一条路径，且当x[1:i]的费用小于当前最优值时算法进入树的第i层，否则将剪去相应的子树。

     算法具体代码如下：

[cpp] view
plaincopy

  1. //5d9 旅行员售货问题 回溯法求解  
  2. #include "stdafx.h"  
  3. #include <iostream>  
  4. #include <fstream>   
  5. using namespace std;  
  6.   
  7. ifstream fin("5d9.txt");   
  8. const int N = 4;//图的顶点数    
  9.   
  10. template<class Type>  
  11. class Traveling  
  12. {  
  13.     template<class Type>  
  14.     friend Type TSP(Type **a, int n);  
  15.     private:  
  16.         void Backtrack(int i);  
  17.         int n,           // 图G的顶点数  
  18.             *x,          // 当前解  
  19.             *bestx;      // 当前最优解  
  20.             Type **a,    // 图G的领接矩阵  
  21.             cc,          // 当前费用  
  22.             bestc;       // 当前最优值  
  23.             int NoEdge;  // 无边标记  
  24.  };   
  25.   
  26. template <class Type>  
  27. inline void Swap(Type &a, Type &b);  
  28.   
  29. template<class Type>  
  30. Type TSP(Type **a, int n);  
  31.   
  32. int main()  
  33. {  
  34.     cout<<"图的顶点个数 n="<<N<<endl;  
  35.   
  36.     int **a=new int*[N+1];  
  37.     for(int i=0;i<=N;i++)  
  38.     {  
  39.         a[i]=new int[N+1];  
  40.     }  
  41.   
  42.     cout<<"图的邻接矩阵为:"<<endl;  
  43.   
  44.     for(int i=1;i<=N;i++)  
  45.     {  
  46.         for(int j=1;j<=N;j++)  
  47.         {  
  48.             fin>>a[i][j];  
  49.             cout<<a[i][j]<<" ";  
  50.         }  
  51.         cout<<endl;  
  52.     }  
  53.     cout<<"最短回路的长为："<<TSP(a,N)<<endl;  
  54.   
  55.     for(int i=0;i<=N;i++)  
  56.     {  
  57.         delete []a[i];  
  58.     }  
  59.     delete []a;  
  60.   
  61.     a=0;  
  62.     return 0;  
  63. }  
  64.   
  65. template<class Type>  
  66. void Traveling<Type>::Backtrack(int i)  
  67. {   
  68.     if (i == n)  
  69.     {  
  70.         if (a[x[n-1]][x[n]] != 0 && a[x[n]][1] != 0 &&   
  71.             (cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc || bestc == 0))   
  72.         {  
  73.             for (int j = 1; j <= n; j++) bestx[j] = x[j];  
  74.             bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];    
  75.         }  
  76.     }  
  77.     else  
  78.     {  
  79.         for (int j = i; j <= n; j++)  
  80.         {  
  81.              // 是否可进入x[j]子树?  
  82.              if (a[x[i-1]][x[j]] != 0 && (cc + a[x[i-1]][x[i]] < bestc || bestc == 0))  
  83.              {  
  84.                 // 搜索子树  
  85.                 Swap(x[i], x[j]);  
  86.                 cc += a[x[i-1]][x[i]];  //当前费用累加  
  87.                 Backtrack(i+1);         //排列向右扩展,排列树向下一层扩展  
  88.                 cc -= a[x[i-1]][x[i]];    
  89.                 Swap(x[i], x[j]);  
  90.              }   
  91.         }  
  92.     }  
  93. }  
  94.   
  95. template<class Type>  
  96. Type TSP(Type **a, int n)  
  97. {  
  98.     Traveling<Type> Y;  
  99.     Y.n=n;  
  100.     Y.x=new int[n+1];  
  101.     Y.bestx=new int[n+1];  
  102.   
  103.     for(int i=1;i<=n;i++)  
  104.     {  
  105.         Y.x[i]=i;  
  106.     }  
  107.   
  108.     Y.a=a;  
  109.     Y.cc=0;  
  110.     Y.bestc=0;  
  111.   
  112.     Y.NoEdge=0;  
  113.     Y.Backtrack(2);  
  114.   
  115.     cout<<"最短回路为："<<endl;  
  116.     for(int i=1;i<=n;i++)    
  117.     {  
  118.         cout<<Y.bestx[i]<<" --> ";  
  119.     }  
  120.     cout<<Y.bestx[1]<<endl;  
  121.   
  122.     delete [] Y.x;  
  123.     Y.x=0;  
  124.     delete [] Y.bestx;  
  125.   
  126.     Y.bestx=0;  
  127.     return Y.bestc;  
  128. }  
  129.   
  130. template <class Type>  
  131. inline void Swap(Type &a, Type &b)  
  132. {    
  133.     Type temp=a;   
  134.     a=b;   
  135.     b=temp;  
  136. }  

     算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。 

     程序运行结果如图：


     2、圆排列问题

     问题描述

     给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为。


     问题分析

     圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时a=[r1,r2,……rn]是所给的n个元的半径，则相应的排列树由a[1:n]的所有排列构成。

    解圆排列问题的回溯算法中，CirclePerm(n,a)返回找到的最小的圆排列长度。初始时，数组a是输入的n个圆的半径，计算结束后返回相应于最优解的圆排列。center计算圆在当前圆排列中的横坐标，由x^2
= sqrt((r1+r2)^2-(r1-r2)^2)推导出x = 2*sqrt(r1*r2)。Compoute计算当前圆排列的长度。变量min记录当前最小圆排列长度。数组r表示当前圆排列。数组x则记录当前圆排列中各圆的圆心横坐标。

     在递归算法Backtrack中，当i>n时，算法搜索至叶节点，得到新的圆排列方案。此时算法调用Compute计算当前圆排列的长度，适时更新当前最优值。

     当i<n时，当前扩展节点位于排列树的i-1层。此时算法选择下一个要排列的圆，并计算相应的下界函数。

      算法具体代码如下：

[cpp] view
plaincopy

  1. //圆排列问题 回溯法求解  
  2. #include "stdafx.h"  
  3. #include <iostream>  
  4. #include <cmath>  
  5. using namespace std;  
  6.   
  7. float CirclePerm(int n,float *a);  
  8.   
  9. template <class Type>  
  10. inline void Swap(Type &a, Type &b);  
  11.   
  12. int main()  
  13. {  
  14.     float *a = new float[4];  
  15.     a[1] = 1,a[2] = 1,a[3] = 2;  
  16.     cout<<"圆排列中各圆的半径分别为："<<endl;  
  17.     for(int i=1; i<4; i++)  
  18.     {  
  19.         cout<<a[i]<<" ";  
  20.     }  
  21.     cout<<endl;  
  22.     cout<<"最小圆排列长度为：";  
  23.     cout<<CirclePerm(3,a)<<endl;  
  24.     return 0;  
  25. }  
  26.   
  27. class Circle  
  28. {  
  29.     friend float CirclePerm(int,float *);  
  30.     private:  
  31.         float Center(int t);//计算当前所选择的圆在当前圆排列中圆心的横坐标  
  32.         void Compute();//计算当前圆排列的长度  
  33.         void Backtrack(int t);  
  34.   
  35.         float min,  //当前最优值  
  36.               *x,   //当前圆排列圆心横坐标  
  37.               *r;   //当前圆排列  
  38.         int n;      //圆排列中圆的个数  
  39. };  
  40.   
  41. // 计算当前所选择圆的圆心横坐标  
  42. float Circle::Center(int t)  
  43. {  
  44.     float temp=0;  
  45.     for (int j=1;j<t;j++)  
  46.     {  
  47.         //由x^2 = sqrt((r1+r2)^2-(r1-r2)^2)推导而来  
  48.         float valuex=x[j]+2.0*sqrt(r[t]*r[j]);  
  49.         if (valuex>temp)  
  50.         {  
  51.             temp=valuex;  
  52.         }  
  53.     }  
  54.     return temp;  
  55. }  
  56.   
  57. // 计算当前圆排列的长度  
  58. void Circle::Compute(void)  
  59. {  
  60.     float low=0,high=0;  
  61.     for (int i=1;i<=n;i++)  
  62.     {  
  63.         if (x[i]-r[i]<low)  
  64.         {  
  65.             low=x[i]-r[i];  
  66.         }  
  67.   
  68.         if (x[i]+r[i]>high)  
  69.         {  
  70.             high=x[i]+r[i];  
  71.         }  
  72.     }  
  73.     if (high-low<min)  
  74.     {  
  75.         min=high-low;  
  76.     }  
  77. }  
  78.   
  79. void Circle::Backtrack(int t)  
  80. {  
  81.     if (t>n)  
  82.     {  
  83.         Compute();  
  84.     }  
  85.     else  
  86.     {  
  87.         for (int j = t; j <= n; j++)  
  88.         {  
  89.             Swap(r[t], r[j]);  
  90.             float centerx=Center(t);  
  91.             if (centerx+r[t]+r[1]<min)//下界约束  
  92.             {  
  93.                 x[t]=centerx;  
  94.                 Backtrack(t+1);  
  95.             }  
  96.             Swap(r[t], r[j]);  
  97.         }  
  98.     }  
  99. }  
  100.   
  101. float CirclePerm(int n,float *a)  
  102. {  
  103.     Circle X;  
  104.     X.n = n;  
  105.     X.r = a;  
  106.     X.min = 100000;  
  107.     float *x = new float[n+1];  
  108.     X.x = x;  
  109.     X.Backtrack(1);  
  110.     delete []x;  
  111.     return X.min;  
  112. }  
  113.   
  114. template <class Type>  
  115. inline void Swap(Type &a, Type &b)  
  116. {    
  117.     Type temp=a;   
  118.     a=b;   
  119.     b=temp;  
  120. }  

     如果不考虑计算当前圆排列中各圆的圆心横坐标和计算当前圆排列长度所需的计算时间按，则 Backtrack需要O(n!)计算时间。由于算法Backtrack在最坏情况下需要计算O(n!)次圆排列长度，每次计算需要O(n)计算时间，从而整个算法的计算时间复杂性为O((n+1)!)

     上述算法尚有许多改进的余地。例如，像1,2,…,n-1,n和n,n-1, …,2,1这种互为镜像的排列具有相同的圆排列长度，只计算一个就够了，可减少约一半的计算量。另一方面，如果所给的n个圆中有k个圆有相同的半径，则这k个圆产生的k!个完全相同的圆排列，只计算一个就够了。 

     程序运行结果为：


 

0032算法笔记——【回溯法】电路板排列问题和连续邮资问题

分类： 算法2013-05-08
10:10 410人阅读 评论(0) 收藏 举报
电路板排列问题连续邮资问题回溯法算法笔记等价类

     1、电路板排列问题

    问题描述

     将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B={1, 2, …, n}是n块电路板的集合，L={N1, N2, …, Nm}是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是x[i]。x所确定的电路板排列Density
(x)密度定义为跨越相邻电路板插槽的最大连线数。

    例：如图，设n=8, m=5，给定n块电路板及其m个连接块：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中两个可能的排列如图所示，则该电路板排列的密度分别是2，3。

       

     左上图中，跨越插槽2和3,4和5，以及插槽5和6的连线数均为2。插槽6和7之间无跨越连线。其余插槽之间只有1条跨越连线。在设计机箱时，插槽一侧的布线间隙由电路板的排列的密度确定。因此，电路板排列问题要求对于给定的电路板连接条件(连接块)，确定电路板的最佳排列，使其具有最小密度。

     问题分析

     电路板排列问题是NP难问题，因此不大可能找到解此问题的多项式时间算法。考虑采用回溯法系统的搜索问题解空间的排列树，找出电路板的最佳排列。设用数组B表示输入。B[i][j]的值为1当且仅当电路板i在连接块Nj中。设total[j]是连接块Nj中的电路板数。对于电路板的部分排列x[1:i]，设now[j]是x[1:i]中所包含的Nj中的电路板数。由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当now[j]>0且now[j]！=total[j]。用这个条件来计算插槽i和i+1间的连线密度。

    算法具体实现如下：

[cpp] view
plaincopy

  1. //电路板排列问题 回溯法求解  
  2. #include "stdafx.h"  
  3. #include <iostream>  
  4. #include <fstream>   
  5. using namespace std;  
  6.   
  7. ifstream fin("5d11.txt");   
  8.   
  9. class Board  
  10. {  
  11.     friend int Arrangement(int **B, int n, int m, int bestx[]);  
  12.     private:  
  13.         void Backtrack(int i,int cd);  
  14.         int n,      //电路板数  
  15.             m,      //连接板数  
  16.             *x,     //当前解  
  17.             *bestx,//当前最优解  
  18.             bestd,  //当前最优密度  
  19.             *total, //total[j]=连接块j的电路板数  
  20.             *now,   //now[j]=当前解中所含连接块j的电路板数  
  21.             **B;    //连接块数组  
  22. };  
  23.   
  24. template <class Type>  
  25. inline void Swap(Type &a, Type &b);  
  26.   
  27. int Arrangement(int **B, int n, int m, int bestx[]);  
  28.   
  29. int main()  
  30. {  
  31.     int m = 5,n = 8;  
  32.     int bestx[9];  
  33.   
  34.     //B={1,2,3,4,5,6,7,8}  
  35.     //N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}  
  36.   
  37.     cout<<"m="<<m<<",n="<<n<<endl;  
  38.     cout<<"N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}"<<endl;  
  39.     cout<<"二维数组B如下："<<endl;  
  40.   
  41.     //构造B  
  42.     int **B = new int*[n+1];  
  43.     for(int i=1; i<=n; i++)  
  44.     {  
  45.         B[i] = new int[m+1];  
  46.     }  
  47.   
  48.     for(int i=1; i<=n; i++)  
  49.     {  
  50.         for(int j=1; j<=m ;j++)  
  51.         {  
  52.             fin>>B[i][j];  
  53.             cout<<B[i][j]<<" ";  
  54.         }  
  55.         cout<<endl;  
  56.     }  
  57.   
  58.     cout<<"当前最优密度为:"<<Arrangement(B,n,m,bestx)<<endl;  
  59.     cout<<"最优排列为："<<endl;  
  60.     for(int i=1; i<=n; i++)  
  61.     {  
  62.         cout<<bestx[i]<<" ";  
  63.     }  
  64.     cout<<endl;  
  65.   
  66.     for(int i=1; i<=n; i++)  
  67.     {  
  68.         delete[] B[i];  
  69.     }  
  70.     delete[] B;  
  71.   
  72.     return 0;  
  73. }  
  74.   
  75. void Board::Backtrack(int i,int cd)//回溯法搜索排列树  
  76. {  
  77.     if(i == n)  
  78.     {  
  79.         for(int j=1; j<=n; j++)  
  80.         {  
  81.             bestx[j] = x[j];  
  82.         }  
  83.         bestd = cd;  
  84.     }  
  85.     else  
  86.     {  
  87.         for(int j=i; j<=n; j++)  
  88.         {  
  89.             //选择x[j]为下一块电路板  
  90.             int ld = 0;  
  91.             for(int k=1; k<=m; k++)  
  92.             {  
  93.                 now[k] += B[x[j]][k];  
  94.                 if(now[k]>0 && total[k]!=now[k])  
  95.                 {  
  96.                     ld ++;  
  97.                 }  
  98.             }  
  99.   
  100.             //更新ld  
  101.             if(cd>ld)  
  102.             {  
  103.                 ld = cd;  
  104.             }  
  105.   
  106.             if(ld<bestd)//搜索子树  
  107.             {  
  108.                 Swap(x[i],x[j]);  
  109.                 Backtrack(i+1,ld);  
  110.                 Swap(x[i],x[j]);  
  111.   
  112.                 //恢复状态  
  113.                 for(int k=1; k<=m; k++)  
  114.                 {  
  115.                     now[k] -= B[x[j]][k];  
  116.                 }  
  117.             }  
  118.         }  
  119.     }     
  120. }  
  121.   
  122. int Arrangement(int **B, int n, int m, int bestx[])  
  123. {  
  124.     Board X;  
  125.   
  126.     //初始化X  
  127.     X.x = new int[n+1];  
  128.     X.total = new int[m+1];  
  129.     X.now = new int[m+1];  
  130.     X.B = B;  
  131.     X.n = n;  
  132.     X.m = m;  
  133.     X.bestx = bestx;  
  134.     X.bestd = m+1;  
  135.   
  136.     //初始化total和now  
  137.     for(int i=1; i<=m; i++)  
  138.     {  
  139.         X.total[i] = 0;  
  140.         X.now[i] = 0;  
  141.     }  
  142.   
  143.   
  144.     //初始化x为单位排列并计算total  
  145.     for(int i=1; i<=n; i++)  
  146.     {  
  147.         X.x[i] = i;  
  148.         for(int j=1; j<=m; j++)  
  149.         {  
  150.             X.total[j] += B[i][j];  
  151.         }  
  152.     }  
  153.   
  154.     //回溯搜索  
  155.     X.Backtrack(1,0);  
  156.     delete []X.x;  
  157.     delete []X.total;  
  158.     delete []X.now;  
  159.     return X.bestd;  
  160. }  
  161.   
  162. template <class Type>  
  163. inline void Swap(Type &a, Type &b)  
  164. {    
  165.     Type temp=a;   
  166.     a=b;   
  167.     b=temp;  
  168. }  

    算法效率

     在解空间排列树的每个节点处，算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。另外，生成排列树需要O(n!)时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd>=0。因此最优解被更新的额次数为O(m)。更新最优解需要O(mn)时间。综上，解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)。

     程序运行结果为：


     2、连续邮资问题

     问题描述

     假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。

     问题分析

    解向量：用n元组x[1:n]表示n种不同的邮票面值，并约定它们从小到大排列。x[1]=1是唯一的选择。
    可行性约束函数：已选定x[1:i-1]，最大连续邮资区间是[1:r]，接下来x[i]的可取值范围是[x[i-1]+1:r+1]。

     计算X[1:i]的最大连续邮资区间在本算法中被频繁使用到，因此势必要找到一个高效的方法。直接递归的求解复杂度太高，我们不妨尝试计算用不超过m张面值为x[1:i]的邮票贴出邮资k所需的最少邮票数y[k]。通过y[k]可以很快推出r的值。如果y[r]的值在上述动态规划运算过程中已赋值，则y[r]<maxint。语句while(y[r]<maxint) r++可以很快的计算出r值。关键是如何计算数组y，分析过程如下：

     r表示由x[1…i]能贴出的最大连续区间，现在，要想把第i层的结点往下扩展，有两个问题需要解决：一，哪些数有可能成为下一个的邮票面值，即x[i+1]的取值范围是什么；二，对于一个确定的x[i+1]，如何更新r的值让它表示x[1…i+1]能表示的最大连续邮资区间。
第一个问题很简单，x[i+1]的取值要和前面i个数各不相同，最小应该是x[i] + 1，最大就是r+1，否则r+1没有办法表示。我们现在专注第二个问题。
第二个问题自己有两种思路：一，计算出所有使用不超过m张x[1…i+1]中的面值能够贴出的邮资，然后从r+1开始逐个检查是否被计算出来。二，从r+1开始，逐个询问它是不是可以用不超过m张x[1…i+1]中的面值贴出来。
     两种思路直接计算其计算量都是巨大的，需要借助动态规划的方法。模仿0-1背包问题，假设S(i)表示x[1…i]中不超过m张邮票的贴法的集合，这个集合中的元素数目是巨大的，例如，只使用1张邮票的贴法有C(i+1-1,1)＝C(i,1)=i种，使用2张邮票的贴法有C(i+2-1,2)=C(i+1,2)=i*(i+1)/2种，……，使用m张邮票的贴法有C(i+m-1, m)种，其中C(n,r)表示n个元素中取r个元素的组合数。于是，S(i)中的元素的数目总共有C(i+1-1, 1) + C(i+2-1,2)+
… + C(i+m-1,m)个。S(i)中的每个元素就是一种合法的贴法，对应一个邮资。当前最大连续邮资区间为1到r，那么S(i)中每个元素的邮资是不是也在1到r之间呢？不一定，比如{1,2,4}，当m=2时，它能贴出来8，但不能贴出来7。总之，在搜索时，一定要保持状态的一致性，即当深度搜索到第i层时，一定要确保用来保存结点状态的变量中保存的一定是第i层的这个结点的状态。定义S(i)中元素的值就是它所表示的贴法贴出来的邮资，于是，可以把S(i)中的元素按照它们的值的相等关系分成k类。第j类表示贴出邮资为j的所有的贴法集合，用T(j)表示，T(j)有可能是空集，例如对于{1,2,4},T(7)为空集，T(8)={{4,4}}。此时有：S(i)
= T(1) U T(2) U T(3) U … U T(k)，U表示两个集合的并。
     现在考虑x[i+1]加入后对当前状态S(i)的影响。假设s是S(i)中的一个元素，即s表示一种合法的贴法，x[i+1]对s能贴出的邮资的影响就是x[i+1]的多次重复增加了s能贴出的邮资。x[i+1]对s的影响就是，如果s中贴的邮票不满m张，那就一直贴x[i+1]，直到s中有m张邮票，这个过程会产生出很多不同的邮资，它们都应该被加入到S(i+1)中。因为s属于S。

     综上分析，考虑如果使用动态规划方法计算数组y的值，状态转移过程：将x[i-1]加入等价类集S中，将会引起数组x能贴出的邮资范围变大，对S的影响是如果S中的邮票不满m张，那就一直贴x[i-1],直到S中有m张邮票，这个过程会产生很多不同的邮资，取能产生最多不同邮资的用邮票最少的那个元素。

      例如：如下图所示，设m=4,n=5。当x[1]=1时，2张{1,1}可以贴出邮资2。这时，设x[2]=3。将3往{1,1}中添加，产生新的邮资贴法：5:{3,1,1}，8:{3,3,1,1}。这时，程序需要更新数组y的值。如果新的贴法比y[5]，y[8]已有的贴法所用的张数更少，则更新之。


    算法具体实现如下：

[cpp] view
plaincopy

  1. //连续邮资问题 回溯法求解  
  2. #include "stdafx.h"  
  3. #include <iostream>  
  4. using namespace std;  
  5.   
  6. class Stamp  
  7. {  
  8.     friend int MaxStamp(int  ,int  ,int []);  
  9.     private:  
  10.         int Bound(int i);  
  11.         void Backtrack(int i,int r);  
  12.         int n;//邮票面值数  
  13.         int m;//每张信封最多允许贴的邮票数  
  14.         int maxvalue;//当前最优值  
  15.         int maxint;//大整数  
  16.         int maxl;//邮资上界  
  17.         int *x;//当前解  
  18.         int *y;//贴出各种邮资所需最少邮票数  
  19.         int *bestx;//当前最优解  
  20. };  
  21.   
  22. int MaxStamp(int n,int m,int bestx[]);  
  23.   
  24. int main()  
  25. {  
  26.     int *bestx;  
  27.     int n = 5;  
  28.     int m = 4;  
  29.     cout<<"邮票面值数:"<<n<<endl;  
  30.     cout<<"每张信封最多允许贴的邮票数:"<<m<<endl;  
  31.   
  32.     bestx=new int[n+1];  
  33.     for(int i=1;i<=n;i++)  
  34.     {  
  35.         bestx[i]=0;  
  36.     }  
  37.       
  38.     cout<<"最大邮资:"<<MaxStamp(n,m,bestx)<<endl;  
  39.   
  40.     cout<<"当前最优解:";  
  41.     for(int i=1;i<=n;i++)  
  42.     {  
  43.         cout<<bestx[i]<<"  ";  
  44.     }  
  45.     cout<<endl;  
  46.       
  47.     return 0;  
  48. }  
  49.   
  50. void Stamp::Backtrack(int i,int r)  
  51. {  
  52.     /* 
  53.      *动态规划方法计算数组y的值。状态转移过程： 
  54.      *考虑将x[i-1]加入等价类集S中，将会引起数组x 
  55.      *能贴出的邮资范围变大，对S的影响是如果S中的 
  56.      *邮票不满m张，那就一直贴x[i-1],直到S中有m张 
  57.      *邮票，这个过程会产生很多不同的邮资，取能产生 
  58.      *最多不同邮资的用邮票最少的那个元素 
  59.      */  
  60.     for(int j=0;j<=x[i-2]*(m-1);j++)  
  61.     {  
  62.         if(y[j]<m)  
  63.         {  
  64.             for(int k=1;k<=m-y[j];k++)//k x[i-1]的重复次数  
  65.             {  
  66.                 if(y[j]+k<y[j+x[i-1]*k])  
  67.                 {  
  68.                     y[j+x[i-1]*k]=y[j]+k;  
  69.                 }  
  70.             }  
  71.         }  
  72.     }  
  73.   
  74.     //如果y[r]的值在上述动态规划运算过程中已赋值，则y[r]<maxint  
  75.     while(y[r]<maxint)  
  76.     {  
  77.         r++;  
  78.     }  
  79.   
  80.     if(i>n)  
  81.     {  
  82.         if(r-1>maxvalue)  
  83.         {  
  84.             maxvalue=r-1;  
  85.             for(int j=1;j<=n;j++)  
  86.             {  
  87.                 bestx[j]=x[j];  
  88.             }  
  89.         }  
  90.         return;  
  91.     }  
  92.   
  93.     int *z=new int[maxl+1];  
  94.   
  95.     for(int k=1;k<=maxl;k++)  
  96.     {  
  97.         z[k]=y[k];  
  98.     }  
  99.   
  100.     for(int j=x[i-1]+1;j<=r;j++)  
  101.     {  
  102.         x[i]=j;  
  103.         Backtrack(i+1,r);  
  104.         for(int k=1;k<=maxl;k++)  
  105.         {  
  106.             y[k]=z[k];  
  107.         }  
  108.     }  
  109.     delete[] z;  
  110. }  
  111.   
  112. int MaxStamp(int n,int m,int bestx[])  
  113. {  
  114.     Stamp X;  
  115.     int maxint=32767;  
  116.     int maxl=1500;  
  117.       
  118.     X.n=n;  
  119.     X.m=m;  
  120.     X.maxvalue=0;  
  121.   
  122.     X.maxint=maxint;  
  123.     X.maxl=maxl;  
  124.     X.bestx=bestx;  
  125.   
  126.     X.x=new int [n+1];  
  127.     X.y=new int [maxl+1];  
  128.       
  129.     for(int i=0;i<=n;i++)  
  130.     {  
  131.         X.x[i]=0;  
  132.     }  
  133.   
  134.     for(int i=1;i<=maxl;i++)  
  135.     {  
  136.         X.y[i]=maxint;  
  137.     }  
  138.   
  139.     X.x[1]=1;  
  140.     X.y[0]=0;  
  141.   
  142.     X.Backtrack(2,1);  
  143.   
  144.     delete[] X.x;  
  145.     delete [] X.y;  
  146.     return X.maxvalue;  
  147. }  

     程序运行结果如图：


 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞