python - 我怎样才能提高这个最短路径/捷径(数组图DS)解决方案的速度？

Question

给定一个迷宫作为数组的数组，其中 1 是一堵墙，0 是一个可通过的区域:

Must include start node in distance, if you BFS this it will give you 21.

[0][0] is the start point.

    |
[   V
   [0, 0, 0, 0, 0, 0], 
   [1, 1, 1, 1, 1, 0], 
   [0, 0, 0, 0, 0, 0], 
   [0, 1, 1, 1, 1, 1], 
   [0, 1, 1, 1, 1, 1], 
   [0, 0, 0, 0, 0, 0]<--   [-1][-1] is the end point.
]

我们必须找到可能的最短路径，我们可以删除一个“1”来帮助创建捷径。

创建最短路径的快捷方式是将 [1][0] 更改为 0，打开一条使距离为 11 的路径。

[
   [0, 0, 0, 0, 0, 0], 
-->[0, 1, 1, 1, 1, 0], 
   [0, 0, 0, 0, 0, 0], 
   [0, 1, 1, 1, 1, 1], 
   [0, 1, 1, 1, 1, 1], 
   [0, 0, 0, 0, 0, 0]
]
return 11

我最初的想法是遍历每个元素并检查它是否 == 1，然后进行 bfs 比较距离与最小值。

当然那太慢了。所以我想遍历每个元素并检查它是否为 1，然后看看它是否正好有两个可以通过的邻居，因为这似乎是唯一可能的捷径有意义的情况。

这是我的代码:

import copy
def bfs(maze):
    visited = set()
    queue = []
    mazeHeight = len(maze)
    mazeWidth = len(maze[0])
    queue.append(((0,0),1))

    while queue:
        yx,distance = queue.pop(0)
        y,x = yx
        visited.add(yx)
        if yx == (mazeHeight-1,mazeWidth-1):
            return distance

        if y+1 < mazeHeight:
            if not maze[y+1][x] and (y+1,x) not in visited:
                queue.append(((y+1,x),distance+1))

        if y-1 >= 0:
            if not maze[y-1][x] and (y-1,x) not in visited:
                queue.append(((y-1,x),distance+1))

        if x+1 < mazeWidth:
            if not maze[y][x+1] and (y,x+1) not in visited:
                queue.append(((y,x+1),distance+1))

        if x-1 >= 0:
            if not maze[y][x-1] and (y,x-1) not in visited:
                queue.append(((y,x-1),distance+1))

    return False

def answer(maze):
    min = bfs(maze)
    mazeHeight = len(maze)
    mazeWidth = len(maze[0])
    for y in range(mazeHeight):
        for x in range(mazeWidth):
            if maze[y][x]:
                oneNeighbors = 0
                if y+1 < mazeHeight:
                    if not maze[y+1][x]:
                        oneNeighbors += 1

                if y-1 >= 0:
                    if not maze[y-1][x]:
                        oneNeighbors += 1

                if x+1 < mazeWidth:
                    if not maze[y][x+1]:
                        oneNeighbors += 1

                if x-1 >= 0:
                    if not maze[y][x-1]:
                        oneNeighbors += 1
                if oneNeighbors == 2:
                    tmpMaze = copy.deepcopy(maze)
                    tmpMaze[y][x] = 0
                    tmpMin = bfs(tmpMaze)
                    if tmpMin < min:
                        min = tmpMin

    return min


print(answer([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]]))

有什么提高速度的建议吗？

Answer 1

您似乎走在正确的轨道上。可以考虑以下方法:

1. 形成n x m的图n 所在的节点和 m是迷宫矩阵的维度。

2. 如果两个节点相邻，则它们之间存在成本零的边0秒。如果两个节点都是 0，则它们之间存在成本边 one由 1 分隔.

(请注意，您需要为每条路径维护两个成本，一个是上面的 zero-one 成本，另一个是路径中要保持最小跟踪的节点数)。

1. 然后执行 BFS 并只考虑具有 zero-one cost <= 1 的路径.

2. 这将为您提供一个线性时间算法(与节点数成线性关系)。

以下代码可能包含错误，但应该可以帮助您入门。

def bfs(maze):
    visited = set()
    queue = []
    mazeHeight = len(maze)
    mazeWidth = len(maze[0])
    queue.append(((0,0),1,0))    

    while queue:
        yx,distance, cost = queue.pop(0)
        y,x = yx
        visited.add(yx)
        if yx == (mazeHeight-1,mazeWidth-1):
            return distance

        if y+1 < mazeHeight:
            if not maze[y+1][x] and (y+1,x) not in visited:
                queue.append(((y+1,x),distance+1, cost))

        if y-1 >= 0:
            if not maze[y-1][x] and (y-1,x) not in visited:
                queue.append(((y-1,x),distance+1, cost))

        if x+1 < mazeWidth:
            if not maze[y][x+1] and (y,x+1) not in visited:
                queue.append(((y,x+1),distance+1, cost))

        if x-1 >= 0:
            if not maze[y][x-1] and (y,x-1) not in visited:
                queue.append(((y,x-1),distance+1, cost))

        if cost == 0:
            if y+2 < mazeHeight:
                if not maze[y+2][x] and (y+2,x) not in visited and maze[y+1][x] == 1:
                    queue.append(((y+2,x),distance+2, cost+1))

            if y-1 >= 0:
                if not maze[y-2][x] and (y-2,x) not in visited  and maze[y-1][x] == 1:
                    queue.append(((y-2,x),distance+2, cost+1))

            if x+1 < mazeWidth:
                if not maze[y][x+2] and (y,x+2) not in visited and maze[y][x+1] == 1:
                    queue.append(((y,x+2),distance+2, cost+1))

            if x-1 >= 0:
                if not maze[y][x-2] and (y,x-2) not in visited and maze[y][x-1] == 1:
                    queue.append(((y,x-2),distance+2, cost+1))

    return False