加速 Dijkstra 的算法来解决 3D 迷宫

Question

我正在尝试编写一个可以解决 3D 迷宫的 Python 脚本，我正在使用 Dijkstra 算法和优先级队列（包含在模块 heapq 中）来完成它。这是我的主要功能代码：

from heapq import *
def dijkstra(start,end,vertices,obstacles):
    covered=[]
    s=vertices.index(s)
    currentVertex=s
    liveDistances={}
    for i in range(len(vertices)):
        liveDistances[i]=inf
    liveDistances[s]=0
    next=[[liveDistances[s],s]]
    while next:
        np,currentVertex=heappop(next)
        covered.append(currentVertex)
        for u in sons(vertices[currentVertex]):
            v=vertices.index(u)
            if v in covered:continue
            if 1+liveDistances[currentVertex]<liveDistances[v]:
                liveDistances[v]=1+liveDistances[currentVertex]
                heappush(next,[liveDistances[v],v])
    if liveDistances[vertices.index(e)]!=inf:
        return liveDistances[vertices.index(e)]
    else:
        return "No path!"

所以基本上它只是将 Dijkstra 应用于 3D 图形。

该程序运行良好，但我想知道它在 10 秒内解决一个 100x100 的 2D 迷宫或在 2 分钟内解决一个 30x30x30 的迷宫是否正常？我在这里实施错误吗？或者它只是正确的执行时间？我可以增强它吗？

我寻求增强的原因是因为我被要求在不到 5 秒（时间限制）内解决问题（在最大 40x40x40 的 3D 迷宫中找到最短路径）。

Answer 1

你知道 A* 搜索 ("A-star") 吗？这是对 Dijkstra 算法的修改，当您对情况的几何结构有所了解时，它可以提供很大帮助。未经修改的 Dijkstra 假设任何边缘都可能是通往目标的极短路径的起点，但情况的几何形状通常不允许这样做，或者至少使其不太可能。

基本思想是，如果您试图找到从丹佛到匹兹堡的最短路径，则通往盐湖城的边不太可能有帮助。因此，您通过向它们添加从该节点到目标的距离的下限来偏置堆上的权重——在这种 2D 情况下，这将是直线或大圆距离，因为没有实际的道路可以比那个短。这种启发式倾向于将错误的选择推到更深的堆中，因此它们通常永远不会被探索。

不过，我无法证明您构建 3D 迷宫的方法适用于 A* 搜索。

Answer 2

我怀疑很多时间会花在这两行：

v=vertices.index(u)
if v in covered:continue

这两行都是 O(n) 操作，其中 n 是图中的顶点数。

我建议您将第一个替换为字典（从顶点名称映射到顶点索引），然后将 covered 从列表更改为集合。

这应该使两个操作的时间复杂度为 O(1)，并且可以使您的速度提高几个数量级。

Answer 3

我最初的方法是使用一些基本的回溯：

boolean[][][] visited = new boolean[h][w][d];
boolean foundPath = false;
public void path(int y, int x,int z) {
        visited[y][x][z] = true;
        if (x == targetx && y == target && z == targetz) {
            foundPath = true;
            return;
        }
        if (!visited[y - 1][x][z] && !foundPath) //if up
            path(y - 1, x, z);
        if (!visited[y + 1][x][z] && !foundPath) //if down
            path(y + 1, x, z);
        if (!visited[y][x - 1][z] && !foundPath) //if left
            path(y, x - 1, z);
        if (!visited[y][x + 1][z] && !foundPath) //if right
            path(y, x + 1, z);
        if (!visited[y][x][z+1] && !foundPath) //if forward
            path(y, x, z + 1);
        if (!visited[y][x][z-1] && !foundPath) //if backward
            path(y, x + 1, z - 1);

        if (foundPath) return;
        visited[y][x][z] = false;
    }

加速 Dijkstra 的算法来解决 3D 迷宫

Speeding up Dijkstra's algorithm to solve a 3D Maze

python

algorithm

3d

maze

dijkstra