字节跳动2019春招 - 旅行商问题

题目描述

小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

输入描述:

城市个数n（1<n≤20，包括北京）
城市间的车票价钱 n行n列的矩阵 m[n][n]

输出描述:

最小车费花销 s

输入例子1:

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

输出例子1:

13

当时的想法

经典的旅行商问题，在《人工智障——一种现代的方法》里看到过，说了这是个NP难问题，可惜当时没有深究这个问题到底怎么实现。旅行商问题可以通过遗传算法等算法获得一个较优的解，但是如果要求最优解，则只能暴力计算，但是TSP（Traveling Salesman Problem）怎么暴力计算也是有讲究的。
一开始想，反正说了这是NP难，那就只能指数复杂度，上来直接dfs就是超时，然后就直接蒙蔽了。

算法分析

暴力dfs超时的原因依然是重复计算了很多地方。譬如总共有6个城市，从城市<0>出发，<0-1-2-3>和<0-2-1-3>两条路径，它们的后续搜索过程是完全相同的。解决该问题有两种方法，为dfs添置表项用于存储历史搜索结果；动态规划。
即使TSP是NP难问题，普通dfs在TSP上的复杂度为，而经过表项优化的dfs和DP可以将复杂度将为大约。

动态规划

DP也是答案中提供的，比较普遍的做法，但是理解该动态规划的递推式有一丝丝困难。

基本思想为，计算从A出发经过BCD最后回到A的开销，一定为<从B出发经过CD到A的开销+A到B的开销>、<从C出发经过BD到A的开销+A到C的开销>、<从D出发经过BC到A的开销+A到D的开销>三者之一。我们只要计算出这三条子路径的值，分别加上单程的开销，取最小值就能得到A->BCD->A的开销。计算B->CD->A的开销同样可以拆分为C->D->A + dist(B, C)和D->C->A + dist(B,D)进行计算。

维护数组dp[N][1 << (N-1)]，其中N代表城市的数量。dp数组的第一维坐标代表路径的出发城市，第二维用bitmap的形式记录了该路径经过了哪些城市。dp[i][j]的的值代表从城市出发，经由bitmap 中的城市最终回到北京（终点城市）的总开销。需要注意的是，dp中存储的路径是一条线而不是一个环

我们可以指定任意一个城市为北京（终点城市），反正最终结果是一个环，结果都是一样的。但出于方便考虑，我们指定编号最大的那个城市（N-1号城市）为终点城市。终点城市不可能出现在dp存储的路径中，因为我们默认终点城市一定会经过，且在路径的末尾。

举个例子，N=6，终点城市为5，dp[0][0b00110]表示从城市0出发，经过1和2，回到终点城市5的最小开销。dp的第二维索引中，第k位表示是否经过了城市k。

接下来我们就可以构造递推式了，dp[k][mask] = min(dp[c for (1<dp[5][31] = min(dp[0][30] + dist[5][0], dp[1][29] + dist[5][1], dp[2][27] + dist[5][2], dp[3][23] + dist[5][3],
dp[4][15] + dist[5][4])

表项优化的dfs

相比DP，我感觉带表项的dfs容易理解的多。类似于国际象棋的哈希表，我们需要将子树搜索得到的部分结果进行存储，并在面临历史搜索过的相同局面时直接返回表项中存储的结果，而不对子树进行展开。

用之前举过的例子，总共有6个城市，从城市<0>出发，<0-1-2-3>和<0-2-1-3>两条路径的后续搜索过程时完全相同的。譬如我们在搜索<0-1-2-3>这条路线时已经搜出后续的最佳路线是<5-4-0>，也就是说当前的最佳路径是<0-1-2-3-5-4-0>，那么我们在搜索<0-2-1-3>分支时，其后续的最佳路线一定也是<5-4-0>。

我们需要解决的首要问题是，怎么构建表项来存储部分结果？我们不能仅仅依靠路径经过了哪些城市来存储部分结果，譬如<0-1-2>、<0-2-1>两条路径都经过了0、1、2三个城市，还剩下3、4、5没去，但两者一条路径目前在城市2而另一条路径在城市1，显然<0-1-2>路径的后续计算结果无法用于代替<0-2-1>的后续计算，但路径<0-1-2-3>的后续计算可以代替<0-2-1-3>，因为它们不但经过了相同的城市，且当前处于同一城市。

维护数组dict[N][1 << (N-1)]，其中N代表城市的数量。dict数组第一维的坐标代表路径当前位于哪个城市，第二维用bitmap的形式记录了该路径经过了哪些城市。dict[i][j]的值代表经由bitmap 中的城市，且当前位于城市时，后续路径的最小开销。因为部分搜索只能保证后续的搜索是最优的，而不保证之前的搜索，所以直接存储当前整条路径搜到叶节点得到的最优总开销是不可靠的。

AC代码

MLE（memory limit exceeded）坑点

1. 不论DP还是dfs，数组都只能开x[21][1<<19]，如果开x[21][1<<20]会超内存限制（限制32MB），反正有一个城市要作为终点不需要作为中间城市存储状态，开19就够用了。
2. 即使开x[21][1<<19]，21 2^19 sizeof(int) = 42MB，依然超出了内存限制。题目中说单张票的价格不超过1000，那么21张票的价格就不超过21000，完全可以用16位的short或unsigned short类型进行存储，可以节省一半的内存，21MB就不会超过内存限制了。

答案中有一个人是直接开的vector > dp(stateNum,vector(n,MAX))，结果它竟然没超内存，我当时直接震惊，不相信爱情了，结果通过assert大法发现测试点中输入的最大N只有18，vector是动态分配内存的所以逃过一劫，如果输入N=20它就会原地亲妈爆炸。

动态规划

#pragma warning(disable:4996)

#include <iostream>
#include <algorithm>

using namespace std;

unsigned short x[21][21];
unsigned short dp[21][1 << 19];

int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> x[i][j];

    fill(dp[0], dp[0] + 21 * (1 << 19), 65535);
    for (int i = 0; i < N; ++i)        // dp[i][0]代表从城市i出发没去过其它任何城市就返回终点的开销
        dp[i][0] = x[N - 1][i];

    for (int mask = 1; mask < (1 << (N - 1)); ++mask)
    {
        for (int beg = 0; beg < N; ++beg)
        {
            if (mask & (1 << beg))            // 从城市beg出发的路径不可能再经过城市beg
                continue;
            for (int city = 0; city < N - 1; ++city)        // 搜索每一个可分的分支
            {
                int cur_mask = (1 << city);
                if (mask & cur_mask)
                    dp[beg][mask] = min(dp[beg][mask], (unsigned short)(dp[city][mask ^ cur_mask] + x[beg][city]));
            }
        }
    }

    cout << dp[N-1][(1 << (N - 1)) - 1] << endl;
    system("pause");
}

表项优化的dfs

#pragma warning(disable:4996)

#include <iostream>
#include <algorithm>

using namespace std;

int N;
unsigned short x[21][21];
unsigned short dict[21][1 << 19];

unsigned short dfs(int cur, unsigned short cost, int mask)
{
    unsigned short best = 65535;

    if (!mask)                        // 搜索到达叶节点，加上返回终点的开销返回
        return cost + x[cur][N - 1];
    if (dict[cur][mask] != 65535)        // 之前已经进行过完全一样的后续搜索
        return cost + dict[cur][mask];

    for (int i = 0; i < N - 1; ++i)
    {
        int cur_mask = 1 << i;
        if (mask & cur_mask)
        {
            unsigned short temp = dfs(i, cost + x[cur][i], mask ^ cur_mask);
            best = min(best, temp);
        }
    }
    dict[cur][mask] = best - cost;        // 记录后续路径的总开销
    return best;
}

int main()
{
    cout << (3 >> (-1)) << endl;

    cin >> N;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> x[i][j];

    fill(dict[0], dict[0] + 21 * (1 << 19), 65535);

    cout << dfs(N - 1, 0, (1 << (N - 1)) - 1) << endl;
    system("pause");
}