d_function.cpp

分支限界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;
}