2

我已经实现了一个 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 - 分析结果

配置文件结果 Pastebin 链接

4

1 回答 1

3

这在我看来是错误的：

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是 via 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方法呢？

于 2013-10-01T21:25:59.907 回答