simulatedannealing.cpp

模拟煺火算法,学人工智能的时候写的一个小程序,准确率还是很高的.

// SimulatedAnnealing.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include<string>
#include <cmath>
#include <ctime>
using namespace std;

struct City{
	string name;
	double x;
	double y;
};

int city=0;                            //城市个数
City* cities=NULL;				//存储城市信息
double temperature= 0.0;   //当前温度
int* solution_before = NULL;//前一个温度时的解
int* solution_now    = NULL;//现在温度求得的解

//fstream out("result10.txt");      //保存结果

void readFile(){
	char fileName[20];
	cout<<"请输入文件名";
	cin>>fileName;
	cout<<"需要停止时按CTRL+C，现在开始搜索………"<<endl;
	ifstream inFile(fileName);
	if(!inFile){
		cout<<"文件名有误"<<endl;
		exit(1);
	}
	inFile>>city;
	cities = new City[city];
	for(int i=0; i<city;i++){
		inFile >> cities[i].name;
		inFile >> cities[i].x;
		inFile >> cities[i].y;
	}
	inFile.close();
}   

void Start(){                                                                   //设置初始状态
	temperature = 280;
	if(solution_now!=NULL) 	delete []  solution_now;
	solution_now = new int[city];
	for(int i=0; i<city;i++)
		solution_now[i] = i;
}

void Gen_solution(int* solution_new){                                  //
	int i,j;
	while(true){
		i = rand() % city;
		j = rand() % city;
		if(i ==j||i==0||j==0)
			continue;
		if(i>j){
			int temp = i;
			i = j;
			j = temp;
		}
		break;
	}

	for(int k = 0; k<city; k++)
		solution_new[k] =solution_now[k];
	for(int k = 0; k<=j-i; k++)
		solution_new[i + k] =solution_now[j-k];
}

double Distance(int one,int two){
	return sqrt( (cities[one].x - cities[two].x) * (cities[one].x - cities[two].x) + (cities[one].y - cities[two].y) * (cities[one].y - cities[two].y));
}

double Length(int* res){
	double num = 0.0;
	num += Distance(res[0],res[city-1]);
	for(int i=0;i<city-1;i++){
		num += Distance(res[i],res[i+1]);
	}
	return num;
}

void Print(){
	for(int i=0; i<city; i++)
	{
		cout<<cities[solution_now[i]].name<<" ";
//		out<<cities[solution_now[i]].name<<" ";
	}
	cout<<"长度：";
	//out<<"长度：";
	cout<<Length(solution_now)<<endl;
	//out<<Length(solution_now)<<endl;
}

void Simulate(){
	int loop=0;
	while(true ){
		Start();
		loop++;
		cout<<"第"<<loop<<"次:";
		//out<<"第"<<loop<<"次:";
		while(true){  
			if(solution_before)
				delete [] solution_before;
			solution_before = new int[city];
			for(int i = 0; i<city; i++)
				solution_before[i] = solution_now[i]; 

			for(int i=0; i<100*city; i++){
				int* solution_new;
				bool change = false;
				solution_new = new int[city];
				Gen_solution(solution_new);

				double dis_new =Length(solution_new) ;
				double dis_now = Length(solution_now);
				if(dis_new<dis_now){
					delete [] solution_now ;
					solution_now = solution_new;
					change = true;
				}
				else{
					if(exp( ( dis_now-dis_new ) / temperature)>(double)rand()/RAND_MAX){
						delete [] solution_now;
						solution_now = solution_new;
						change = true;
					}
				}
				if(!change)
					delete [] solution_new;
			}
			if( fabs(Length(solution_before) -Length(solution_now)) < 0.000001){
				Print();
				break;
			}
			temperature= 0.92 * temperature;
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	readFile();
	srand((unsigned int)time(NULL));
	Simulate();
	return 0;
}