旅行商问题的解法探究
在算法与设计分析这门课的 lab1
中，引入了一道较为常见的旅行商问题（Travel Saleman
Problem），这是一个著名的组合优化类的问题。这里我将使用三种方法解决该问题
推销员问题（简化版）
题目背景
市有一推销员，欲到个城市（编号）推销产品。为了节省旅行费用，在出发前他查清了任意两个城市间的旅行费用，想找到一条旅行路线，仅经过每个城市一次，且使旅行费用最少。
注意，推销员初始位置为号城市，即号城市已经访问过，访问过程中和结束后无需重新返回号城市。
题目描述
已知：
城市数量
以对称矩阵表示的城市间距离。其中为城市到城市的距离。，表示两个城市间无直接通路。。
题目保证至少有一条路径满足题意。
输入格式
第行为，以结尾
第行至第行每行个正整数或，每个数以空格隔开，每行结尾为
输出格式
一个数字，表示满足题意的最短路径，以结尾
样例 #1
样例输入 #1
1
2
3
4
5
6
| 5
0 3 6 -1 1
3 0 2 -1 4
6 2 0 2 3
-1 -1 2 0 1
1 4 3 1 0
|
样例输出 #1
提示
保证输入和结果在位范围内
该问题的起源最早可以追溯到一个要到访 45
个德国城市的的旅行商人的自我思考
之后哈佛大学的 Karl Mengerz 在 1930
年也研究了这一问题，这位教授想要找到一个最优的策略完成他的环美徒步。
路径是天文学家哈密顿(William
Rowan Hamilton) 提出，数学定义如下
给定一个图 ,
是否存在一条路线，从一个起点出发，走过每个顶点且只走过一次。
一些初始说明
这个问题可能在多项式时间内被解决吗？
在离散数学中，问题可以认为是已经解决的问题，这个解决的定义是可以做多项式的时间复杂度内解决。所谓的多项式，也就是
，这里的是一个常数。与多项式相反的函数有很多，比如指数函数、阶乘等等。
在
问题的基础上，还有一种更为困难的问题，我们称为问题，这类问题是不能在多项式时间内解决的，但是
问题的准确定义，应为能够在多项式时间内完成解的正确性验证，如果不能完成这样的验证，那我们称它为
刚才提到的旅行商问题就是一个问题，因为即使我们给定了一个解，我们也没有办法快速判断给定的解是否正确，必须要遍历完所有的情况才可以。我们验证的复杂度就已经超出了多项式的范畴，所以它不属于
NP 问题，比 NP 问题更加困难，所以是一个问题。总体上的难度如下：
旅行商问题和回路都被证明了是难的问题，即不能在多项式事件内被解决。
证明可参考 reference 2
其中提到旅行商问题是回路的一种退化？？
解决方法 Ⅰ 枚举
假如说我们直接暴力枚举所有的路径的话，复杂度是在 级别 对于
的数据范围，第一个点一定在 0，总的能够决定的去向只有 9
个。可能性一共有 种，即
3628800，实际上也能够通过本题了。
所以最简单的思路就是枚举所有的可能，并计算其中最小的一条路径。
下面是两种 dfs 的实现思路
第一种方法我们可以计算出结果的全排列，这样结果就唯一确定了，对于计算全排列，可以采用深度优先搜索，或者是
c++中的库函数next_permutation完成，使用这一方法解决的优点在于代码较短，且容易理解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define int long long
using namespace std;
int w[11][11];
int n, way = 1e9;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int x;
cin >> x;
w[i][j] = (x == -1 ? 1e8 : x);
}
vector<int> v(n);
iota(v.begin(),v.end(),0);
int cost = 1e9;
while(next_permutation(v.begin() + 1, v.end())){
int temp_cost = 0;
for (int i = 0; i < n - 1; i ++)
temp_cost += w[v[i]][v[i + 1]];
cost = min(temp_cost, cost);
}
cout << cost << endl;
return 0;
}
|
结果错了一个点，我觉得应该是因为一上来 while 里面就进行了一次
next_permutaion() 所以没有了最开始的 1，2，3，4 ... 8 这个全排列
改成这样也许可行，可惜现在评测已经关闭，我也没有办法验证我的想法了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int w[11][11];
int n, way = 0x3f3f3f3f;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int x;
cin >> x;
w[i][j] = (x == -1 ? 1e9 : x);
}
iota(v.begin(),v.end(),0);
int cost = 1e9;
while(1){
int temp_cost = 0;
for (int i = 0; i < n - 1; i ++)
temp_cost += w[v[i]][v[i + 1]];
cost = min(temp_cost, cost);
if(next_permutation(v.begin() + 1, v.end()))
continue;
else
break;
}
cout << cost << endl;
return 0;
}
|
在过程中，我们采用 state
对枚举的状态进行定义，使用状态压缩的方式进行记录，以达到简化代码的目的
首先我们引入二进制表达状态(即状态压缩)的方法。
我们在计算机当中，所有数据都是以二进制的形式存储的。一般一个 int
整形是 4 个字节，也就是 32 位 bit，我们通过这 32 位 bit 上 0 和 1
的组合可以表示多大 21 亿个不同的数。如果我们把这 32 位 bit
看成是一个集合，则每一个数都应该对应集合的一种状态，并且每个数的状态都可以是不同的。
由于题目中所给的结点状态仅有访问过和未访问过这两种，那么如果我们将访问过用
1 表示，没访问过用 0
来表示，这样我们就能够用一个数来表示出所有数的访问状态，这就是状压的思想！
这样子，实际上对于一个 int 类型的数，我们可以用这个数记录 32
个位置上的值，因此最多可以获得 32 个数的状态（虽然本题中只需要 10
个数就可以了）。
表示完状态后，为了能够快速的进行状态的访问，我们可以使用位运算使代码更加简洁。
state >> j & 1
这个值即可代表在该位置上的节点是否已经访问过，在表达是之前加 表示没访问过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <iostream>
#include <vector>
using namespace std;
int w[11][11];
int n, way = 0x3f3f3f3f;
bool vis[45];
void dfs(int i, int num, int state, int road)
{
if (road > way)
return;
if (num == n)
{
if (road < way)
way = road;
return;
}
for (int j = 0; j < n; j++)
{
if (!(state >> j & 1))
{
road += w[i][j];
dfs(j, num + 1, state + (1 << j), road);
road -= w[i][j];
}
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int x;
cin >> x;
w[i][j] = (x == -1 ? 1e9 : x);
}
dfs(0, 1, 1, 0);
cout << way << endl;
return 0;
}
|
测试结果如图：
解决方法 Ⅱ
状态压缩的动态规划
对于这样一个
的问题，我们如果考虑优化，可以从动态规划的角度进行思考
由于前面提到了状态压缩，因此这里我们可以引入状态压缩的 dp
来解决这一问题。
状态压缩的动态规划是竞赛中常见的一种题目，可以将复杂度降低很多，对于
的情况都能求解
状态表示： => 当前访问点的状态是
(二进制下), 最后停留在 点上
实际上，动态规划的核心在于用一个简洁的方式表达出来当前的结果，之后再进行状态的转移。
我们可以首先思考一下之前计算过程缓慢的原因，再从中找到优化的思路
在计算的过程中，有部分的状态比较相似，例如有两条路都是从
0->2->3->4 往后计算的，前面这些相同的路
径所需要的花费是一致的，并不需要多次计算。
但由于我们暴力枚举了所有的结果，所以进行了不必要的重复的计算，如果我们能够将这部分相似的结果利用起来，不就达到了优化的目的吗？下面我给出一个状态计算的方法
状态计算：
从没访问过 点变为访问过
点，从有没有访问过的状态转移至访问过的状态，即可实现优化
复杂度： 遍历了所有的节点两轮 ，访问所有状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <iostream>
#include <vector>
#include <cstring>
#define int long long
using namespace std;
const int N = 11, M = 1 << N;
int n;
int w[N][N];
int f[M][N];
signed main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
{
int x;
cin >> x;
w[i][j] = (x == -1 ? 1e9 : x);
}
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for (int state = 1; state < 1 << n; state ++ )
if(state & 1)
for (int j = 0; j < n; j ++ )
if(state >> j & 1)
for (int k = 0; k < n; k ++ )
if(state >> k & 1)
f[state][j] = min(f[state][j], f[state - (1 << j)][k] + w[k][j]);
int mn = 1e9;
for(int i = 0; i < n; i ++)
mn = min(mn, f[(1<<n) - 1][i]);
cout << mn;
return 0;
}
|
测试结果如图
扩展思考 假设问题的规模进一步扩大了呢？
在实际的生活中，我们可能会遇到一些 n
较大的情况，那对于这种算法，传统的算法理论求解精确解可能比较有难度，复杂度较高。但是，在生活中，我们可能不需要获得如此准确的结果，获取到一个较优的可行解可能就能够满足我们的生活需要了。这里我引入了蚁群算法来解决这一类
n 较大的问题
蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法：蚂蚁在运动过程中，能够在它所经过的路径上留下信息素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向。蚁群算法就是模拟这一过程来实现优化。
求解 TSP
问题的蚁群算法中的人工蚂蚁具有以下特点：
1）他们概率性地选择下一条路径，该概率与路径长度和路径上的信息素浓度有关；
2）为了保证解的逻辑可行，蚂蚁不允许选择已经走过的路径（通过禁忌表实现）；
3）蚂蚁走过一条路径时会在该路径上面分泌一种叫做信息素的物质。
时间有限，蚁群算法的做法待补 😭
可以使用蚁群算法来较快的算出一个可行解，虽然可能无法通过洛谷的测试，但是应当是对实际生活更为有帮助的一种解决办法。
参考文件
