跟踪瓷砖在*搜索(Keeping track of tiles in a* search)

我有所产生的瓷砖很难保持跟踪getAdjacentTiles(..) 我已经确定我的A *实现的性能问题，下面是我不保持之前已经看到了瓷砖的跟踪了解，向每一个电话getAdjacentTiles返回新砖（ Node的），而不是任何的瓷砖openSet或closedSet 。我决定使用Node对象的列表，所有创建至今的瓷砖，并传递到getAdjacentTiles以确定它是否产生了瓷砖已被访问。

我的问题是，我似乎无法跟踪这些砖正常。每当我的A *需要采取比约4动作更加才能到end就胡扯出来的位置。这我相信有我怎么想跟踪瓷砖（再次做Node ，我将不得不怀疑问题是与我的Python的知识已被访问的），我是允许做.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

让我们火起来的交互式解释，看看我们能找到。（你没有给你的问题类的名称，所以我把它叫做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>

OK，第一个问题是，这些Node实例不言自明。我们不能“以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)

OK，这就是更多的信息。让我们火了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那么我们不应该再次加入到堆。相反，我们应该重新heapify：

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']

答复意见

“你怎么调用Search().aStar(...)来自解释？” 我跑了解释，然后在提示符的解释该行的代码类型。参见教程。
“因此，欧氏距离将永远是一个。” 是的，如果你在一个统一的成本网格搜索路径，然后邻国之间的欧几里得距离始终是相同的。
“现在想起来， curNode.cost - self.manHatDist(curNode.pos, end)总是等于零。” 那是不对的。在您的实现中， cost的搜索节点为（i）达到从一开始就知道节点的成本，加上（II）达到从该节点结束的成本可容许估计。所以，如果你减去容许估计，那么你应该回去（我）一次。