python - 如何让我的 A 星搜索算法更高效？

问题描述

我在 matplotlib 中有一个网格（20*20 或 40*40 基于用户的选择），其中包含基于 LatLong 位置划分的数据。该网格中的每个单元格代表一个 0.002 或 0.001 的区域（例如：[-70.55, 43.242]到[-70.548, 43.244]）。网格根据阈值着色，例如高于 30 的任何东西都是绿色的，低于 30 的任何东西都是红色的。

我实现了 A start 算法以在该图上从一个位置（单元格）移动到另一个位置，同时避开所有绿色单元格。在绿色和红色单元格边界上行驶的成本为 1.3，而对角线成本为 1.5，在两个红色单元格之间行驶的成本为 1。

我正在使用对角距离启发式算法，对于每个单元格，我都会获取所有可能的邻居并G根据阈值设置它们的值。

现在我大部分时间都能找到正确的路径，对于附近的单元格，它运行时间不到 1 秒。但是当我走得更远时，它需要 14-18 秒。

我不明白我在这里做错了什么？我一直在想办法改进它，但失败了。

这是算法的一个片段。我想指出，确定可访问的邻居和设置G值在这里可能不是问题，因为每个函数调用运行时间大约为 0.02 - 0.03 秒。

任何建议表示赞赏！谢谢

def a_star(self, start, end):
    startNode = Node(None, start)
    endNode = Node(None, end)
    openList = []
    closedList = []
    openList.append(startNode)

    while len(openList) > 0:

        current = openList[0]
        if current.location == endNode.location:
            path = []
            node = current
            while node is not None:
                path.append(node)
                node = node.parent
            return path[::-1]

        openList.pop(0)
        closedList.append(current)

       # This takes around 0.02 0.03 seconds
        neighbours = self.get_neighbors(current)

        for neighbour in neighbours:
            append = True
            for node in closedList:
                if neighbour.location == node.location:
                    append = False
                    break
            for openNode in openList:
                if neighbour.location == openNode.location:
                    if neighbour.g < openNode.g:
                        append = False
                        openNode.g = neighbour.g
                        break
            if append:

                neighbour.h = round(self.heuristic(neighbour.location, endNode.location), 3)
                neighbour.f = round(neighbour.g + neighbour.h, 3)

                bisect.insort_left(openList, neighbour)
    return False

编辑：添加节点片段

 class Node:
    def __init__(self, parent, location):
        self.parent = parent
        self.location = location
        self.g = 0
        self.h = 0
        self.f = 0

编辑 2：添加图像

圆圈是起点，星是终点。黄色单元格不可访问，因此黄色单元格上没有对角线路径，并且无法在两个黄色单元格之间移动。

标签： pythonalgorithmmatplotlibsearcha-star

这部分效率很低。对于您遍历两个相对较大的列表的每个邻居，一旦列表开始增长，这会使整体复杂性非常高：

for node in closedList:
    if neighbour.location == node.location:
        append = False
        break
for openNode in openList:
    if neighbour.location == openNode.location:

基本上，您的算法不应依赖于任何列表。你有你的单元格，你从列表中弹出一个，你得到 8 个邻居，你通过与你拥有的单元格进行比较来处理它们，然后将其中一些附加到列表中。无需遍历任何列表。

python - 如何让我的 A 星搜索算法更高效？

问题描述

解决方案

推荐阅读