旅行商问题

简介

旅行商问题（简称TSP问题）是这样描述的：

一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。这是一个非常经典的组合优化问题。由于其在交通运输，电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。

问题分析

从图论的角度看，可以把推销员的路径当成一条哈密顿回路，城市与城市之间的道路看做无向边，道路的距离看做无向边的边权，城市看做图中的点。所以，该问题实质是在一个带权完全无向图中，找条权值最小的哈密顿回路。

由于该问题的可行解是所有顶点（假设共有n个顶点）的全排列，所以一般精确算法的时间复杂度为 $O(N!)$ 。随着顶点数的增加，时间复杂度会以指数级别的程度上升，所以这是一个NP-Complete问题和NP-Hard问题。

研究历史

早期的研究者使用精确算法（动态规划，暴力搜索等）求解该问题，但是随着问题规模增大，时间复杂度开始指数爆炸，快速增长到无法计算的地步，此时精确算法变得无能为力。因此在后来的研究中，国内外学者更偏向于使用近似算法或者启发式算法（模拟退火，蚁群算法）来求解该问题的近似解。

我的思路

以下关于精确做法的讨论全部基于n数据范围不大的情况下。

方案评测链接

通过对该问题的模型进行建图，很容易想到一种朴素的做法。枚举n个点的全排列，这样一共就有n!种情况，对于所有这些情况，分别计算路径长度，取路径长度的最小值。点与点之间的最短路可以通过floyd算法预处理求出，时间复杂度为 $O(N ^3)$ 。总的时间复杂度为 $O(N \times N!)$ 。

乍一看没问题，但是这样忽略了每个点只能经过一次的限制条件。如果考虑上该条件，每个点只有两种状态，已访问过和未访问过，这样就很自然的会想到状态压缩的思路去表示方案的集合。

在任意时刻，要表示出哪些点被走过，哪些点没有走过，可以用一个n位二进制数，若第i位为1则表示第i个点已经被经过，反之未被经过。这样所有可能的状态都能通过一个整数表示出来了（前提是计算机存放的下 $2^k$ 规模的数据，因此要限制数据范围大小）。

这样，利用状态压缩DP求解该问题的方案就呼之欲出了。

状压DP

令dp[i][j]表示当前状态情况用整数表示为i时，且目前处于点j时的最短路径。

起始状态：dp[1][0] = 0。表示只经过了起点0，最短路径长度为0，其余状态都设为正无穷大。
目标状态：dp[ $2^n - 1$ ][终点]，即经过所有点且处于终点的最短路。加上终点到起点1的距离，即为所求答案。
状态转移方程： $dp[i][j] = min(dp[i][j], dp[i \bigoplus 2^{j-1})][k] + g[k][j])$

因此可以写一个三重循环，第一重循环枚举状态，第二重枚举i状态下可能的点j，第三种枚举i状态下可能的点k去更新最短距离

细节

k表示该状态由点k走到点j
g[k][j]表示点k和点j之间的最短路大小
由于是从点k到点j，所以必须满足以下两个条件
1. 在i的状态下，点j已访问过
2. 点k已被访问过
这可以通过简单的if判断语句+位运算基本知识解决
除了点j外，其他点的状态不能发生改变。

这里主要着重讲一下4条件。

异或的一个重要运算法则就是 $x \bigoplus 0 = x$ ，而 $2^{k-1}$ 除了k位上的数字为1其余均为0，这样就可以保证从点k走到点j，除了点j的状态，其他点的状态不会发生改变

这样，该问题的状态压缩DP解法分析完毕。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 25
#define INF 0x3f3f3f3f
ll read() {
    ll x=0,f=1;char ch;
    do{ch=getchar();if(ch=='-') f=-1;} while(ch<'0'||ch>'9');
    do{x=x*10+ch-48;ch=getchar();} while(ch>='0'&&ch<='9');
    return x*f;
}
int dp[1 << 20][20], g[20][20];
int n;

void init() {
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
}

void solve() {
    n = read();
    init(); //初始化状态
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g[i][j] = read();
    for (int i = 1; i < (1 << n); i += 2) { //优化，第1位必定已经过
        for (int j = 0; j < n; j++) {
            if (!((i >> j) & 1)) continue; //当前i状态下未经过j点，忽略
            for (int k = 0; k < n; k++) {
                if (j == k) continue; //无意义情况
                if (!((i >> k) & 1)) continue; //当前i状态下未经过点k，忽略
                dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + g[k][j]);
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; i++) { //枚举终点
        ans = min(ans, dp[(1 << n) - 1][i] + g[i][0]);
    }
    printf("%d\n", ans);
}

int main() {
    solve();
    return 0;
}

高亮代码

模拟退火SA

虽然该问题可以用状态压缩DP解决，但实际上跑得非常慢。当点的数量大于20后，程序就无法在规定时间内运行出正确的结果。因此必须提出新的算法来解决该问题。

这里就引入了近似算法的概念~~从网上抄的~~：近似算法是一种适合于解决大规模组合优化问题的通用而有效的近似算法，理论上算法具有概率的全局优化性能，具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点。模拟退火算法是一种随机算法，并不一定能找到全局的最优解，可以比较快的找到问题的近似最优解。

翻译一下就是：模拟退火等其他近似算法跑得快，但是结果不一定正确。不过算法设计的越合理，离正确结果就越接近。

模拟退火算法核心的思想就是在搜索过程中有一定的概率p来接受一个比当前解要差的解，因此有可能会跳出局部的最优解，达到全局的最优解。

解决tsp思路

产生一条新的路径 $path_i$ ，并计算路径 $path_i$ 的长度
若 $path_{i + 1}$ 的长度小于 $path_i$ 则接受 $path_{i+1}$ 。否则依然有一定的概率接受 $path_{i+1}$ 为新的路径。
重复以上步骤，直到找出答案退出循环

这样既避免了无穷无尽的枚举，也能够在有限的循环中尽量减少寻找局部最优解的步数，统筹全局。

通过这样的分析可以看出，模拟退火算法不能像状态压缩DP一样百分百求出精确解，只能够较快速地找出问题的最优近似解。

tsp问题应用

旅行商问题具有重要的实际意义和工程背景。它一开始是为交通运输而提出的，比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等。实际上其应用范围扩展到了许多其他领域．下面举几个实例。

印制电路板转孔是 TSP 应用的经典例子，在一块电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游。把这个问题转化为 TSP，孔相当于城市．孔到孔之问的移动时间就是距离。

天体成像的时候，需要对两颗卫星的位置进行调整，如何控制卫星，使消耗的燃料最少，可以用 TSP 来求解。这里把天体看作城市，距离就是卫星移动消耗的燃料。

美国国家卫生协会在人类基因排序工作中用 TSP 方法绘制放射性杂交图。把 DNA 片段作为城市．它们之间的相似程度作为城市间的距离。法国科学家已经用这种办法作出了老鼠的放射性杂交图。

此外，旅行商问题还有电缆和光缆布线、晶体结构分析、数据串聚类等多种用途。更重要的是．它提供了一个研究组合优化问题的理想平台。很多组合优化问题，比如背包问题、分配问题、车间调度问题都和 TSP 同属 NP 完全问题，它们都是同等难度的．如果其中一个能用多项式确定性算法解决，那么其他所有的 NP 完全问题也能用多项式算法解决。很多方法本来是从 TSP 发展起来的．后来推广到其他 NP 完全问题上去。