您的位置: 首页  >  文章  >  分支限界法

分支限界法

分类: 文章 • 2025-04-28 16:52:16

分支限界法（branch and bound method）按广度优先策略搜索问题的解空间树，在搜索过程中，对待处理的节点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大或极小）的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。分支限界法适合求解最优化问题。



 1、分支限界法思想

       上节中回溯法是从根节点出发，按照深度优先的策略搜索问题的解空间树，在搜索过程中，如果某点所代表的部分解不满足约束条件，则对该节点为根的子树进行剪枝；否则继续按照深度优先的策略搜索以该结点为根，当搜索到一个满足的约束条件的叶子结点时，就找到了一个可行解。


       分支限界法首先要确定一个合理的限界函数（bound funciton），并根据限界函数确定目标函数的界[down ,up]，按照广度优先策略搜索问题的解空间树，在分直结点上依次扩展该结点的孩子结点，分别估算孩子结点的目标函数可能值，如果某孩子结点的目标函数可能超出目标函数的界，则将其丢弃；否则将其加入待处理结点表（简称PT表），依次从表PT中选取使目标函数取得极值的结点成为当前扩展结点，重复上述过程，直到得到最优解。




2、TSP问题中使用分支限界法

       【TSP问题】：

       TSP问题是指旅行家要旅行n个城市，要求各个城市经理且仅经理依次然后回到出发城市，并要求所走的路程最短。我们以下图的无限图为例，采用分支限界法解决这个问题。


分支限界法


       该无向图对应的代价矩阵如下所示：

分支限界法

       代价矩阵是1到1,1到2,1到3,1到4,1到5距离写在第一行，第二行为2到1,2到2,2到3,2到4，、、、依次


       （1）找到目标函数的界。上界为，采用贪心算法求得上界，从节点1开始到节点3--->5--->4--->2--->1,路径，即为图中红色圈的路径，其路径长度为C=1+2+3+7+3=16。

下界为矩阵中每行中两个最小的相加，所有的行加起来的和的一半。( (3+1)+(3+6)+(1+2)+(3+4)+(2 +3) )/2=14 

所以求得界为[14,16]。

       （2）计算每个节点的限界值。

计算目标函数（限界函数），lb分为三部分，第一部分是经过路径的长度相加的2倍，加上第二部分离着路径首尾节点最近的距离相加（不在已知路径上的），加上第三部分除了路径上节点，矩阵中两个最短的距离相加，最后这三部分和相加，得到的结果除以2便是每个节点的限界值。（对于1条正在生成的路径/部分解，设已经确定的顶点(已经经过/遍历的城市)集合为U=(r1, r2, …, rk)，则该部分解的目标函数的下界为(已经经过的路径的总长的2倍+从起点到最近未遍历城市的距离+从终点到最近未遍历城市的距离+进入/离开未遍历城市时各未遍历城市带来的最小路径成本)除以2并向上取整。假设正在生成的路径/部分解为1→4,U={1,4},未遍历城市={2,3,5},该部分解下界为{2*5+1+3+(3+6)+(1+2)+(2+3)}/2向上取整等于16。）

       （3）画出PT图。如下所示。



分支限界法


 

              根据上述所述得到最优解1-->3-->5-->4-->2-->1



【C代码】：

[cpp] view plain copy
  1. //分支限界法  
  2. #include<iostream>  
  3. #include<algorithm>  
  4. #include<cstdio>  
  5. #include<queue>  
  6. #define INF 100000  
  7. using namespace std;  
  8. /*  n*n的一个矩阵  */  
  9. int n;  
  10. int mp[22][22];//最少3个点，最多15个点  
  11. /*输入距离矩阵*/  
  12. void in()  
  13. {  
  14.     scanf("%d",&n);  
  15.     for(int i=1; i<=n; i++)  
  16.     {  
  17.         for(int j=1; j<=n; j++)  
  18.         {  
  19.             if(i==j)  
  20.             {  
  21.                 mp[i][j]=INF;  
  22.                 continue;  
  23.             }  
  24.             scanf("%d",&mp[i][j]);  
  25.         }  
  26.     }  
  27. }  
  28. struct node  
  29. {  
  30.     int visp[22];//标记哪些点走了  
  31.     int st;//起点  
  32.     int st_p;//起点的邻接点  
  33.     int ed;//终点  
  34.     int ed_p;//终点的邻接点  
  35.     int k;//走过的点数  
  36.     int sumv;//经过路径的距离  
  37.     int lb;//目标函数的值  
  38.     bool operator <(const node &p )const  
  39.     {  
  40.         return lb>p.lb;  
  41.     }  
  42. };  
  43. priority_queue<node> q;  
  44. int low,up;  
  45. int inq[22];  
  46. //确定上界  
  47. int dfs(int u,int k,int l)  
  48. {  
  49.     if(k==n) return l+mp[u][1];  
  50.     int minlen=INF , p;  
  51.     for(int i=1; i<=n; i++)  
  52.     {  
  53.         if(inq[i]==0&&minlen>mp[u][i])/*取与所有点的连边中最小的边*/  
  54.         {  
  55.             minlen=mp[u][i];  
  56.             p=i;  
  57.         }  
  58.     }  
  59.     inq[p]=1;  
  60.     return dfs(p,k+1,l+minlen);  
  61. }  
  62. int get_lb(node p)  
  63. {  
  64.     int ret=p.sumv*2;//路径上的点的距离  
  65.     int min1=INF,min2=INF;//起点和终点连出来的边  
  66.     for(int i=1; i<=n; i++)  
  67.     {  
  68.         if(p.visp[i]==0&&min1>mp[i][p.st])  
  69.         {  
  70.             min1=mp[i][p.st];  
  71.         }  
  72.     }  
  73.     ret+=min1;  
  74.     for(int i=1; i<=n; i++)  
  75.     {  
  76.         if(p.visp[i]==0&&min2>mp[p.ed][i])  
  77.         {  
  78.             min2=mp[p.ed][i];  
  79.         }  
  80.     }  
  81.     ret+=min2;  
  82.     for(int i=1; i<=n; i++)  
  83.     {  
  84.         if(p.visp[i]==0)  
  85.         {  
  86.             min1=min2=INF;  
  87.             for(int j=1; j<=n; j++)  
  88.             {  
  89.                 if(min1>mp[i][j])  
  90.                 min1=mp[i][j];  
  91.             }  
  92.             for(int j=1; j<=n; j++)  
  93.             {  
  94.                 if(min2>mp[j][i])  
  95.                 min2=mp[j][i];  
  96.             }  
  97.             ret+=min1+min2;  
  98.         }  
  99.     }  
  100.     return ret%2==0?(ret/2):(ret/2+1);  
  101. }  
  102. void get_up()  
  103. {  
  104.     inq[1]=1;  
  105.     up=dfs(1,1,0);  
  106. }  
  107. void get_low()  
  108. {  
  109.     low=0;  
  110.     for(int i=1; i<=n; i++)  
  111.     {  
  112.         /*通过排序求两个最小值*/  
  113.         int min1=INF,min2=INF;  
  114.         int tmpA[22];  
  115.         for(int j=1; j<=n; j++)  
  116.         {  
  117.             tmpA[j]=mp[i][j];  
  118.         }  
  119.         sort(tmpA+1,tmpA+1+n);//对临时的数组进行排序  
  120.         low+=tmpA[1];  
  121.     }  
  122. }  
  123. int solve()  
  124. {  
  125.     /*贪心法确定上界*/  
  126.     get_up();  
  127.       
  128.     /*取每行最小的边之和作为下界*/  
  129.     get_low();  
  130.       
  131.     /*设置初始点,默认从1开始 */  
  132.     node star;  
  133.     star.st=1;  
  134.     star.ed=1;  
  135.     star.k=1;  
  136.     for(int i=1; i<=n; i++) star.visp[i]=0;  
  137.     star.visp[1]=1;  
  138.     star.sumv=0;  
  139.     star.lb=low;  
  140.       
  141.     /*ret为问题的解*/  
  142.     int ret=INF;  
  143.       
  144.     q.push(star);  
  145.     while(!q.empty())  
  146.     {  
  147.         node tmp=q.top();  
  148.         q.pop();  
  149.         if(tmp.k==n-1)  
  150.         {  
  151.             /*找最后一个没有走的点*/  
  152.             int p;  
  153.             for(int i=1; i<=n; i++)  
  154.             {  
  155.                 if(tmp.visp[i]==0)  
  156.                 {  
  157.                     p=i;  
  158.                     break;  
  159.                 }  
  160.             }  
  161.             int ans=tmp.sumv+mp[p][tmp.st]+mp[tmp.ed][p];  
  162.             node judge = q.top();  
  163.               
  164.             /*如果当前的路径和比所有的目标函数值都小则跳出*/  
  165.             if(ans <= judge.lb)  
  166.             {  
  167.                 ret=min(ans,ret);  
  168.                 break;  
  169.             }  
  170.             /*否则继续求其他可能的路径和，并更新上界*/  
  171.             else  
  172.             {  
  173.                 up = min(up,ans);  
  174.                 ret=min(ret,ans);  
  175.                 continue;  
  176.             }  
  177.         }  
  178.         /*当前点可以向下扩展的点入优先级队列*/  
  179.         node next;  
  180.         for(int i=1; i<=n; i++)  
  181.         {  
  182.             if(tmp.visp[i]==0)  
  183.             {  
  184.                 next.st=tmp.st;  
  185.   
  186.                 /*更新路径和*/  
  187.                 next.sumv=tmp.sumv+mp[tmp.ed][i];  
  188.   
  189.                 /*更新最后一个点*/  
  190.                 next.ed=i;  
  191.   
  192.                 /*更新顶点数*/  
  193.                 next.k=tmp.k+1;  
  194.   
  195.                 /*更新经过的顶点*/  
  196.                 for(int j=1; j<=n; j++) next.visp[j]=tmp.visp[j];  
  197.                 next.visp[i]=1;  
  198.   
  199.                 /*求目标函数*/  
  200.                 next.lb=get_lb(next);  
  201.                   
  202.                 /*如果大于上界就不加入队列*/  
  203.                 if(next.lb>up) continue;  
  204.                 q.push(next);  
  205.             }  
  206.         }  
  207.     }  
  208.     return ret;  
  209. }  
  210. int main()  
  211. {  
  212.     in();  
  213.     printf("%d\n",solve());  
  214.     return 0;  
  215. }  



3、分支限界法解决0/1背包问题。


       在这里只写个思路，相对来说也是比较简单的。

       （1）首先将背包按照价值由大到小进行排列。

       （2）找到上界和下界，背包问题的下界把第一个价值最大的装入背包。上界，采用背包问题的贪心算法（三种策略）最终求得上界。

       （3）限界函数ub=v+（W-w）*（v i+1    /    w i+1）

       （4）画PT表格，每个节点进行判断是否剪枝。最终得到最优解。



算法设计与分析大概总结到这。


       学习是一点一点深入的，这一点体会是多么的深刻，就像我的牙齿一样，黑的部分不是一天两天能黑的，牙疼的引起也不是一天两天的事情，要有牙齿病菌的这种精神！~~~

点击打开链接

相关推荐