如何提高这个最短 path/shortcut(array graph 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

你似乎走对了路。可以考虑以下方法：

形成 n x m 个节点的图，其中 n 和 m 是迷宫矩阵的维度。
如果两个节点相邻0，则它们之间存在成本零的边。如果两个节点都是 0 并且被 1.

one

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

然后执行BFS并只考虑具有zero-one cost <= 1.
这将为您提供一个线性时间算法（与节点数成线性关系）。

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

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

如何提高这个最短 path/shortcut(array graph DS) 解决方案的速度？

How can I improve the speed of this shortest path/shortcut(array graph DS) solution?

python

algorithm

data-structures

array-algorithms