模拟退火算法解决TSP问题

本资源包括“基于模拟退火算法解决TSP问题”的相关代码以及TSP的城市数据。

#include 
#include  
#include 
#include 
#include 
#include 	// 本文用于输出对齐
#include 
#include 

#include “SA.h“

using namespace std;

// 城市数据格式转化
void CityDataTranslate（）{
	ifstream read_in;
	read_in.open（“L:\\Coding\\TSP_SA模拟退火算法\\TSP_SA模拟退火算法\\ch150.txt“）;		// 待转换数据
	if （!read_in.is_open（））
	{
		cout<<“文件读取失败.“<		return;
	}

	ofstream fout（“L:\\Coding\\TSP_SA模拟退火算法\\TSP_SA模拟退火算法\\city_150.txt“）;		// 转换后的数据存入文档 city_150.txt

	double city_table[MAX_CITYNUM][MAX_CITYNUM];
	int city_No[MAX_CITYNUM];
	double city_x[MAX_CITYNUM];
	double city_y[MAX_CITYNUM];

	int vex_num;
	read_in >> vex_num;
	fout << vex_num << endl;

	for （int i = 0; i < vex_num; i++）
	{
		read_in >> city_No[i] >> city_x[i] >> city_y[i];

		fout << i + 1 <<“ “;
	}
	fout<
	for （int i = 0; i < vex_num; i++）
	{
		city_table[i][i] = 0;
		for （int j = 0; j < vex_num; j++）
		{
			double temp = （city_x[i] - city_x[j]）*（city_x[i] - city_x[j]） + （city_y[i] - city_y[j]）*（city_y[i] - city_y[j]）;
			city_table[i][j] = sqrt（temp）;
			fout << city_table[i][j]<<“ “;
		}
		fout<	}
}

int main（）{
	// CityDataTranslate（）;   // 创建城市表

	time_t T_begin = clock（）;
	Graph G;
	CreateGraph（G）;

	// 1. initial w and target function f（w）
	// 2. random production new solution - eg: ABCDEA --> ABCEDA
	// 3. judge whether accepted new solution or not 
	// 4. Simulate Annealing

	TSP_solution bestSoluion = SA_TSP（G）;
	Display（G bestSoluion）;

	time_t T_end = clock（）;
	double RunningTime = double（T_end - T_begin）/CLOCKS_PER_SEC;

	cout<<“程序运行时间 RunningTime = “<
	system（“pause“）;
	return 0;
}

void CreateGraph（Graph &G）{
	ifstream read_in;
	read_in.open（“L:\\Coding\\TSP_SA模拟退火算法\\TSP_SA模拟退火算法\\city_5.txt“）;
	if （!read_in.is_open（））
	{
		cout<<“文件读取失败.“<		return;
	}

	read_in >> G.vex_num;
	// read_in >> G.arc_num;
	G.arc_num = 0;
	for （int i = 0;i < G.vex_num; i++）
	{
		read_in >> G.vexs[i];
	}
	G.vexs[G.vex_num] = ‘\0‘;	// char的结束符.

	for （int i = 0; i < G.vex_num;i++）
	{
		for （int j = 0; j < G.vex_num; j++）
		{
			read_in >> G.arcs[i][j];

			// calculate the arc_num
			if （G.arcs[i][j] > 0）
			{
				G.arc_num++;
			}
		}
	}

	// display
	cout<<“无向图创建完毕，相关信息如下：“<	cout<<“【顶点数】 G.vex_num = “<	cout<<“【边数】 G.arc_num = “<	cout<<“【顶点向量】 vexs[max_vexNum] = “;
	for （int i = 0; i < G.vex_num; i++）
	{
		cout << G.vexs[i] << “ “;
	}
	cout<	for （int i = 0; i < G.vex_num;i++）
	{
		for （int j = 0; j < G.vex_num; j++）
		{
			cout << std::right << setw（4） << G.arcs[i][j]<<“ “;
		}
		cout<	}
}

TSP_solution SA_TSP（Graph G）{
	srand （ unsigned （ time（0） ） ）;

	// 当前温度
	double Current_Temperature = INITIAL_TEMPERATURE;

	// 最优解
	TSP_solution Best_solution;
	Best_solution.le

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        758  2016-11-05 18:51  SA_TSP\city_10.txt

     文件       1098  2016-11-05 18:46  SA_TSP\city_12.txt

     文件       1736  2016-11-05 13:04  SA_TSP\city_15.txt

     文件       5248  2016-11-04 17:21  SA_TSP\city_26.txt

     文件       7422  2016-11-04 17:14  SA_TSP\city_31.txt

     文件         89  2017-01-16 23:48  SA_TSP\city_5.txt

     文件        277  2016-11-05 16:32  SA_TSP\city_6.txt

     文件        824  2017-01-16 22:58  SA_TSP\SA.h

     文件       7372  2017-01-16 23:48  SA_TSP\TSP_SA.cpp

     目录          0  2017-01-17 21:54  SA_TSP

----------- ---------  ---------- -----  ----

                24824                    10