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结果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)

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

第二个问题。在发现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方法呢？