分支限界法求图的最短路径

分支限界法

定义：

分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：

　　1 ．产生当前扩展结点的所有孩子结点；

　　2 ．在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；

　　3 ．将其余的孩子结点加入活结点表；

　　4 ．从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解（最优解）或活结点表为空。分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。

问题描述：

给定n个城市，有一个旅行商从某一城市出发，访问每个城市各一次后再回到原出发城市，要求找出的巡回路径最短。

问题分析：

分支限界法是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。在总的原则下，根据对状态控件树中结点检索的次序的不同又将分支限界设计策路分为数种不同的检索方法。在求解旅行商问题时，程序中采用FIFO检索（First In First Out），它的活结点表采用一张先进先出表（即队列）。可以看出，分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。

代码实现：

 1 #include"stdlib.h"
 2 #include <iostream>
 3 using namespace std;
 4 
 5 //各个城市之间的路径长度
 6 int CityVal[4][4]={
 7                     {0 ,30,6,4},
 8                     {30,0 ,5,10},
 9                     {6,5,0 ,20 },
10                     {4,10,20 ,0}};
11 
12 struct CityNum{
13     int MinVal[2];       //最短路径长度
14     int PastCity[2][4]; //走过的路径
15 }city[4];
16 
17 int find(int j,int k,int boolnum)
18 {
19     int i;
20     for(i=0;i<4;i++)
21         if(j==city[k].PastCity[boolnum][i])
22             return 1;
23     return 0;
24 }
25 void copy(int k,int boolnum1,int j,int boolnum2)
26 {
27     int i=0;
28     while(city[k].PastCity[boolnum1][i]!=0)
29     {
30     city[j].PastCity[boolnum2][i]=city[k].PastCity[boolnum1][i];
31     i++;
32     }
33     city[j].PastCity[boolnum2][i]=k;
34 }
35 
36 
37 
38 int main()
39 {
40     int i,j,k;
41     int boolnum=0;
42     int TempMinVal;
43     int TempCity;
44     int TempVal;
45     for(i=0;i<2;i++)
46         for(j=0;j<4;j++)
47             for(k=0;k<4;k++)
48                 city[k].PastCity[i][j]=0;
49     for(i=1;i<4;i++)
50         city[i].MinVal[boolnum]=CityVal[i][0];
51     for(i=0;i<2;i++)
52     {
53         for(j=1;j<4;j++)
54         {
55             TempMinVal=32767;
56             for(k=1;k<4;k++)
57             {
58                 if(j!=k&&!find(j,k,boolnum))
59                 {
60                 TempVal=CityVal[j][k]+city[k].MinVal[boolnum];
61                     if(TempMinVal>TempVal)
62                     {
63                         TempMinVal=TempVal;
64                         TempCity=k;
65                     }
66                 }
67             }
68             city[j].MinVal[(boolnum+1)%2]=TempMinVal;
69             copy(TempCity,boolnum,j,(boolnum+1)%2);
70         }
71         boolnum=(boolnum+1)%2;
72     }
73     TempMinVal=32767;
74     for(i=1;i<4;i++)
75     {
76         TempVal=CityVal[0][i]+city[i].MinVal[boolnum];
77         if(TempMinVal>TempVal)
78         {
79             TempMinVal=TempVal;
80             TempCity=i;
81         }
82     }
83     cout<<"最小费用为:"<<TempMinVal<<endl;
84     cout<<"最佳周游路径为:";
85     cout<<1<<' ';
86     cout<<TempCity+1<<' ';
87     for(i=1;i>=0;i--)
88         cout<<city[TempCity].PastCity[boolnum][i]+1<<' ';
89     cout<<1<<endl;
90 }