d_function.rar_TSP 分支限界_branch and bound tsp_分支限界 TSP_分支限界tsp

//分支限界tsp算法中求下界函数的值 #include<iostream> #include<vector> using namespace std; class Down_function { public: // int r; int r1; int r2; int temp; vector <int> A; int weight[5][5]; void swap(int &x,int &y); int min(vector<int> A,int n); int Go(); int sum1(int weight[5][5],int n,int i,vector<int> &A); //返回矩阵行的r值 int sum2(int weight[5][5],int n,int i,vector<int> &A); //返回列的r值 Down_function(); }; Down_function::Down_function() { r1=0; r2=0; int W[5][5]={{888,19,10,29,12},{15,888,4,16,2},{20,7,888,18,3},{3,5,2,888,4},{15,4,14,7,888}}; for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ weight[i][j]=W[i][j]; } } } void Down_function::swap(int &x,int &y) { int t; t=x; x=y; y=t; } int Down_function::min(vector<int> A,int n) { int i,j; for(i=0;i<=n;i++) { for(j=n;j>i;j--) { if(A[j]<A[j-1]) swap(A[j],A[j-1]); } } //cout<<A[0]<<endl; return A[0]; } int Down_function::sum1(int w[5][5],int n,int i,vector<int> &A) //i表示计算到第几行 { temp=0; //记录每行的r值，每次进入函数就将其设为0 if(i==n){ return r1; } else{ for(int j=0;j<n;j++){ A.push_back(weight[i][j]); } temp=min(A,4); A.clear(); //见笔记 for(int s=0;s<n;s++){ weight[i][s]-=temp; } r1+=temp; sum1(weight,5,i+1,A); } } int Down_function::sum2(int w[5][5],int n,int i,vector<int> &A) { temp=0; if(i==n){ return r2; } else{ for(int j=0;j<n;j++){ A.push_back(weight[j][i]); } temp=min(A,4); A.clear(); for(int s=0;s<n;s++){ weight[s][i]-=temp; } r2+=temp; sum2(weight,5,i+1,A); } } int Down_function::Go() { int a=sum1(weight,5,0,A); int b=sum2(weight,5,0,A); int c=a+b; return c; } void main() { Down_function d1; cout<<d1.Go()<<endl; }