旅行商问题

Posted by qingdujun on 2019-07-19

旅行商问题又叫做Traveling Salesman Problem,是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。

本文主要参考了JeoKwok、Jerkwin和mztkenan的相关内容,详情见文末。

定义

假设现在有4个城市0,1,2,3。他们之间的代价如下图,可以存成二维表的形式,现在要从城市0出发,最后又回到0,期间1,2,3都必须并且只能经过一次,使代价最小。

tsp

  • 我们要求的最终结果是dp(0,{1,2,3})。它表示从城市0开始,经过{1,2,3}之中的城市并且只有一次,求出最短路径。
  • dp(0,{1,2,3})是不能一下子求出来的,那么他的值是怎么得出的呢?看树形图的第二层,第二层表明了dp(0,{1,2,3})所需依赖的值。那么得出,
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    dp(0,{1,2,3})=min{
    city_dis[0][1]+dp(1,{2,3})
    city_dis[0][2]+dp{2,{1,3})
    city_dis[0][3]+dp{3,{1,2})
    }

    ...

    dp(1,{2,3})=min{
    city_dis[1][2]+dp(2,{3})
    city_dis[1][3]+dp{3,{2})
    }

tsp

动态规划公式

其中的 dp(i,{j,k,l}) 表示由城市 i 出发, 集合 {j,k,l} 中的城市 j,k,l 每个经过一次需要的最小路程, 箭头上的值表示两个城市之间的距离。

\begin{equation} \nonumber
dp[i, u] =
\begin{cases}
city_dis[i][0] & u = {} \
\underset{k \in u}{min}{city_dis[i][k]+dp[k][u-2^{k-1}} & u != \emptyset
\end{cases}
\end{equation}

  • dp数组的大小为$dp[size][2^{size-1}]$。
  • 判断城市k是否属于集合u(二进制表示)的方法是使用二进制与操作, 若$0 == u \& 2^{k-1}$,则不存在。
  • 注意,$2^{k-1}$在编程时,相当于对数字0x01左移k-1位。即,$2^{k-1} == 1 << (k-1)$。
  • $u-2^{k-1}$表示集合u中移除k之后的数字,比如{1,2}=011=3,如果移除k=1的话,应该为010也就是$3-2^{1-1}=010$。
    dp2

为了方便求解并记录路径, 可以使用二进制数表示城市集合。一个n位的二进制数可以表示n个城市的集合。当某位为1时, 表示这个位所代表的城市出现在集合中。

  • 例子中最多有3个城市需要经历, 所以需要 $2^3=8$ 个集合。每个集合对应的数字如下,
    bin

算法实现

以下dp表,从左往右,按列开始填充。
https://github.com/qingdujun/algorithm/blob/master/tsp.cpp

  • for循环u负责列(它是一个集合);
  • for循环i负责行(看上面的树形图,每一层相当于一行);
  • for循环k负责选择(动态规划,选择某一层中最小的那个)。

这个例子的最终结果为10。

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
46
47
48
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int tsp(vector<vector<int>>& city_dis) {
if (city_dis.empty()) {
return 0;
}

int size = city_dis.size();
vector<vector<int>> dp(size, vector<int>(pow(2, size-1), 0));
for (int i = 0; i < size; ++i) {
dp[i][0] = city_dis[i][0]; //initialize the first column
}

for (int u = 1; u < dp[0].size(); ++u) {
for (int i = 0; i < dp.size(); ++i) {
if (0 == ((1<<(i-1)) & u)) {
int min_dis = INT32_MAX;
for (int k = 1; k < size; ++k) {
if (0 != ((1<<(k-1)) & u)) {
int temp = city_dis[i][k] + dp[k][u - (1<<(k-1))];
if (temp < min_dis) {
min_dis = temp;
}
}
}
dp[i][u] = min_dis;
}
}
}

return dp[0].back();
}

int main(int argc, char const *argv[]) {
vector<vector<int>> city_dis = {
{0, 3, 6, 7},
{5, 0, 2, 3},
{6, 4, 0, 2},
{3, 7, 5, 0}};

int min_dis = tsp(city_dis);
cout << min_dis << endl;

return 0;
}

References:
[1] JeoKwok,TSP(旅行者问题)——动态规划详解
[2] Jerkwin,旅行推销商问题TSP的动态规划解法
[3] mztkenan,动态规划解决TSP问题