在*搜索中跟踪磁贴

Question

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

我的问题是，我似乎无法正确地跟踪这些瓷砖。每当我的A*需要超过4次移动才能到达end位置时，它就会失败。我确信这与我如何跟踪这些分片有关（同样是Node）我会怀疑问题出在我对python的知识上，是否允许我像在getAdjacentTiles(...)中循环使用allTiles集一样做.apped(tile)？在

Here's a link to the question that led me to this one

生成的错误（有时，仅当A*路径超过约3步时….）

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

来源

^{pr2}$

Answer 1

让我们启动交互式解释器看看能找到什么。（问题中没有给出类的名称，所以我将其命名为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”执行任何操作，因此让我们向Node类添加一个__repr__方法：

^{pr2}$

然后再试一次：

>>> 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 debugger并执行postmortem：

>>> 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弹出两次（因为堆可以有多个相同的项），但只能从openSet中删除一次。相关代码如下所示：

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

第一个问题是，尽管您费尽心思给出了__lt__和{}方法，但还是推送了(cost, t)对。相反，只需将t推到堆上：

heapq.heappush(openHeap, t)

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

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

你得写信了

^{8}$

现在，第二个问题（这是我的错，抱歉），是如果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)

这应该让你担心：成本不应该总是整数吗？看来成本计算还是错的。上面写着：

    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(...)？”我运行解释器，然后在解释器提示符处输入这行代码。See the tutorial。

2. “所以欧几里德距离永远是1。”是的，如果你在一个统一的成本网格中搜索路径，那么相邻之间的欧几里德距离总是相同的。

3. “现在我考虑一下，curNode.cost - self.manHatDist(curNode.pos, end)总是等于零。”这是不对的。在您的实现中，搜索节点的cost是（i）从一开始到达该节点的成本，加上（ii）从该节点到达终点的成本的可接受估计值。所以，如果你减去可容许的估计值，你应该又回到（i）。