/**
*遺傳算法求解中國旅行商問題
*遺傳算法使用的三個算子：
*（1）選擇算子：根據適應度函數，選擇適應度該高的個體進行下一步的雜交，
??????反應進化過程中優勝劣汰的自然規律
*（2）交叉算子：交叉過程隨機選擇兩個個體進行排隊，根據預先設定的交叉概
??????率Pc（0.5~0.8），決定是否交叉，交叉方法有單點交叉，兩點交叉，和均
	??勻交叉，這個類似于生物學中染色體交換基因片段
*（3）變異算子：變異算子將新個體的基因鏈中的某一位或者某一片段按變異概率
??????Pm（0.001~0.1）進行變異
**/

#include
#include
#include
#include
#include“qsort.h“
#define?INF?9999999??//指定為正無窮

//定義坐標點結構體
struct?Point
{
	int?x;
	int?y;
};
/**********************************************
*以下過程包括：
*1.?讀入31個城市的坐標位置
*2.?求任意兩個城市間的距離
*3.?求一條完整路徑的總長度
************************************************/
//從文件讀取坐標點
Point*?getPoints（int?len?char*?filename）
{
	Point*?ps?=?（Point*）malloc（sizeof（Point）*len）;
	FILE?*infile;
	fopen_s（&infile?filename?“r“）;
	if?（infile?==?NULL）
	{
		printf（“文件打開失敗\n“）;
	}
	for?（int?i?=?0;?i?	{
		fscanf_s（infile?“%d%d“?&ps[i].x?&ps[i].y）;
	}
	fclose（infile）;
	return?ps;
}

//求兩點間的距離
float?getDistance（Point?p1?Point?p2）
{
	return?powf（powf（p1.x?-?p2.x?2）?+?powf（p1.y?-?p2.y?2）?0.5）;
}

//計算任意兩座城市間的距離，并保存在二維數組里
float**?getAnyDistance（Point*?ps?int?len）//求任意兩座城市之間的距離
{
	float**?cost?=?（float**）malloc（sizeof（float*）*len）;
	for?（int?i?=?0;?i?	{
		cost[i]?=?（float*）malloc（sizeof（float）*len）;
	}
	for?（int?i?=?0;?i?	{
		for?（int?j?=?i?+?1;?j?		{
			cost[i][j]?=?getDistance（ps[i]?ps[j]）;
			cost[j][i]?=?cost[i][j];
		}
		cost[i][i]?=?0;
	}
	return?cost;
}

//計算一條環路的總長度，本算法里面的適應度就是以環路的長度為標準，越小適應度越高
float?getTotalDistance（int?*path?float?**cost?int?len）
{
	float?total?=?0;
	for?（int?i?=?0;?i?	{
		total?+=?cost[path[i]][path[i?+?1]];
	}
	total?+=?cost[path[len?-?1]][path[0]];
	return?total;
}

void?copyPath（int?*path1?int?*path2?int?len）
{
	while?（len>0）
	{
		path1[len?-?1]?=?path2[len?-?1];
		len--;
	}
}
/****************************************************/
//判斷值在不在數組的start位到end位之間，在返回標號，不在-1;
int?isInArray（int?value?int?*s?int?start?int?end）
{???
	//printf（“vslue=%d?start=%dend=%d\n“?valuestartend）;
	for?（int?i?=?start;?i?<=?end;?i++）
	{???
		//printf（“s[%d]?=?%d\n“?is[i]）;
		if?（s[i]?==?value）
		{???
			//printf（“%d返回值：%d\n“?i?s[i]）;
			return?i;
		}
	}	
		return?-1;		
}

//兩個個體交叉，產生兩個新的個體的過程
void?Cross（int?*f1?int?*f2?int?*s1?int?*s2?int?start?int?end?int?len）
{???
	
	if?（start?>=?end?||?end?>=?len）
	{
		return;
	}
	int?jk;
	for?（int?i?=?start;?i?<=?end;?i++）//交換start到end間的基因片段
	{
		s1[i]?=?f2[i];
		s2[i]?=?f1[i];
	}
	/**
	*理論上講交叉過程應該保持其他部分不變化，但受制于本討論問題中每一個城市
	*是唯一的，并且要求出現并且只能出現在回路中一次，（出發節點兩次）因此交換
	*基因片段后必將影響其他部分，這里的工作就是在盡量保證不變的前提下，解決沖突
	*本算法參考博客名為?xiaoning6p14?關于巡回旅行商問題的遺傳算法路徑交叉的思路
	*進行編寫，使用部分匹配交叉（PMX）詳細算法地址為：
	*http://blog.sina.com.cn/s/blog_5d7883db0100bl04.html
	**/
	for?（int?i?=?（end+1）%len;?i?!=?start;?i++i%=len）
	{???
		j?=?isInArray（f1[i]?s1?start?end）;
		if?（j!=-1）
		{??
			k?=?isInArray（f1[j]?s1?start

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2013-12-10?18:12??GA_TSP\
?????目錄???????????0??2013-12-04?15:47??GA_TSP\Debug\
?????文件???????37376??2013-12-04?17:28??GA_TSP\Debug\GA_TSP.exe
?????文件??????363452??2013-12-04?17:28??GA_TSP\Debug\GA_TSP.ilk
?????文件??????510976??2013-12-04?17:28??GA_TSP\Debug\GA_TSP.pdb
?????目錄???????????0??2013-12-04?17:28??GA_TSP\GA_TSP\
?????目錄???????????0??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\
?????文件???????27857??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA.obj
?????文件????????1857??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA_TSP.log
?????目錄???????????0??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA_TSP.tlog\
?????文件????????3902??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA_TSP.tlog\CL.read.1.tlog
?????文件????????1670??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA_TSP.tlog\CL.write.1.tlog
?????文件?????????171??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA_TSP.tlog\GA_TSP.lastbuildstate
?????文件????????1298??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA_TSP.tlog\cl.command.1.tlog
?????文件????????2442??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA_TSP.tlog\link.command.1.tlog
?????文件????????2660??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA_TSP.tlog\link.read.1.tlog
?????文件?????????580??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\GA_TSP.tlog\link.write.1.tlog
?????文件????????4430??2013-12-04?17:13??GA_TSP\GA_TSP\Debug\QSort.obj
?????文件???????60416??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\vc120.idb
?????文件???????86016??2013-12-04?17:28??GA_TSP\GA_TSP\Debug\vc120.pdb
?????文件????????7929??2013-12-04?17:28??GA_TSP\GA_TSP\GA.cpp
?????文件????????4188??2013-12-04?11:32??GA_TSP\GA_TSP\GA_TSP.vcxproj
?????文件????????1150??2013-12-04?11:32??GA_TSP\GA_TSP\GA_TSP.vcxproj.filters
?????文件?????????796??2013-12-04?17:10??GA_TSP\GA_TSP\QSort.cpp
?????文件?????????369??2013-12-02?13:46??GA_TSP\GA_TSP\points.txt
?????文件??????????50??2013-12-04?13:14??GA_TSP\GA_TSP\qsort.h
?????文件?????????338??2013-12-10?18:09??GA_TSP\GA_TSP\result.txt
?????文件?????2883584??2013-12-10?18:12??GA_TSP\GA_TSP.sdf
?????文件?????????964??2013-12-04?10:04??GA_TSP\GA_TSP.sln
?????文件???????24064??2013-12-10?18:12??GA_TSP\GA_TSP.v12.suo