• 来自北大算法课的Leetcode题解：847. 访问所有节点的最短路径

    代码仓库：Github | Leetcode solutions @doubleZ0108 from Peking University.

    • 解法1(超时)：因为所有边的长度都为1，因此对于无权无向图的遍历可以采用广度优先遍历。因为题目要求可以从任意节点出发，因此就将每个节点作为起始点分别进行广度优先遍历，且因为要遍历到所有节点，因此在常规的(node, cost) 元组基础上还要加加一个traveled数组记录每个点当前是否被遍历。

      • 改进1(T5% S85%)：这么做超时的主要问题是因为traveled是数组，没法hash，因此无法使用visited记录(node, traveled)是否出现过减小搜索空间。解决办法是将这个数组变为字符串 → 更进一步可以变为二进制字符串 → 又可以用一位十进制数表示，这样既可以hash，又进行了状态压缩。具体来说，

        • 如果十进制数 == 2 N − 1 2^N - 1 2N−1则代表所有节点都被访问到了，具体实现if traveled == (1 << N) - 1:

        • 初始化为出发节点的二进制对应的十进制，1<（左移 i i i位代表 × 2 i \times 2^i ×2i）

        • 记录traveled信息的增加，traveled_ = traveled | (1 << dst)

          FF3E5D35-DCAC-4460-BC14-327828FD88AB.jpeg

      • 改进2(T18% S33%)：也可以把所有点作为起点都压入同一个队列中然后一起做（替代外层循环），只要找到一个traveled全覆盖的就可以终止返回了

    class Solution(object):
    def shortestPathLength(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: int
        """
        # 解法1 改进1
        minCost = 1e06
        for start in range(len(graph)): # 分别把每个点作为起始
            queue = [(start, 0, 1<<start)]
            visited = set((start, 1<<start))

            while queue:
                src, cost, traveled = queue.pop(0)
                if traveled == (1 << len(graph)) - 1:
                    minCost = min(minCost, cost)
                    break
                for dst in graph[src]:
                    traveled_ = traveled | (1 << dst)
                    if (dst, traveled_) not in visited:
                        queue.append((dst, cost+1, traveled_))
                        visited.add((dst, traveled_))

        return minCost


    def otherSolution(self, graph):
        # 解法1 改进2
        queue = [(start, 0, 1<<start) for start in range(len(graph))]
        visited = set((start, 1<<start) for start in range(len(graph)))

        while queue:
            src, cost, traveled = queue.pop(0)
            if traveled == (1 << len(graph)) - 1:
                return cost
            for dst in graph[src]:
                traveled_ = traveled | (1 << dst)
                if (dst, traveled_) not in visited:
                    queue.append((dst, cost+1, traveled_))
                    visited.add((dst, traveled_))


        # 解法1(超时)
        minCost = 1e06
        for start in range(len(graph)): # 分别把每个点作为起始
            queue = [(start, 0, [0 for _ in range(len(graph))])]
            queue[0][-1][start] = 1

            while queue:
                src, cost, traveled = queue.pop(0)
                if 0 not in traveled: 
                    minCost = min(minCost, cost)
                    break
                for dst in graph[src]:
                    traveled_ = traveled.copy()
                    traveled_[dst] = 1
                    queue.append((dst, cost+1, traveled_))

        return 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
  • 相关阅读:
    视频特效制作软件 After Effects 2024 mac中文版新增功能
    美容行业怎样利用自动化程序减少积压索赔案件
    2024骨传导耳机哪款值得买？健身人士说这五款骨传导耳机好~
    Java面试题
    word调整标题编号
    HTML使用canvas绘制海报（网络图片）
    cpp学习笔记：STL list容器
    【MyBatis笔记03】MyBatis实现CRUD增删改查功能
    洛谷P6586 蒟蒻火锅的盛宴
    Net 高级调试之一：开始认识一些调试工具
  • 原文地址：https://blog.csdn.net/double_ZZZ/article/details/126517769