small_tsp.cpp

一个小的TSP 问题,用遗传算法实现.可以用来学习.

#include <stdio.h>
#include <math.h>
#include <memory.h>
#include <time.h>
#include <conio.h>
#define MAX_NUM		20
double s_citys[MAX_NUM][2];
double s_distances[MAX_NUM][MAX_NUM];
int s_num = 0;
double s_min = 1e200;
int s_indexMin[MAX_NUM];
int s_index[MAX_NUM];
bool s_mark[MAX_NUM];

bool ReadFile()
{
	FILE * fp = fopen("citys.txt", "r");
	if(fp)
	{
		s_num = 0;
		while(!feof(fp) && s_num < MAX_NUM)
		{
			fscanf(fp, "%lf, %lf\n", &s_citys[s_num][0], &s_citys[s_num][1]);
			s_num++;
		}
		fclose(fp);
		return true;
	}
	return false;
}

void Search(int index)
{
	int i, j;
	double sum;
	for(i = 1; i < s_num; i++)
	{
		if(s_mark[i])
		{
			s_index[index] = i;
			s_mark[i] = false;
			if(index == s_num - 1)
			{
				// 计算总距离
				sum = 0.0;
				for(j = 0;j < s_num - 1; j++)
				{
					sum += s_distances[s_index[j]][s_index[j + 1]];
				}
				sum += s_distances[s_index[s_num - 1]][s_index[0]];
				if(sum < s_min)
				{
					memcpy(s_indexMin, s_index, sizeof(s_index));
					s_min = sum;
				}
			}
			else
			{
				Search(index + 1);
			}
			s_mark[i] = true;
		}
	}
}

void WriteFile()
{
	FILE * fp = fopen("result.txt", "w");
	if(fp)
	{
		for(int i = 0; i < s_num; i++)
		{
			fprintf(fp, "%d\n", s_indexMin[i]);
		}
		fclose(fp);
	}
}


void main()
{
	int i, j;
	if(ReadFile())
	{
		time_t start, end;
		double timeUsed;
		time(&start);
		printf("开始穷举,请等待...");
		for(i = 1; i < s_num; i++)
		{
			for(j = 0; j < i; j++)
			{
				s_distances[i][j] = 
					sqrt(
					(s_citys[i][0] - s_citys[j][0]) * (s_citys[i][0] - s_citys[j][0]) +
					(s_citys[i][1] - s_citys[j][1]) * (s_citys[i][1] - s_citys[j][1]));
				s_distances[j][i] = s_distances[i][j];
			}
		}
		s_min = 1e200;
		s_index[0] = 0;
		memset(s_mark, true, sizeof(s_mark));
		s_mark[0] = false;
		Search(1);
		time(&end);
		timeUsed = difftime(end, start);
		if(timeUsed < 1.0)
		{
			printf("\n用时小于1秒!\n");
		}
		else
		{
			printf("\n用时%.0lf秒!\n", timeUsed);
		}
		printf("\n最短行程%lf\n", s_min);
		printf("最佳访问序列:\n");
		for(int i = 0; i < s_num; i++)
		{
			printf("%02d\n", s_indexMin[i]);
		}
		WriteFile();
		printf("按任意键继续...");
		getch();
	}
	else
	{
		printf("读取文件失败");
	}
}