python - 加速 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

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

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

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

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

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