python - A-star 比 dijkstra 慢

Question

我有一个令人讨厌的错误，我在很长一段时间内都无法解决。我已经在 python 中使用 A*（A-star）和 Dijkstra 实现了迷宫求解，我的 A* 实际上比 Dijkstra 慢。

这部分对两者都是相同的：

    open_list={}

    dist=dict([(v, float('inf')) for v in self.adj_list])
    dist[start]=0

    parents=dict([(v,None) for v in self.adj_list])

    marked={}
    marked[start]=True
    while open_list:
        (tmp,val)=min(open_list.items(), key=lambda x: x[1])
#take current minimum from open_list, add it to closed list and
#remove it from open_list

        del open_list[tmp]

        #if we found exit
        if tmp == stop:
            path=deque([])

            while parents[tmp]:
                path.appendleft(tmp)
                tmp=parents[tmp]

            path.appendleft(start)
            return list(path)

一个*：

 for v,w in self.adj_list[tmp]:
            if v not in marked:
                marked[v]=True

                dist[v]=dist[tmp]+w
                open_list[v]=dist[v]+self.h[v]

                parents[v]=tmp

            elif v in open_list:
                if dist[v] > dist[tmp]+w:#better path exists
                    dist[v]=dist[tmp]+w
                    parents[v]=tmp
                    open_list[v]=dist[v]#update value in open_list

迪杰斯特拉：

for v,w in self.adj_list[tmp]:
            if v not in marked:
                marked[v]=True

                dist[v]=dist[tmp]+w
                open_list[v]=dist[v]

                parents[v]=tmp

            elif v in open_list:
                if dist[v] > dist[tmp]+w:
                    dist[v]=dist[tmp]+w
                    parents[v]=tmp
                    open_list[v]=dist[v]

正如你所看到的，它们是相同的（除了 A* 中的启发式部分），但由于某种原因，A* 速度较慢并且if dist[v] > dist[tmp]+w:#better path exists更频繁地进入这个分支。启发式很好，我检查了多次

有任何想法吗？

如果你想尝试，这里是 Github repo

标签： pythonpython-3.xdijkstraa-starmaze