字节跳动前端答疑群and周日笔试第4题毕业旅行题思路分析
欢迎还没参加笔试的同学使用内推码在官网报名--> VMPGVEU
面向人群： 暑期实习：次年毕业生（毕业时间为 2020.1.1-2020.12.31期间的同学） 全职春招：应届毕业生（毕业时间为 2018.8.1-2019.12.31期间的同学）
正文：
第4题的本质是旅行商问题，解法有很多种。暴力搜索只能通过一小部分的测试用例。 很多同学在纠结北京是第几个城市或第一行是不是北京，其实完全没必要。北京可以是任何一个城市，在这个题中，最终要输出的是一个遍历所有城市的单向环路，所以选择哪个城市作为起点并不影响最终的结果。
该题解题思路很多，暴力搜索、贪心搜索、动态规划(构造最优子结构，自底向上计算最优解)、最小生成树、分治界限(基于上下届或降解阶)，回溯等等。经典TSP问题的算法还包括 模拟退火，遗传算法，蚁群算法，神经网络等待，有兴趣的同学可以去github搜索相关代码阅读。
动态规划法，简单分析下思路，照这个思路过所有用例问题应该不大：
- 1.因为最后走的路线为一个环，可以设城市0为起点城市。
- 2.将每个城市看作二进制的一个位(1代表有，0代表没有)，则数k可以表示一些城市的集合(例如k=13，二进制表示为1101，表示城市0,2,3的集合)
- 3.dp[k][j]表示经过了k集合中的所有城市并且以j城市为终点的路径的最小值。
- 则dp[k][j] = Min{dp[k][j],dp[k-j][i] dis[i][j] | (0<=i<=n-1 && i属于集合k)};(其中k-j表示集合k中去掉数j后的集合(所以j应该是集合k中的元素))，
更多思路可以看这篇文章 https://www.jianshu.com/p/43aa80069265
最后，再次广告下😂。 字节跳动商业变现团队招前端实习或社招，组内拥抱最新前端技术栈，技术氛围浓厚，新人成长空间很大（悄悄告诉你，这道题是组内一位同学出的）。坐标北京，福利待遇啥的就不说了，你懂得😎。
部门的客户端/测开/后端/数据等岗位也在持续招聘中，校招同学请使用内推码VMPGVEU在官网投递。社招/大三或研二实习同学可直接发简历到邮箱 guojunyan@bytedance.com 标题注明【岗位 实习/社招 姓名 手机号】，
另外，建了一个前端内推答疑群，有什么找工作相关的困惑欢迎在群里吐槽交流，群里有已经在字节参加工作的学长/学姐，欢迎要向他们 提 （砸!）问（简！）题（历！）
查看21道真题和解析