尝试使用广度优先搜索时如何缩短生成图的时间？

Question

我不知道如何解释这一点。基本上我正在尝试做Leetcode问题“752.打开锁”

我的解决方案是使用广度优先搜索算法。基本上：

1. 像这样生成 10,000 种可能的组合图

graph{
0000:{0001,0010,0100,...9000},
.
.
.
9999:{9990,9909...0999}
}

2. 使用广度优先搜索打印出从头到尾的每一个可能的路径，将这些路径保存到一个二维数组中。
3. 根据目标和死锁开始过滤每条路径

• 删除所有存在死锁的路径
• 取出所有目标不是最终值的路径

4. 获取最短路径的长度，负1然后返回

当手动测试测试用例时，我的程序似乎可以工作。但是生成 10,000 种可能的组合花了很长时间，以至于当我提交时，Leetcode 给出了超过时间限制的错误。

使用BFS时，不应该有一个现成的图吗？但生成图表时计算时间太长。那么我如何在 BFS 期间动态生成图，这可以缩短计算时间

class Solution:
    @staticmethod
    def generate_lock_graph():
        # Initialize the lock graph
        lock_graph = {}
        
        # Generate all possible combinations of lock digits
        for i in range(10):
            for j in range(10):
                for k in range(10):
                    for l in range(10):
                        node = f"{i}{j}{k}{l}"  # Create a lock combination node
                        neighbors = []  # Initialize the list of neighboring nodes
                        
                        # Generate all possible moves for the current lock combination
                        for digit in range(4):
                            # Generate a new lock combination by incrementing the digit
                            new_combination = list(node)
                            new_combination[digit] = str((int(new_combination[digit]) + 1) % 10)
                            neighbors.append("".join(new_combination))
                            
                            # Generate a new lock combination by decrementing the digit
                            new_combination = list(node)
                            new_combination[digit] = str((int(new_combination[digit]) - 1) % 10)
                            neighbors.append("".join(new_combination))
                        
                        lock_graph[node] = neighbors
        
        return lock_graph

    @staticmethod
    def bfs(graph, start):
        global explored
        global queue
        global possiblePaths

        explored = []
        queue = [[start]]
        possiblePaths = [[start]]

        while queue:  # Creating loop to visit each node
            # Get current node
            path = queue.pop(0)
            node = path[-1]

            if node not in explored:
                neighbours = graph[node]
                for neighbour in neighbours:
                    new_path = list(path)
                    new_path.append(neighbour)

                    possiblePaths.append(new_path)
                    queue.append(new_path)
                explored.append(node)
        # print(possiblePaths)
        return possiblePaths

    def openLock(self, deadends: List[str], target: str) -> int:
        graph = self.generate_lock_graph() #generate the graph
        allpaths = self.bfs(graph,"0000") #start bfs, give all possible path from start to finish
        allpaths = [path for path in allpaths if not any(deadend in path for deadend in deadends)] # remove all paths with deadends
        # allpaths = [path for path in allpaths if target in path] # remove all paths without the target
        allpaths = [path for path in allpaths if path[-1] == target] # remove all paths where target is not the final value
        # print(allpaths)
        if len(allpaths) == 0: # return -1 if no possible paths
            return -1
        else:
            return len(allpaths[allpaths.index(min(allpaths,key=len))]) - 1 # minus one to remove the first node, get the shortest list (shortest path)
solution = Solution()
# solution.bfs(graph,'0000')
deadends = ["0201","0101","0102","1212","2002"]
target = "0202"
print(solution.openLock(deadends,target))

Answer 1

1. 不要使用列表作为队列；从前面移除需要线性时间，而不是恒定时间。更喜欢

   collections.deque

   。
2. 无需在内存中生成实际的图形。您可以在运行 BFS 的同时搜索所有下一个组合，从而使代码变得更加简单。
3. 使用集合来存储访问过的状态而不是列表。

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dist = {}
        deadends_set = {(*map(int, s),) for s in deadends}
        src = (0,) * 4
        if src in deadends_set:
            return -1
        dist[src] = 0
        q = deque([src])
        dest = *map(int, target),
        while q and dest not in dist:
            curr = q.popleft()
            for i, d in enumerate(curr):
                for m in -1, 1:
                    nxt = curr[:i] + ((d + m) % 10,) + curr[i+1:]
                    if nxt not in dist and nxt not in deadends_set:
                        dist[nxt] = dist[curr] + 1
                        q.append(nxt)
        return dist.get(dest, -1)