旅行商问题

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

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

定义

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

  • 我们要求的最终结果是dp(0,{1,2,3})。它表示从城市0开始,经过{1,2,3}之中的城市并且只有一次,求出最短路径。
  • dp(0,{1,2,3})是不能一下子求出来的,那么他的值是怎么得出的呢?看树形图的第二层,第二层表明了dp(0,{1,2,3})所需依赖的值。那么得出,
    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})
    }

动态规划公式

其中的 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\)

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

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

算法实现

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

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

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

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