#?include?
#?include
#?include
#?include?
#?define?Max?31?

int?cnttstart;??????????????????????????//?要經過的城市個數起點
double?arry1[Max][Max];???????????????????//?鄰接矩陣，存放兩兩城市間的距離
double?fn=0gn=0hn=0;????????????????????//?啟發函數
double?f1=0g1=0h1=0;
int?arry3[Max];???????????????????????????//?存放已歷經的城市名
int?arry4[Max];???????????????????????????//?標志位數組，cn個城市中已歷經的置0，未歷經的置1

//?定義頂點數據類型
struct?Vertex???????????????
{
??int?x;
??int?y;
}City[Max];

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//?主函數
void?main（）
{??
??void?RandNum（int）;?
??void?CityCoordinate（）;
??double?CityCost（intint）;
??void?TSP（）;
??double?MaxLengh（）;

??int?ij;

??CityCoordinate（）;??????????//?隨機生成并顯示20個城市及其坐標

??printf（“\n“）;
??printf（“\n“）;?

???for（i=1;?i???{
?????tt=0;
?????for（j=i;?j?????{??
	???if（i==j）???arry1[i][j]=0;
???????else???arry1[i][j]=CityCost（ij）;
?????}
???}
??
??TSP（）;???????????????????????????????//?用最小生成樹查找最短路徑

??printf（“\n從%d出發的最佳路徑為：%d→“startstart）;
??for（i=2;i<=cn;i++）?printf（“%d→“arry3[i]）;
??printf（“%d\n“arry3[cn+1]）;

??printf（“總路徑長度為:%f\n“fn）;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//?隨機數產生器
int?RandNum（int?max）????????
{
??int?m;
??m=rand（）%（max-1）+1;???????????????????//?產生一個1~20的隨機數
??return?m;
}

//?生成并顯示城市坐標
void?CityCoordinate（）??????
{
??int?ijhh=0;

??srand（（unsigned）time（NULL））;???//?使用當前時間作為種子
??City[1].x=RandNum（Max）;????????//?生成并顯示第1個城市的坐標
??City[1].y=RandNum（Max）;
??printf（“City[1]的坐標:?（%d%d）;?????“?City[1].x?City[1].y）;
??

??for（i=2;i??{
????City[i].x=RandNum（Max）;
????City[i].y=RandNum（Max）;

????for（j=1;j???????if（City[i].x==?City[j].x&&?City[i].y==?City[j].y）
?????????i=i-1;
?
	hh++;?????????????????????????????//?換行
????if（0!=i%2）??hh=0;??????????????
	if（0==hh）???printf（“\n“）;

????printf（“City[%d]的坐標:?（%d%d）;???“?i?City[i].x?City[i].y）;//?顯示第i個城市的坐標
??}
}

//?計算并顯示城市間的歐式距離
double?CityCost（int?iint?j）
{
??int?x1x2y1y2hh=0;
??double?Distancet;

??x1=?City[i].x;
??x2=?City[j].x;
??y1=?City[i].y;
??y2=?City[j].y;
??t=（x1-x2）*?（x1-x2）+（y1-y2）*?（y1-y2）;
??Distance=sqrt（t）;
??arry1[i][j]=Distance;
??
??hh++;
??if（0!=tt%2）??hh=0;????????????//?換行??
??if（0==hh）???printf（“\n“）;

??printf（“%d與%d的距離：%3.2f??????“?i?j?Distance）;
??return?arry1[i][j];
}

//?用啟發式的MST查找最短路徑/////////////////////////////////////////////////////////
void?TSP（）
{
??int?Mnode;?????????????????????????????????????????//?起點，當前搜索層的父節點
??int?hiklmnnn;
??int?xy=0;
??int?arry2[Max]={00?00?0?00?00?0?00?00?0?00?00?00};?//?標志位數組，已歷經的置0，未歷經的置1
??double?temp1=

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????6668??2008-10-23?22:16??tsp\Ex2\Debug\BuildLog.htm

?????文件????????406??2008-10-21?11:47??tsp\Ex2\Debug\Ex2.exe.embed.manifest

?????文件????????472??2008-10-21?11:47??tsp\Ex2\Debug\Ex2.exe.embed.manifest.res

?????文件????????381??2008-10-23?22:16??tsp\Ex2\Debug\Ex2.exe.intermediate.manifest

?????文件????1170000??2008-12-18?13:42??tsp\Ex2\Debug\Ex2.ilk

?????文件??????13980??2008-12-18?13:40??tsp\Ex2\Debug\Ex2.obj

?????文件?????233816??2008-12-18?13:39??tsp\Ex2\Debug\Ex2.pch

?????文件????2321408??2008-10-23?22:16??tsp\Ex2\Debug\Ex2.pdb

?????文件?????????67??2008-10-23?22:16??tsp\Ex2\Debug\mt.dep

?????文件??????41984??2008-12-18?13:42??tsp\Ex2\Debug\vc60.idb

?????文件??????53248??2008-12-18?13:40??tsp\Ex2\Debug\vc60.pdb

?????文件??????27648??2008-10-20?21:56??tsp\Ex2\Debug\vc80.idb

?????文件??????36864??2008-10-20?21:56??tsp\Ex2\Debug\vc80.pdb

?????文件??????68608??2008-10-23?22:16??tsp\Ex2\Debug\vc90.idb

?????文件??????69632??2008-10-23?22:16??tsp\Ex2\Debug\vc90.pdb

?????文件???????6873??2008-12-18?13:43??tsp\Ex2\Ex2.cpp

?????文件???????3365??2008-10-20?21:48??tsp\Ex2\Ex2.dsp

?????文件????????514??2008-10-20?21:55??tsp\Ex2\Ex2.dsw

?????文件??????41984??2008-12-18?13:43??tsp\Ex2\Ex2.ncb

?????文件??????53760??2008-12-18?13:43??tsp\Ex2\Ex2.opt

?????文件???????1029??2008-12-18?13:42??tsp\Ex2\Ex2.plg

?????文件????????871??2008-10-25?11:56??tsp\Ex2\Ex2.sln

????..A..H.?????15360??2008-12-18?13:44??tsp\Ex2\Ex2.suo

?????文件???????4854??2008-10-20?21:56??tsp\Ex2\Ex2.vcproj

?????文件???????1427??2008-10-25?12:09??tsp\Ex2\Ex2.vcproj.WWW-00787D97796.Administrator.user

?????文件??????58881??2008-10-23?22:18??tsp\Ex2_1-1.jpg

?????文件??????22787??2008-10-23?22:21??tsp\Ex2_1-2.jpg

?????文件??????55783??2008-10-25?11:57??tsp\Ex2_1-3.jpg

?????文件??????25342??2008-10-25?11:59??tsp\Ex2_1-4.jpg

?????文件?????111323??2008-12-18?14:05??tsp\Ex2_1-5.jpg

............此處省略8個文件信息