毕业旅行问题.md
date: 2021-08-22 12:11:39.91
updated: 2021-08-22 12:11:39.91
url: /2021/08/22/字节跳动---毕业旅行问题md
categories:
tags:
字节跳动---毕业旅行问题
@[toc]
一、问题描述
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
输入描述:
城市个数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
例子说明1:
共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。
二、分析
方法一：回溯【超时】
把所有的解通过一棵树表达出来，然后通过深度优先遍历，找到一个解的时候就将其记录下来，最后输出最小的解即可
如图所示，从根节点到叶子节点的所经过的节点就是其路径，每个边的长度之和就是总车票价格。
当然还有一种优化的方法，就是在遍历过程中，如果发现此时路径长度已经超出了之前找到的最小路径长度，就可以进行剪支操作，即不再遍历。
这种方法的时间复杂度为$O(n!)O(n!)O(n!)$，当n大于12之后，其计算时间就已经非常大了。这种方法会因为超时无法通过所有的测试数据。
方法二：动规
-
第一步：明确动态规划的状态和选择
对于这道题，状态无非就是 旅行出发的起点和经过的城市，所以用一个二维dp数组来进行递归
旅行的出发点 还好说， 用数组的索引 就可以直接表示，关键是怎么表示已经经过的城市，经过的城市不可能只有一个，一个数组的索引肯定不能够表示全部，所以用什么来表示这个状呢？？？
所以用数组的下标索引当成一个位图，用其中的 每个bit位代表已经经过哪些城市
虽然找到解决经过的城市的方法，但是还要考虑怎么设置进比特位，因为我们在进行判断的时候肯定需要知道对应bit位是那个城市，所以还需要考虑bit位的设计
规定：从1到n-1（n为城市的个数） 用二进制表示的话，刚好可以映射成除了0号城市外的剩余n-1个城市在不在子集n[j]，1代表在，0代表不在
例：若有总共有4个城市的话，除了第0号城市，对于1-3号城市
111 = V-1 = 2^3 - 1 = 7 ，从高位到低位表示3到1号城市都在子集中
而101 = 5 ，表示3,1号城市在子集中，而其他城市不在子集中
所以该索引的大小为：1 << n（n为城市的个数）
int stateNum = 1 << n;
// dp[i][j]中的i是一个二进制形式的数，表示经过城市的集合，如0111表示经过了城市0,1,2
// dp[i][j]表示经过了i中的城市，并且以j结尾的路径长度
vector<vector<int> > dp(stateNum,vector<int>(n,MAX));
dp[i][j]的含义：中的i是一个二进制形式的数，表示经过城市的集合，如0111表示经过了城市0,1,2，表示经过了i中的城市，并且以j城市结尾的路径（钱）长度
第二步：明确base case
这个就很容易确定
dp[1][0] = 0; //从城市0出发，所以经过城市0，以城市0结尾的路径为0
从城市0出发，所以经过城市0，以城市0结尾的路径为0
第三步：找状态转移方程
👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇
在代码中
三、代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int getAns(vector<vector<int>> &nums)
{
const int MAX = 0x0fffffff;
int n = nums.size();
int stateNum = 1 << n;
// dp[i][j]中的i是一个二进制形式的数，表示经过城市的集合，如0111表示经过了城市0,1,2
// dp[i][j]表示经过了i中的城市，并且以j结尾的路径长度
vector<vector<int> > dp(stateNum,vector<int>(n,MAX));
dp[1][0] = 0; //从城市0出发，所以经过城市0，以城市0结尾的路径为0
//从城市0出发，更新和其他城市的距离
for(int i=1;i<stateNum;i++)
{
for(int j=0;j<n;j++)
{
if(dp[i][j] != MAX)
{
//如果已经访问过
for(int k=0;k<n;k++)
{
if( (i & (1 << k) ) == 0)
{
//没有访问过k，且从这里到k的距离小于原来的距离，则更新
dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k],dp[i][j] + nums[j][k]);
}
}
}
}
}
int res = MAX;
for(int i=1;i<n;i++)
{
res = min(res,dp[stateNum-1][i] + nums[i][0]);
}
return res;
}
int main(int argc, char const *argv[])
{
int n;
while(cin>>n)
{
vector<vector<int>> edges(n,vector<int>(n,0));
int x;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin>>edges[i][j];
}
}
cout<<getAns(edges)<<endl;
}
return 0;
}
评论区