带有python的BFS，当EndPoint离startPoint很远时找不到解决方案

Question

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)

Answer 1

您的实现细节看起来有点模糊，但据我所知，您没有任何一种visited数组来跟踪您已经访问过的单元格，从而将算法从O（N ^ 2 ）之类的疯狂对象，例如O（4 ^ N）（假设N等于数组的高度/宽度，则N为数组的高度/宽度）。您只需保留一个这样的数组并在将它们添加到队列中时将它们标记掉，并确保下次看到它们时不要再次添加它们。