需要指导、转载等，请联系作者 Lewis XU（Email: xuwei3893@gmail.com）。
快手2019年算法真题
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
输入描述：
城市个数$n$（1<$n$≤20） 城市间的车票价钱 $n$行$n$列的矩阵 $price[n][n]$
输出描述：
最小车费花销 $s$
输入例子：
4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0
输出例子：
13
题解
该题属于TSP问题，即每个城市都需要访问一次，并且回到原城市。TSP是NP问题，暴力枚举解空间数量为O($n!$)，状态压缩可以使复杂度降到O($n2^n$)。
状态压缩的关键
可以用一个数字表示当前的一个状态，该数字的二进制则标记该状态是从城市0已经到达过的城市（注意：该二进制的标记是倒着的）。如7的二进制为111，表示从起点城市0已经到达过了城市1、城市2、城市3，2的二进制为10,则表示从起点城市0已经到达了城市1。下面用表格展示了更多的例子，帮助读者理解。
| 状态码 | 二进制 | 已经到达过的城市集合 |
|---|---|---|
| 0 | 0 | {} |
| 1 | 1 | {1} |
| 2 | 10 | {2} |
| 3 | 11 | {1,2} |
| 4 | 100 | {3} |
| 5 | 101 | {1,3} |
| 6 | 110 | {2,3} |
| 7 | 111 | {1,2,3} |
| … | … | … |
检查一个状态$state$是否经过了城市$i$
可使用位运算进行检查。如果$state$包含了城市$i$，则$state$的二进制表示的倒数第$i$位必定为1，依此可以按照($state$>>($i-1$))&1来书写代码。
状态转移方程
记$c[i][state]$为将城市$i$加入到当前状态$state$的票价，那么： \(c[i][state] = \begin{cases} price[i][0], &\text{if }state = 0 \\ price[i][k] + c[k][state-\{k\}], &\text{if }state \neq 0 \text{and} state \text{not contain} k \end{cases}\)
代码
#include <bits/stdc++.h>
using namespace std;
//Assume start from 0 to 0
int tsp(vector<vector<int>> &prices) {
uint nCity = prices.size();
//总的状态数量
ulong nState= (ulong(1)<<(nCity-1))-1;
//cost[i,j] 把i添加到集合j之后的结果
vector<vector<int>> cost(nState, vector<int>(nCity, 9999));
for(int i=0; i<nCity; ++i) {
cost[0][i] = prices[i][0];
}
for(int state=1; state<nState; ++state) {
for(int city = 1; city<nCity; ++city) {
//当前状态没有访问过city，就计算将city包含进来的费用
if(((state>>(city-1))&1) != 1) {
for(int k=1; k<nCity; ++k) {
//如果访问过city_k，就把k踢出去，计算prices[k][city] + cost[state-k][k]
if(((state>>(k-1))&1) == 1) {
cost[state][city] = min(cost[state][city], prices[city][k] + cost[state-(1<<(k-1))][k]);
}
}
}
}
}
int minCost = numeric_limits<int>::max();
for(int i=1; i<nCity; ++i) {
minCost = min(minCost, prices[i][0]+cost[nState-(1<<(i-1))][i]);
}
return minCost;
}
int main(){
int n;
cin>>n;
vector<vector<int>> prices(n,vector<int>(n, 0));
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
cin>>prices[i][j];
}
}
cout<<tsp(prices)<<endl;
return 0;
}
需要指导、转载等，请联系作者 Lewis XU（Email: xuwei3893@gmail.com）。
