时间戳

首页 > 解决方案 > BFS与python，当endPoint远离startPoint时找不到解决方案

python - BFS与python，当endPoint远离startPoint时找不到解决方案

问题描述

BFS 的主要算法如下。当 endRow 和 endColumn 远离 startRow 和 startColumn 时，需要很长时间才能在 10x10 网格中找到 startPoint 和 endPoint 之间的路径。关于如何减少运行时间的任何合乎逻辑的解释？

nums = Queue.Queue()
nums.put("")
add = ""
maze  = createMaze()
maze[endRow][endColumn] = "O"

while not findEnd(maze, add): 
    add = nums.get()
    #print(add)
    for j in ["L", "R", "U", "D"]:
        put = add + j
        if valid(maze, put):
            nums.put(put)

标签： pythonbreadth-first-search

解决方案

您的实现细节看起来有点模糊，但据我所知，您没有任何类型的visited数组可以跟踪您已经访问过的单元格，这会将您的算法从 O(N^2) 转换为疯狂的东西O(4^N) （其​​中 N 是数组的高度/宽度，假设它们相等）。您只需要保留这样的数组并在将它们添加到队列时标记值，并确保下次看到它们时不要再次添加它们。

推荐阅读