Python - 加速A星寻路算法

Question

我写了第一个稍微复杂一点的算法，叫做A星寻路算法。我参考了一些Python.org的建议，在实现图的时候，使用了字典来存储每个节点连接到的所有其他节点。因为这是为了做一个游戏，所以每个节点其实就是一个网格中的一个方块，这也是我计算启发式（也就是估算路径的方式）时的依据。

多亏了timeit这个工具，我知道我可以每秒成功运行这个函数超过一百次。这样一来，我有点不安，因为这还没有考虑其他“游戏内容”，比如图形显示或者游戏逻辑的计算。所以我很想看看有没有人能帮我加速这个算法，我对Cython或者类似的东西完全不熟悉，也不会写一行C语言。

不多说了，这就是我的A星函数。

def aStar(self, graph, current, end):
    openList = []
    closedList = []
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList.append(current)
    while len(openList) is not 0:
        current = min(openList, key=lambda inst:inst.H)
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.append(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.append(tile)
                tile.parent = current
    return path

Answer 1

正如上面所提到的，把 closedSet 改成一个集合。

我尝试把 openList 写成一个堆，使用了 import heapq：

import heapq

def aStar(self, graph, current, end):
    closedList = set()
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList = [(-1, current)]
    heapq.heapify(openList)
    while openList:
        score, current = openList.heappop()
        if current == end:
            return retracePath(current)
        closedList.add(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.heappush((tile.H, tile))
                tile.parent = current
    return path

不过，你还是需要在 if tile not in openList 这行代码里进行搜索，所以我会这样做：

def aStar(self, graph, current, end):
    openList = set()
    closedList = set()

    def retracePath(c):
        def parentgen(c):
             while c:
                 yield c
                 c = c.parent
        result = [element for element in parentgen(c)]
        result.reverse()
        return result

    openList.add(current)
    while openList:
        current = sorted(openList, key=lambda inst:inst.H)[0]
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.add(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                openList.add(tile)
                tile.parent = current
    return []

Answer 2

我会像大家说的那样使用集合，但我还会用一个堆来找到最小的元素（也就是下一个current）。这就需要同时维护一个开放集合和一个开放堆，不过内存使用应该不是大问题。而且，集合的插入速度是O(1)，堆的插入速度是O(log N)，所以它们的速度都很快。唯一的问题是，heapq模块并不是特别适合用键来操作。就我个人而言，我会直接修改它来支持键，这应该不难。或者，你也可以在堆中使用(tapes.H, tapes)这样的元组。

另外，我会采纳aaronasterling的建议，使用迭代而不是递归，但我还会把元素添加到path的末尾，然后在最后反转path。这样做的原因是，在列表的第0个位置插入一个元素非常慢（我记得是O(N)），而添加到末尾是O(1)，如果我没记错的话。那部分的最终代码是：

def retracePath(c):
    path = [c]
    while c.parent is not None:
        c = c.parent
        path.append(c)
    path.reverse()
    return path

我把return path放在最后，因为从你的代码来看，似乎应该这样做。

以下是使用集合、堆等的最终代码：

import heapq


def aStar(graph, current, end):
    openSet = set()
    openHeap = []
    closedSet = set()

    def retracePath(c):
        path = [c]
        while c.parent is not None:
            c = c.parent
            path.append(c)
        path.reverse()
        return path

    openSet.add(current)
    openHeap.append((0, current))
    while openSet:
        current = heapq.heappop(openHeap)[1]
        if current == end:
            return retracePath(current)
        openSet.remove(current)
        closedSet.add(current)
        for tile in graph[current]:
            if tile not in closedSet:
                tile.H = (abs(end.x - tile.x)+abs(end.y-tile.y))*10
                if tile not in openSet:
                    openSet.add(tile)
                    heapq.heappush(openHeap, (tile.H, tile))
                tile.parent = current
    return []

Answer 3

一个简单的优化方法是用集合（sets）来代替列表（lists）来表示开放集合和闭合集合。

openSet   = set()
closedSet = set()

这样一来，所有的 in 和 not in 检查的时间复杂度就会变成 O(1)，而不是 O(n)。