文章目录

• 一、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 为边集，各顶点间距离为 C_ij，已知（C_ij > 0，C_ij = +∞，i，j ∈ V），并设
x   i j   = { 1 ， 边 ( i , j ) 在 最 优 路 线 上 0 ， 其 他 x~ij~= \begin{cases} 1，边(i, j)在最优路线上 \\ 0，其他 \end{cases} x ij ={1，边(i,j)在最优路线上0，其他​
则旅行商问题的数学模型可写成如下的线性规划形式：
p = ∑ i ≠ j c i j x i j p = \sum_{i ≠ j} c_{ij}x_{ij} p=i​=j∑​cij​xij​
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分类

旅行商问题按把不同的分类方法可以分为不同的种类，这里只介绍距离矩阵划分： 当 c_ij = c_ji，(i, j ∈ V)时，问题被称为对称型旅行商问题，反之称为非对称型旅行商问题，非对称旅行商问题可以化为对称型旅行商问题，用对称型的方法求解。当对所有的 i, j, k ∈[1, n]，有不等式 c_ij + c_jk ≥ c_ik，问题满足三角形不等式的，也称三角型旅行商问题。
旅行售货商问题(TSP)是组合优化领域的经典问题之一,而其中考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展，多种扩展形式¹如下：

1. 最小哈密顿链的问题：起点和终点不同；
2. 非对称旅行商问题（asymmetric TSP）：距离矩阵非对称的旅行商问题；
3. 多人旅行商问题（muti-person TSP）：由多人完成旅行的旅行商问题；
4. 多目标旅行商问题（multi-objective TSP）；
5. 依次排序问题（Sequence ordering problem ，SOP）：这类问题是非对称旅行商问题，在给定一系列顶点和距离矩阵下，寻找最短从顶点 1 到顶点 n 哈密顿链，同时满足限制：某些顶点要在一些顶点之前被连接。
6. 载货量受限制的车辆路径问题（Capacitated vehicle routing problem，CVRP）：给定 n-1 个顶点和一个仓库，一直顶点和顶点、仓库和顶点的距离，卡车载货量受限制，卡车每次在部分顶点和仓库之间往返，寻求一条经过所有顶点的最短路线。

二、贪心算法

贪心算法，又名贪婪算法，是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择，它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择，并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

1. 算法思路

贪心算法以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。

贪心算法求解具有以下性质²：

1. 贪心选择性质：一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解
2. 最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。

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;

具体代码如下：

#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];


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;
}


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 问题。