文章目录
 
一、TSP 概述
1. TSP
2. 数学模型
3. TSP分类
  
二、贪心算法
1. 算法思路
2. 算法框架
3. 问题
  
三、贪心算法求解 TSP

 
 
一、TSP 概述
 
1. TSP
 
旅行商问题即 TSP（Traveling Salesman Problem），又称为货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
 TSP问题是一个组合优化问题，该问题可以被证明具有NPC计算复杂性。从图论的角度来看，该问题实质是给定一个带权完全无向图（顶点表示城市，边表示道路，权重是道路的成本或距离），找一个权值最小的 Hamilton 回路。
 
2. 数学模型
 
记 G = (V, E) 为赋权图，V = {1， 2 ， ……，n} 为顶点集，E 为边集，各顶点间距离为 Cij，已知（Cij > 0，Cij = +∞，i，j ∈ V），并设
 $$xij=\{\begin{array}{l}1，边(i,j)在最优路线上\\ 0，其他\end{array}$$
 则旅行商问题的数学模型可写成如下的线性规划形式：
 $$p=\sum _{i\ne j}{c}_{ij}{x}_{ij}$$
 
     
      
       
        
         s
        
        
         .
        
        
         t
        
        
         .
        
        
         =
        
        
         
          {
         
         
          
           
            
             
              
               
                ∑
               
               
                
                 j
                
                
                 ≠
                
                
                 i
                
               
              
              
               
                c
               
               
                
                 i
                
                
                 j
                
               
              
              
               =
              
              
               1
              
              
               ,
              
             
            
           
           
            
             
              
               i
              
              
               ∈
              
              
               V
              
             
            
           
          
          
           
            
             
              
               
                ∑
               
               
                
                 i
                
                
                 ≠
                
                
                 j
                
               
              
              
               
                c
               
               
                
                 i
                
                
                 j
                
               
              
              
               =
              
              
               1
              
              
               ,
              
             
            
           
           
            
             
              
               j
              
              
               ∈
              
              
               V
              
             
            
           
          
          
           
            
             
              
               
                ∑
               
               
                
                 i
                
                
                 ,
                
                
                 j
                
                
                 ∈
                
                
                 S
                
               
              
              
               
                x
               
               
                
                 i
                
                
                 j
                
               
              
              
               ≤
              
              
               ∣
              
              
               K
              
              
               ∣
              
              
               −
              
              
               1
              
              
               ,
              
             
            
           
           
            
             
              
               K
              
              
               ⊂
              
              
               V
              
             
            
           
          
          
           
            
             
              
               
                x
               
               
                
                 i
                
                
                 j
                
               
              
              
               ∈
              
              
               {
              
              
               0
              
              
               ,
              
              
               1
              
              
               }
              
             
            
           
           
            
             
              
               i
              
              
               ,
              
              
               j
              
              
               ∈
              
              
               V
              
             
            
           
          
         
        
       
       
         s.t.=\begin{cases} \sum_{j ≠ i} c_{ij} = 1 ,& i∈V \\ \sum_{i ≠ j} c_{ij} = 1 ,& j∈V \\ \sum_{i,j∈S} x_{ij} ≤|K|-1 ,& K ⊂V \\ x_{ij}∈\{0, 1\} & i,j∈V\\ \end{cases}
       
      
     s.t.=⎩⎪⎪⎪⎨⎪⎪⎪⎧​∑j​=i​cij​=1,∑i​=j​cij​=1,∑i,j∈S​xij​≤∣K∣−1,xij​∈{0,1}​i∈Vj∈VK⊂Vi,j∈V​
 K 为 V 的所有非空子集，|K| 为集合 K 中所含图 G 的顶点个数。前两个余数意味着对每个顶点而言，出度和入度都为1，后一约束则保证没有任何子回路解的产生，于是满足上述约束的解构成了一条 Hamilton 回路。
 
3. TSP分类
 
旅行商问题按把不同的分类方法可以分为不同的种类，这里只介绍距离矩阵划分： 当 cij = cji，(i, j ∈ V)时，问题被称为对称型旅行商问题，反之称为非对称型旅行商问题，非对称旅行商问题可以化为对称型旅行商问题，用对称型的方法求解。当对所有的 i, j, k ∈[1, n]，有不等式 cij + cjk ≥ cik，问题满足三角形不等式的，也称三角型旅行商问题。
 旅行售货商问题(TSP)是组合优化领域的经典问题之一,而其中考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展，多种扩展形式如下：
 
最小哈密顿链的问题：起点和终点不同；
非对称旅行商问题（asymmetric TSP）：距离矩阵非对称的旅行商问题；
多人旅行商问题（muti-person TSP）：由多人完成旅行的旅行商问题；
多目标旅行商问题（multi-objective TSP）；
依次排序问题（Sequence ordering problem ，SOP）：这类问题是非对称旅行商问题，在给定一系列顶点和距离矩阵下，寻找最短从顶点 1 到顶点 n 哈密顿链，同时满足限制：某些顶点要在一些顶点之前被连接。
载货量受限制的车辆路径问题（Capacitated vehicle routing problem，CVRP）：给定 n-1 个顶点和一个仓库，一直顶点和顶点、仓库和顶点的距离，卡车载货量受限制，卡车每次在部分顶点和仓库之间往返，寻求一条经过所有顶点的最短路线。
 
二、贪心算法
 
贪心算法，又名贪婪算法，是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择，它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择，并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
 
1. 算法思路
 
贪心算法以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。
 
 贪心算法求解具有以下性质：
 
贪心选择性质：一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解
最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。
 
2. 算法框架
 
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，而贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
 
//问题随机初始解
while(能向总目标前进一步)
{
	//利用可行的决策，从候选集合中求出可行解的一个解元素；
}
 
3. 问题
 
贪心算法也存在如下问题：
 
不能保证求得的最后解是最佳的；
不能用来求最大最小解问题；
只能在某些特定条件约束的情况下使用，例如贪心策略必须具备无后效性等。
 
三、贪心算法求解 TSP
 
贪心策略基本思路：从一节点出发遍历所有能到达的下一节点，选择距离最近的节点作为下一节点，然后把当前节点标记已走过，下一节点作为当前节点，重复贪心策略，以此类推直至所有节点都标记为已走节点结束。
 TSP 数据集来自于 TSPLIB 上的 att48.tsp，这是一个对称 TSP 问题，城市规模为48，其最优值为10628。其距离计算方法如下：
 
 
 
The edge weight type ATT corresponds to a special “pseudo-Euclidean” distance function. Let x[ i ] and y[ i ] be the coordinates of node i. The distance between two points i and j is computed as follows:
 double dis = sqrt((pow((double)x[i] - x[j], 2) / 10 + pow((double)y[i] - y[j], 2) / 10 ));
 int disInt = (int)dis;
 if(disInt < dis) dis = disInt + 1;
 else dis = disInt;
 
 
具体代码如下：
 
/*********************************************************************************************************************
 * TSP 算例来自TSPLIB，att48.tsp 数据集，其中有 48 个城市，距离为伪欧式距离
 * TSPLIB is a library of sample instances for the TSP (and related problems)from various sources and of various types.
 * 目前最佳解总距离为 10628，其中距离的计算方式为 sqrt((x*x + y*y)/10)
 * 使用贪心策略求解，解集总距离为 12861，可见贪心策略只是局部最优解
**********************************************************************************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

// 城市数量 N
#define N 48
// 城市距离矩阵
int distance[N][N];

/***********************************************************************
 * Function   ：init()
 * Description：从文件中读取城市坐标，并计算城市之间的距离 distance[N][N] 
 * Input      ：void
 * Output     ：void
 * Return     ：void
 ***********************************************************************/
void init()
{
	//城市的 x 和 y 坐标
	int x[N] = { 0 };
	int y[N] = { 0 };
	//从 data.txt 文件读取数据
	FILE* fp;
	if ((fp = fopen("..//att48.txt", "r")) == NULL)
		//if ((fp = fopen("..//kroB100.txt", "r")) == NULL)
	{
		printf("can not open the file!");
		exit(0);
	}
	while (!feof(fp))
	{
		int count;
		fscanf(fp, "%d", &count);
		fscanf(fp, "%d%d", &x[count - 1], &y[count - 1]);
	}
	fclose(fp);
	//计算城市之间距离
	for (int i = 0; i < N - 1; i++)
	{
		distance[i][i] = 0;				// 对角线为0
		for (int j = i + 1; j < N; j++)
		{
			double dis = sqrt((pow((double)x[i] - x[j], 2) / 10 + pow((double)y[i] - y[j], 2) / 10));
			int disInt = (int)dis;
			distance[i][j] = dis == disInt ? disInt : disInt + 1;
			distance[j][i] = distance[i][j];
		}
	}
	distance[N - 1][N - 1] = 0;
}

/***********************************************************************
 * Function   ：TSPGreedyAlgorithm()
 * Description：贪心策略求解 TSP 问题
 * Input      ：void
 * Output     ：TSP 路径和对应的总距离
 * Return     ：void
 ***********************************************************************/
void TSPGreedyAlgorithm()
{
	//总路程
	int totalDistance = 0;		
	//默认从 0 开始遍历
	int current = 0;	
	//标识城市是否被访问,访问过置为 1
	bool visit[N] = { false };
	visit[0] = 1;
	printf("TSP 路径为：%d ->", 1);

	//遍历 N - 1 次
	for (int i = 1; i < N; i++)
	{
		//设置较大的距离初始值用来选取最近邻
		int min_distance = 0x7fffffff;
		//保存当前最近邻城市
		int temp;
		//循环选取城市
		for (int j = 1; j < N; j++)
		{
			if (!visit[j] && distance[current][j] < min_distance)
			{
				min_distance = distance[current][j];
				temp = j;
			}
		}
		visit[temp] = 1;
		current = temp;
		totalDistance += min_distance;
		printf(" %d ->", temp + 1);
	}
	totalDistance += distance[current][0];
	printf(" %d\n", 1);
	printf("TSP 总距离为：%d\n", totalDistance);
}

int main()
{
	init();
	TSPGreedyAlgorithm();
	return 0;
}
 
结果如下：
 
 可见，贪心算法求解 TSP 问题只能得到局部最优解，如果需要得到最优解，需要采用局部搜索算法等非精确性算法，作者将在后文中继续介绍其他方法求解 TSP 问题。
 
 
 
 
The multiple traveling salesman problem: an overview of formulations and solution procedures. ↩︎
 
计算机算法设计与分析研究,新华出版社,2015.09. ↩︎
 
计算机算法基础,西南交通大学出版社,2015.02. ↩︎
 
 

 
  TSP_旅行商问题 - 贪心算法
 
 
TSP_旅行商问题-贪心算法
TSP_旅行商问题-模拟退火算法
TSP_旅行商问题-遗传算法
TSP_旅行商问题-基本蚁群算法
 
问题描述
 
寻找最短路径使得其经过所有城市 
 测试数据集：tsp.eil51问题
 
1 37 52
2 49 49
3 52 64
4 20 26
5 40 30
6 21 47
7 17 63
8 31 62
9 52 33
10 51 21
11 42 41
12 31 32
13 5 25
14 12 42
15 36 16
16 52 41
17 27 23
18 17 33
19 13 13
20 57 58
21 62 42
22 42 57
23 16 57
24 8 52
25 7 38
26 27 68
27 30 48
28 43 67
29 58 48
30 58 27
31 37 69
32 38 46
33 46 10
34 61 33
35 62 63
36 63 69
37 32 22
38 45 35
39 59 15
40 5 6
41 10 17
42 21 10
43 5 64
44 30 15
45 39 10
46 32 39
47 25 32
48 25 55
49 48 28
50 56 37
51 30 40
 
最优解：426
 
算法思想
 
选择下一城市的策略为 
 距当前城市最近且未被访问过的城市
 
算法流程
 
 
 
准备工作（初始化）
 
 
a、读取数据，txt内数据格式为：序号 $x_i$ $y_i$ 
 b、设置城市数量N、城市坐标数组citys[num] 
 c、计算城市距离矩阵，$dic[i][j]$为第i个城市到第j个城市的距离
 
 
 
开始模拟算法流程 
 seq[num]记录路径， 
 visit[num]标记是否已访问，
 
 
a、初始化visit数组为false未访问； 
 b、随机选择起点城市，记录路径，标记visit[seq[0]]为true已访问；
 
 
 
进入循环体 
 循环N-1次
 
 
a、遍历所有城市，寻找未访问且与上一城市seq[i-1]距离最近的城市mini； 
 b、记录路径，标记visit[mini]为true已访问；
 
 
 
结束循环
 
 
计算路径能量值
 
测试结果
 
当前结果 
  
 最优结果 
 
 
算法代码
 
#include<iostream>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;
const int num = 1000;//city number
const int width = 100;
const int height = 100;

typedef struct node {
    int x;
    int y;
}city;
city citys[num];//citys
double dic[num][num];//distance from two citys;
bool visit[num];//visited
int N;//real citys
int seq[num];//
double answer;
void init() {//set N&&x-y设置N和citys[num]
    N = 51;
    citys[0].x = 37; citys[0].y = 52;
    citys[1].x = 49; citys[1].y = 49;
    citys[2].x = 52; citys[2].y = 64;
    citys[3].x = 20; citys[3].y = 26;
    citys[4].x = 40; citys[4].y = 30;
    citys[5].x = 21; citys[5].y = 47;
    citys[6].x = 17; citys[6].y = 63;
    citys[7].x = 31; citys[7].y = 62;
    citys[8].x = 52; citys[8].y = 33;
    citys[9].x = 51; citys[9].y = 21;
    citys[10].x = 42; citys[10].y = 41;
    citys[11].x = 31; citys[11].y = 32;
    citys[12].x = 5; citys[12].y = 25;
    citys[13].x = 12; citys[13].y = 42;
    citys[14].x = 36; citys[14].y = 16;
    citys[15].x = 52; citys[15].y = 41;
    citys[16].x = 27; citys[16].y = 23;
    citys[17].x = 17; citys[17].y = 33;
    citys[18].x = 13; citys[18].y = 13;
    citys[19].x = 57; citys[19].y = 58;
    citys[20].x = 62; citys[20].y = 42;
    citys[21].x = 42; citys[21].y = 57;
    citys[22].x = 16; citys[22].y = 57;
    citys[23].x = 8; citys[23].y = 52;
    citys[24].x = 7; citys[24].y = 38;
    citys[25].x = 27; citys[25].y = 68;
    citys[26].x = 30; citys[26].y = 48;
    citys[27].x = 43; citys[27].y = 67;
    citys[28].x = 58; citys[28].y = 48;
    citys[29].x = 58; citys[29].y = 27;
    citys[30].x = 37; citys[30].y = 69;
    citys[31].x = 38; citys[31].y = 46;
    citys[32].x = 46; citys[32].y = 10;
    citys[33].x = 61; citys[33].y = 33;
    citys[34].x = 62; citys[34].y = 63;
    citys[35].x = 63; citys[35].y = 69;
    citys[36].x = 32; citys[36].y = 22;
    citys[37].x = 45; citys[37].y = 35;
    citys[38].x = 59; citys[38].y = 15;
    citys[39].x = 5; citys[39].y = 6;
    citys[40].x = 10; citys[40].y = 17;
    citys[41].x = 21; citys[41].y = 10;
    citys[42].x = 5; citys[42].y = 64;
    citys[43].x = 30; citys[43].y = 15;
    citys[44].x = 39; citys[44].y = 10;
    citys[45].x = 32; citys[45].y = 39;
    citys[46].x = 25; citys[46].y = 32;
    citys[47].x = 25; citys[47].y = 55;
    citys[48].x = 48; citys[48].y = 28;
    citys[49].x = 56; citys[49].y = 37;
    citys[50].x = 30; citys[50].y = 40;
}
void set_dic() {//set distance
    for (int i = 0; i<N; ++i) {
        for (int j = 0; j<N; ++j) {
            dic[i][j] = sqrt(pow(citys[i].x - citys[j].x, 2) + pow(citys[i].y - citys[j].y, 2));
        }
    }
}
double dic_two_point(city a, city b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double count_energy(int* conf) {
    double temp = 0;
    for(int i = 1; i<N; ++i){
    temp += dic_two_point(citys[conf[i]], citys[conf[i - 1]]);
    }
    temp += dic_two_point(citys[conf[0]], citys[conf[N - 1]]);
    return temp;
}
void moni() {
    memset(visit, false, sizeof(visit));
    int temp = rand() % N;
    seq[0] = temp;
    visit[temp] = true;
    int mini = -1;
    int ans = 1e9;
    for (int i = 1; i < N; ++i) {//第i位应该经过的点
        ans = 1e9;
        mini = -1;
        for (int j = 0; j < N; ++j) {
            if (!visit[j] && ans > dic[seq[i - 1]][j]) {
                ans = dic[seq[i - 1]][j];
                mini = j;
            }
        }
        seq[i] = mini;
        visit[mini] = true;
    }
    answer=count_energy(seq);
}
void test() {//读取数据，设置N和citys[num]
    ifstream ifile("data.txt");
    if (!ifile) {
        cout << "open field\n";
        return;
    }
    while(!ifile.eof()){
        int te = 0;
        ifile >> te;
        ifile >> citys[te - 1].x >> citys[te - 1].y;
        N = te;
    }
}
void output() {
    cout << "the best road is : \n";
    for (int i = 0; i < N; ++i) {
        cout << seq[i];
        if (i == N - 1)
            cout << endl;
        else
            cout << " -> ";
    }
    cout << "the length of the road is " << answer << endl;
}
int main(){
    srand(time(nullptr));
    int t;
    while (cin >> t) {//仅作为重启算法开关使用，无意义
        init();//使用程序内置数据使用init()函数，
        //test();//使用文件读取数据使用test()函数，
        set_dic();
        moni();
        output();
    }
    return 0;
}

贪心算法之TSP问题
 
贪心算法
 贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 所以不能保证最后结果是最优解,一般是最优解的近似解，但是贪心算法的效率高。
 
问题描述
 旅行商问题（TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的城市（不可重复）之后，最后再回到原点的最小路径成本。
 
贪心策略
 1.从某一个城市开始，每次选择一个城市，直到所有的城市被走完。
 2.每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最小。通过该算法求得的解并不一定是最优的，只是最优解的近似解。传统的贪心算法虽然能求得最优解，但是时间空间性能太差，所以一般采用改良的贪心算法。
 
应用领域
 
1、如何规划最合理高效的道路交通，以减少拥堵；
 
2、如何更好地规划物流，以减少运营成本；
 
3、在互联网环境中如何更好地设置节点，以更好地让信息流动等。
 
代码实现
 
#include<iostream>
#define n 4
using namespace std;
int s[n] = {-1,-1,-1,-1} ;// 记录已经访问过的城市, 初始化为-1,表示未访问
int distance[n][n] = {{10000,3,6,5},// 城市间距离数组,10000表示自己到自己的距离
                      {3,10000,5,4},
                      {6,5,10000,2},
                      {5,4,2,10000}};
                                  
bool visit(int k) {//判断城市k是否被访问过 
    for (int i = 0; i < n ; i++) 
        if (s[i] == k) return 1 ;
        	return 0;
}

void clostCityDistance(int currentCity) { //查找距离当前城市最近的下一个城市       
	int Dtemp = 10000;//Dtemp暂时存储当前最小路径的值 
    for (int i = 0; i < n; i++) 
	{        
        if ( visit(i) == 0 && ::distance[i][s[currentCity]] <Dtemp ) 
		{
            Dtemp = ::distance[i][s[currentCity]] ;
            s[currentCity+1] = i ;//若该城市没有被访问过，且距离当前城市最短，则将访问该城市，存入s[]数组中 
        }
   }
        
for (int i = 0; i < n; i++) 
{//查找是否还有未访问的城市 
    if ( s[i] == -1 )              
        clostCityDistance(s[currentCity+1]);         
    }
} 
void TSP() {
int sum = 0 ;// 最短路径之和 
s[0] = 2;//从第2个城市出发 ，初始化出发的城市,可在0,1,2,3中任意一个 
clostCityDistance(s[0]) ;//寻找距离2城市最近的城市   
    for (int i=0; i < n ; i++) {            
        if (i == n -1) {
            printf("%d",s[i] );
            printf("->%d 距离为：%d\n",s[0],::distance [ s[n-1] ] [s[0]]);
            printf("总距离是  %d\n",sum += ::distance [ s[n-1] ] [s[0]] );
            break ;
        }
            
            printf("%d->%d 距离为：%d \n",s[i],s[i+1], ::distance[ s[i] ][ s[i+1] ]  );
            sum += ::distance[ s[i] ][ s[i+1] ] ;
        }
     
    }

int main() {    
    TSP() ;
    return 0;
}
 
运行结果
 

TSP_旅行商问题 - 贪心算法
 
问题描述:
 
 
 
代码：1.