distance.cpp

本程序用另外一种算法即近邻算法解决ＴＳＰ

/* distance.cpp 读取城市坐标信息，计算两两城市之间的距离，生成距离文件*/
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
using namespace std;

int main()
{ 
	//申明和初始化变量
	char city_name[20];
	float city_x[20], city_y[20];
	float city_distance[20][20];
	float max_distance, min_distance;
	int i=0, k, j;
	string filename;
	ifstream sensor;
	ofstream inform;


	//请求用户输入文件名
	cout<<"enter the name of the data file:(it should be 'data.txt' here)  ";
	cin>>filename;

	//打开文件读取数据信息
	sensor.open(filename.c_str());
	if(sensor.fail())
	{
		cout<<"Error opening input file\n";
	}
	else
	{
		//没有到达文件末尾时循环读取数据
		
		while(!sensor.eof())
		{
			sensor>>city_name[i]>>city_x[i]>>city_y[i];
			i++;
		}
	}
 

	//计算任意两城市之间的距离，求出最大、最小距离

	//初始化最大、最小距离值
    max_distance=sqrt(pow(city_x[1]-city_x[0],2)+pow(city_y[1]-city_y[0],2));
	min_distance=max_distance;

	for(k=0;k<i-1;k++)
	{
		for(j=k+1;j<i;j++)
		{
			city_distance[k][j]=sqrt(pow(city_x[j]-city_x[k],2)+pow(city_y[j]-city_y[k],2));
			if(max_distance<city_distance[k][j])
			{
				max_distance=city_distance[k][j];
			}
			if(min_distance>city_distance[k][j])
			{
				min_distance=city_distance[k][j];
			}
		}
	}

	for(k=0;k<i;k++)
	{
		city_distance[k][k]=0;

		for(j=0;j<k;j++)
		{
			city_distance[k][j]=city_distance[j][k];
		}
	}


	//生成距离文件distance.txt, 文件的开始一行显示的是最大、最小距离
	//第i+1行显示的是：城市i和其他各城市之间的距离

	filename="distance.txt";

	//打开文件
	inform.open(filename.c_str());

	//设置输出格式
	inform.setf(ios::fixed);
	inform.precision(3);

    //写入最大、最小距离信息
	inform<<max_distance<<' '<<min_distance<<endl;

	//写入全部距离信息
	for(k=0;k<i;k++)
	{
		for(j=0;j<i;j++)
		{
			inform<<city_distance[k][j]<<' ';
		}
		inform<<endl;
	}

	//关闭文件
	inform.close();
	return 0;
}