编程题：毕业旅行问题

　

毕业旅行

也就是旅行商（TSP）问题，有很多解决方法，这里就介绍一种：动态规划，参考干货|十分钟教你用动态规划算法解Travelling Salesman Problem（TSP）问题，附代码……。

最重要的是找到状态转移方程，是这个：

从某一点出发，经过V‘+{i}中的所有点到达i（注意i是在V’中的）的最短距离是[经过V‘中所有点最后到达某一点k的最短距离加上k到i的距离]的最小值，Python代码以及解释：

# -*- coding:utf-8 -*-
class Solution:
    def tsp(self, matrix):
        m, n = len(matrix) * len(matrix), len(matrix)
        # 状态压缩DP,5表示0101,dp[i][j]表示从0出发,经过i中的几个到达j,要求i中有j
        dp = [[float('inf')] * n for _ in range(m)]
        dp[1][0] = 0
        for i in range(1, m):
            if not (i & 1):  # i中不能包括0,不能从0出发
                continue
            for j in range(1, n):  # j是要加入的
                if i & (1 << j):  # 如果i中包括j就重复了
                    continue
                for k in range(n):
                    if i & (1 << k):  # 如果i中包括k
                        # i中加上j,0到j的最短距离可能为原来i中任何一个k到j的距离与剩余最短距离之和
                        dp[(1 << j) | i][j] = min(
                            dp[(1 << j) | i][j], dp[i][k] + matrix[k][j])
        res = float('inf')
        # 最后还要回到0
        for i in range(n):
            res = min(res, dp[m - 1][i] + matrix[i][0])
        return res


if __name__ == '__main__':
    print(Solution().tsp(
        [[0, 3, 6, 7], [5, 0, 2, 3], [6, 4, 0, 2], [3, 7, 5, 0]]))
    print(Solution().tsp(
        [[0, 2, 6, 5], [2, 0, 4, 4], [6, 4, 0, 2], [5, 4, 2, 0]]))

相关阅读

关于smtp.exmail.qq.com:25端口访问超时的问题

近期由于项目需要，使用了org.apache.commons.email来发送邮件的功能，如下：<dependency> <groupId>org.apache.commons</groupId>

解决windows系统80端口被占用问题

80端口被system(pid=4)占用的解决方法 80端口一般被当做网页服务器的默认端口，使用本机搭建服务器环境的时候，都会默认使用80端口来

百度竞价常见问题：影响点击量的因素有哪些？

会了百度竞价，其它如搜狗竞价，360竞价也基本上没有什么问题！但百度竞价面临很多的常识！在操作过程中，很多简单的问题，不一定会引起重视

网络不稳定问题的兼容处理

玩家由于网络波动造成短线重连，需要知道的是，网络问题，我们能做的只是兼容处理，不能完美解决。网络问题分两种情况： 一、客户端向服务

互联网产品经理面试问题汇总（18问）

小编导读：以下内容是根据作者看了很多面试经验之后的总结，包括百度面经，腾讯面经，新浪面经，360面经，搜狐面经，迅雷面经等，希望能给大家一