huolangdan.cpp

货郎担问题的程序,按照运行后出现的提示进行输出即可

                                                                                      
//#if !defined(TRAVELER_BASE_H)
#include<iostream.h>
#define TRAVELER_BASE_H
#define MAXNUM 999                    //城市间路径长度或者周游路线长度上限
int **c=NULL;                        //保存各个城市之间路径长度的二维数组c
bool *bv=NULL;                       //记录各个城市是否已游历过的状态的数组bv
int  *path=NULL;                     //记录最优周游路线的数组path
int  num_of_cities=0;
void init();                        //初始化函数,初始化货郎的游历图
int  T_cost(int i,bool bv[],int num);                   //求解最优周游路线长度的函数
int  T_path(int i,bool bv[],int num);                   //构造最优周游路径的函数
void Travelling();                //周游函数,调用上述函数计算最优周游成本及获取最优周游路线
void main()
{
	init();
	Travelling();
}

int  T_cost(int i,bool bv[],int num)                    
{
	bool flag=true;
	for(int j=0;j<num;j++)//查看是否所有城市都已经游历过
	{
		flag&=bv[j];
	}
    if(flag) return c[i][0];
	int mincost=MAXNUM;        //mincost记录当前城市i通过S中所有结点并在城市1终止的最短路径长度
	int cost,city;         //cost记录当前周游路径长度,city记录下一个要到达的城市
	for(j=1;j<num;j++)
	{
		if(bv[j]==true) continue;
		bv[j]=true;
		cost=c[i][j]+T_cost(j,bv,num);
		if(mincost>cost)
		{
			mincost=cost;
			city=j;
		}
		bv[j]=false;
	}
	return mincost;
}
int T_path(int i,bool bv[],int num)  //重新按最优路线游历一遍并记录下游历路径
{
	bool flag=true;
	for(int j=0;j<num;j++)
	{
		flag&=bv[j];
	}
    if(flag) return i;
	int mincost=MAXNUM;                      
	int cost,city;
	for(j=1;j<num;j++)
	{
		if(bv[j]==true) continue;
		bv[j]=true;
		cost=c[i][j]+T_cost(j,bv,num);
		if(mincost>cost)
		{
			mincost=cost;
			city=j; //利用city记住使式子g(i,S)=mincost{c[i][j]+g(j,S-{j})}取最小值的j
		}
		bv[j]=false;
	}
	return city;
}
void  Travelling()
{
	int mincost=MAXNUM;
	int cost;
	bv[0]=true;
	int city;                 //记录游历过的城市
	//开始计算从起始城市出发所周游的路线的最短长度,i为从起始城市出发到达的下一个城市
	for(int i=1;i<num_of_cities;i++)
	{
		bv[i]=true;
		cost=c[0][i]+T_cost(i,bv,num_of_cities);
		if(mincost>cost)
		{
			mincost=cost;
			city=i;        //city记录当前最短周游路线中的下一个城市i
		}
		bv[i]=false;
	}
    if(mincost>=MAXNUM)
	{
		cout<<"无法找到最优周游路线!"<<endl;
		return;
	}
	int start_city=0;
	path[start_city]=start_city+1;                  //从城市1出发开始周游
	start_city++;
	path[start_city]=city+1;
	start_city++;
	int next_city;
	bv[city]=true; //根据上述最短周游路线的计算结果,从城市1出发到达的下一个城市为city
	/*从城市city开始再次按最短周游路线重新游历一次,并用path记录下周游路线*/
	next_city=T_path(city,bv,num_of_cities);
	while(city!=next_city)
	{
		path[start_city]=next_city+1;
        start_city++;
		city=next_city;
		bv[city]=true;
		next_city=T_path(city,bv,num_of_cities);
	}
	path[start_city]=path[0];
    cout<<"最优周游路线为:"<<endl;
	for(i=0;i<=num_of_cities;i++) cout<<"城市"<<path[i]<<",";
	cout<<endl;
	cout<<"最优周游路线长度为:"<<mincost<<endl;
}
void init()
{
	cout<<"请输入要周游的城市的数目:";
	cin>>num_of_cities;
	if(num_of_cities<=0) return;
	path=new int[num_of_cities+1];
	bv=new bool[num_of_cities];
	c=new int*[num_of_cities];
	for(int i=0;i<num_of_cities;i++)
	{
		c[i]=new int[num_of_cities];
		for(int j=0;j<num_of_cities;j++)
		{
			if(j==i) c[i][j]=0;
			else
			{
				cout<<"城市"<<i+1<<"到城市"<<j+1<<"的路程:";
				cin>>c[i][j];
			}
		}
		bv[i]=false;       //初始时各个城市都未曾游历过
	}
	cout<<endl;
}

//#endif