本文共 3133 字，大约阅读时间需要 10 分钟。

1.问题描述 

    TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。

2.算法思想

    贪心法求解TSP问题有两种贪心策略。

     1）最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。

    给定初始的城市a，寻找与其邻接的最短距离的城市b，记录二者之间的路径并增加总路径长度；下一次从城市b开始，寻找与b邻接的最短距离的城市,循环查找，直到找到n-1条路径（n为城市个数），最后加上终点回到起点的边即可。

     2）最短链接策略：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。

    首先按照城市之间距离远近进行排列，从距离最近的两个城市开始，如果这两个城市不在一个联通分量中并且度数均小于等于2，那么记录二者之间的路径，将它们划分到一个联通分量并将度数增加1；然后从距离第二小的两个城市开始，重复上述操作直到记录的路径有n-1条，最后找到度数为1的两个城市，作为最后一条路径。

3.参考代码

最近邻点策略：

/*TSP问题采用贪心法的最近邻点策略*//*	TSP问题是指旅行家需要旅行n个城市，要求各个城市经过且仅经过一次，	然后回到出发城市，并且所走的路径最短。*//*	最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，	直到经过了所有的城市，最后回到出发城市*/#include
   
    #include
    
     #include
     
      using namespace std;//类TSPclass TSP{	private:		int city_number;	//城市个数		int **distance;		//城市距离矩阵		int start;		//出发点		int *flag;		//标志数组，判断城市是否加入汉密顿回路		int TSPLength;		//路径长度	public:		TSP(int city_num);	//构造函数		void correct();		//纠正用户输入的城市距离矩阵		void printCity();       //输出用户输入的城市距离		void TSP1();		//贪心法的最近邻点策略求旅行商问题};//构造函数TSP::TSP(int city_num){	int i=0,j=0;	int start_city;	city_number=city_num;	//初始化起点	cout<<"请输入本次运算的城市起点，范围为："<<0<<"-"<
      
       <
       
        >start_city;	start=start_city;	//初始化城市距离矩阵	distance=new int*[city_number];	cout<<"请输入"<
        
         <<"个城市之间的距离"<
         
          >distance[i][j]; } //初始化标志数组 flag=new int[city_number]; for(i=0;i
          
           "<
           
            <
            
             "<
             
              <
              
               >city_number) { TSP tsp(city_number); //初始化 tsp.correct(); //纠正输入的城市距离矩阵 tsp.printCity(); //打印输入的城市 tsp.TSP1(); //求解 cout<<"-------------------------------------------------------"<
              
             
            
           
          
         
        
       
      
     
    
   

最短链接策略：

/*TSP问题采用贪心法的最短链接策略*//*	TSP问题是指旅行家需要旅行n个城市，要求各个城市经过且仅经过一次，	然后回到出发城市，并且所走的路径最短。*//*	最短链接策略：每次在整个图的范围内选择最短的边加入到解集合中，保证解集合中的边最终形成一个哈密尔顿回路*/#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;/*TSP类*/class TSP{	public:        int start_city;		                //起点城市		int end_city;			//终点城市		int distance;			//两者之间的距离			TSP(int sta,int end,int dis);	//构造函数		TSP();				//默认构造函数		void init(int sta,int end,int dis);	//初始化函数		void printfInfo();			//打印信息	};/*函数原型声明*/int cmp(TSP t1,TSP t2);							//定义排序规则int TSP2(TSP *t,int city_num,int cities,TSP *process);  //最短链接求TSPint find(int x,int *pre);						//寻找前置结点void join(int x,int y,int *pre);					//合并结点//构造函数TSP::TSP(int sta,int end,int dis){	start_city=sta;    end_city=end;	distance=dis;}//默认构造函数TSP::TSP(){}//初始化函数void TSP::init(int sta,int end,int dis){    start_city=sta;    end_city=end;	distance=dis;}//打印信息函数void TSP::printfInfo(){	cout<
       
        <<"\t"<
        
         <<"\t"<
         
          <<"\t\n";}//排序规则int cmp(TSP t1,TSP t2){ return t1.distance
          
           >city_number) { int i,j,k=0; for(i=1;i
           
            >distance[i][j]; } } //生成对象数组 for(i=0;i
           
          
         
        
       
      
     
    
   

4.参考结果

最近邻点：

最短链路：

5.补充

    并查集：通过前置结点来判断当前的结点是否属于一个联通分量，不属于则合并两个结点，合并的方法就是将其中一个结点的前置结点设置为另一个结点；当然还可以压缩路径，计算过程中记录结点的根结点，这样就不用依次向上遍历了。

    关于sort(),sort并不是简单的快速排序，它对普通的快速排序进行了优化，此外，它还结合了插入排序和推排序。系统会根据数据形式和数据量自动选择合适的排序方法，这并不是说每次排序只选择一种方法，是在一次完整排序中不同的情况选用不同方法，比如给一个数据量较大的数组排序，开始采用快速排序，分段递归，分段之后每一段的数据量达到一个较小值后它就不继续往下递归，而是选择插入排序，如果递归的太深，会选择推排序。