最小生成树解决tsp问题

用最小生成树解决TSP问题 非常有用 输入各个城市坐标 可以输出路径

# 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个文件信息