Python，回顾并加速A*算法

Question

我已经实现了一个 A* 算法来找到网格世界中两点之间的最短路径。对于大路径长度，该算法需要很长时间。我首先想知道我的实现是否正确，是否可以进行任何优化？

aStar 算法的参数是您的当前位置和您希望前往的位置，作为 (x,y) 元组。

一个节点的Node.value是一个行进方向(NSEW)，getAdjacentNodes()返回一个与我们可以行进的节点直接相邻的节点列表到。

#Perform an A* search to find the best path to the dirt
  def aStar(self, current, end):
    openSet = set()   #Set of explorable nodes
    openHeap = []     #All paths heap, lowest cost on top
    closedSet = set() #Best path so far
    curNode = Node(0, current, self.manHatDist(current, end))
    openSet.add(curNode)
    openHeap.append((curNode.cost,curNode))
    while openSet:
      curNode = heapq.heappop(openHeap)[1]
      if curNode.pos == end:
          return self.getDirections(curNode)
      openSet.remove(curNode)
      closedSet.add(curNode)
      for tile in self.getAdjacentNodes(curNode.pos):
         if tile not in closedSet:
             tile.parent = curNode
             tile.cost = self.manHatDist(curNode.pos, end) + self.euclidDist(curNode.pos, current) + curNode.cost
             if tile not in openSet:
                 openSet.add(tile)
                 heapq.heappush(openHeap, (tile.cost,tile))
    return []

  #Get the moves made to get to this endNode
  def getDirections(self, endNode):
    moves = []
    tmpNode = endNode
    while tmpNode.parent is not None:
      moves.append(tmpNode.value)
      tmpNode = tmpNode.parent
    moves.reverse()
    return moves

节点类

# Node class for A* search
class Node:
  def __init__(self, value, pos, cost):
    self.pos = pos
    self.cost = cost
    self.value = value
    self.parent = None

  def __lt__(a, b):
    if(a.cost < b.cost):
      return 1
    return 0

  def __gt__(a, b):
    if(a.cost > b.cost):
      return 1
    return 0

编辑 - 这是 getAdjacentNodes 方法

  #Return all possible moves from given tile as Node objects
  def getAdjacentNodes(self, curPos):
    allMoves = ['North','South','East','West']
    posMoves = []
    for direction in allMoves:
      if(self.canMove(direction, curPos)):
        posMoves.append(Node(direction, self.getLocIfMove(curPos, direction), 0))
    return posMoves

EDIT2 - 分析结果

Profile Result Pastebin Link

Answer 1

这在我看来是错误的:

for tile in self.getAdjacentNodes(curNode.pos):
    if tile not in closedSet:
        tile.parent = curNode
        tile.cost = self.manHatDist(curNode.pos, end) + self.euclidDist(curNode.pos, current) + curNode.cost
        if tile not in openSet:
            openSet.add(tile)
            heapq.heappush(openHeap, (tile.cost,tile))

第一个问题。新瓦片成本的计算是:

self.manHatDist(curNode.pos, end) + self.euclidDist(curNode.pos, current) + curNode.cost

但它应该是:

curNode.cost
- self.manHatDist(curNode.pos, end)
+ self.euclidDist(curNode.pos, tile.pos)
+ self.manHatDist(tile.pos, end)

(如果您对表示搜索节点的方式更聪明，则可以避免计算新图 block 成本的减法，但我会把它留给您。)

第二个问题。发现 tile 不在 closedSet 中后，您立即假设到达 tile 的最佳方法是通过 curNode。但是 tile 不可能已经在 openSet 中了吗？如果是这样，可能还有另一种通向 tile 的途径，它比通过 curNode 的途径更好。*所以这段代码应该是:

for tile in self.getAdjacentNodes(curNode.pos):
    if tile not in closedSet:
        cost = (curNode.cost
                - self.manHatDist(curNode.pos, end)
                + self.euclidDist(curNode.pos, tile.pos)
                + self.manHatDist(tile.pos, end))
        if tile not in openSet or cost < tile.cost:
            tile.parent = curNode
            tile.cost = cost
            openSet.add(tile)
            heapq.heappush(openHeap, (cost,tile))

我不能说这是否会解决您的性能问题。但它可能会提供更好的结果。

* 如果 self.euclidDist(curNode.pos, tile.pos) 始终为 1，则不可能有更短的路线。但如果是这样，为什么还要为 euclidDist 而烦恼 方法？