1

我很难跟踪由getAdjacentTiles(..). 我在下面确定了我的 A* 实现的性能问题是我没有跟踪以前看到的图块，每次调用都getAdjacentTiles返回新图块（Node's）而不是openSetor中的任何图块closedSet。我决定使用 Node 对象列表作为迄今为止创建的所有图块，并将其传递给它getAdjacentTiles以确定它生成的图块是否已经被访问过。

我的问题是，我似乎无法正确跟踪这些图块。每当我的 A* 需要采取超过 4 次以上的动作才能到达end它的位置时。我确信这与我如何尝试跟踪瓷砖（再次Node被访问过的瓷砖）.apped(tile)有关getAdjacentTiles(...)当循环通过allTiles集合？

这是导致我提出这个问题的问题的链接

产生的错误（有时，仅当 A* 路径长于大约 3 步时..）

File "P3.py", line 67, in aStar
 openSet.remove(curNode) 
KeyError: <__main__.Node instance at 0xa39edcc>

资源

  #Perform an A* search to find the best path to the dirt
  def aStar(self, current, end):
    openSet = set()
    openHeap = []
    closedSet = set()
    allTiles = set()
    curNode = Node(0, current, self.manHatDist(current, end))
    openSet.add(curNode)
    allTiles.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)
      adjNodes = self.getAdjacentNodes(curNode.pos, allTiles)
      for tile in adjNodes:
        t = tile
        if t not in closedSet:
          cost = (curNode.cost - self.manHatDist(curNode.pos, end) 
                  + self.euclidDist(curNode.pos, current)
                  + self.manHatDist(t.pos, end))
          if t not in openSet or cost < t.cost:
            t.parent = curNode
            t.cost = cost
            openSet.add(t)
            heapq.heappush(openHeap, (cost,t))
        allTiles.add(t)
    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

  #Return all possible moves from given tile as Node objects
  def getAdjacentNodes(self, curPos, allTiles):
    allMoves = ['North','South','East','West']
    posMoves = []
    for direction in allMoves:
      if(self.canMove(direction, curPos)):
        posMoves.append(Node(direction, self.getLocIfMove(curPos, direction)))
    retNodes = []
    for posLocNode in posMoves:
      set = False
      for tile in allTiles:
        if(posLocNode.pos == tile.pos):
          set = True
          retNodes.append(tile)
      if(not set):
        retNodes.append(posLocNode)
    return retNodes
4

1 回答 1

0

让我们启动交互式解释器，看看我们能找到什么。（你没有在问题中给出你的班级名称，所以我称之为Search。）

>>> Search().aStar((0,0), (2,2))
Traceback (most recent call last):
  ...
  File "q19128695.py", line 25, in aStar
    openSet.remove(curNode)
KeyError: <__main__.Node instance at 0x104895518>

好的，第一个问题是这些Node实例不是不言自明的。我们不能对“Node instance at 0x104895518”做任何事情，所以让我们__repr__在类中添加一个方法Node：

def __repr__(self):
    return 'Node({0.value}, {0.pos}, {0.cost})'.format(self)

然后再试一次：

>>> Search().aStar((0,0), (2,2))
Traceback (most recent call last):
  ...
  File "q19128695.py", line 25, in aStar
    openSet.remove(curNode)
KeyError: Node(East, (1, 2), 3.41421356237)

好的，这提供了更多信息。让我们启动Python 调试器并进行事后分析：

>>> import pdb
>>> pdb.pm()
> q19128695.py(25)aStar()
-> openSet.remove(curNode)
(Pdb) openSet
set([Node(North, (2, -1), 6.0), Node(East, (2, 2), 4.65028153987), 
     Node(West, (-1, 1), 5.0), Node(North, (0, -1), 5.0),
     Node(South, (1, 3), 6.65028153987), Node(South, (0, 3), 6.0), 
     Node(East, (3, 0), 6.0), Node(West, (-1, 0), 5.0),
     Node(North, (1, -1), 5.0), Node(East, (3, 1), 6.65028153987),
     Node(West, (-1, 2), 6.0)])
(Pdb) closedSet
set([Node(0, (0, 0), 4), Node(South, (2, 1), 3.41421356237),
     Node(East, (1, 1), 3.0), Node(South, (0, 1), 3.0),
     Node(East, (2, 0), 3.0), Node(East, (1, 0), 3.0),
     Node(East, (1, 2), 3.41421356237), Node(South, (0, 2), 3.0)])
(Pdb) curNode
Node(East, (1, 2), 3.41421356237)
(Pdb) curNode in closedSet
True

所以节点已经关闭了。这怎么可能发生？好吧，如果该节点已添加到openSet和openHeap两次，则可能会发生这种情况。然后它会从openHeap两次弹出（因为堆可以有多个相同的项目），但它只能从openSet一次中删除。有问题的代码如下所示：

if t not in openSet or cost < t.cost:
    t.parent = curNode
    t.cost = cost
    openSet.add(t)
    heapq.heappush(openHeap, (cost,t))

这样做的第一个问题是，(cost, t)即使您费力地提供Node对象__lt__和__gt__方法，您也会推动该对。相反，只需推入t堆：

heapq.heappush(openHeap, t)

这需要在其他地方进行一些更改：而不是

openHeap.append((curNode.cost,curNode))
while openSet:
    curNode = heapq.heappop(openHeap)[1]

你必须写

openHeap = [curNode]
while openSet:
    curNode = heapq.heappop(openHeap)

现在，第二个问题（这是我的错——对不起）是如果t已经在，openSet那么我们不应该再次将它添加到堆中。相反，我们应该重新堆化：

t_open = t in openSet
if not t_open or cost < t.cost:
    t.parent = curNode
    t.cost = cost
    if t_open:
        heapq.heapify(openHeap)
    else:
        openSet.add(t)
        heapq.heappush(openHeap, t)

回到调试器输出，回忆一下：

(Pdb) curNode
Node(East, (1, 2), 3.41421356237)

这3.41421356237应该让你担心：成本不应该总是整数吗？看起来成本计算仍然是错误的。它说：

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

但是第三行应该说：

            + self.euclidDist(curNode.pos, t.pos)

所以，有了所有这些修复，让我们再试一次：

>>> Search().aStar((0,0), (2,2))
['North', 'North', 'East', 'East']

回复评论

  1. “翻译怎么打来Search().aStar(...)的？” 我运行了解释器，然后在解释器提示符下输入了那行代码。请参阅教程。

  2. “所以欧几里得距离永远是一。” 是的，如果您在统一成本网格中搜索路径，那么邻居之间的欧几里得距离将始终相同。

  3. “现在想想，curNode.cost - self.manHatDist(curNode.pos, end)总是等于零。” 那是不对的。在您的实现中，cost搜索节点的 是 (i) 从一开始到达该节点的成本，加上(ii) 从该节点到达终点的成本的可接受估计。因此，如果您减去可接受的估计值，那么您应该再次回到 (i)。

于 2013-10-02T10:36:07.867 回答