在*搜索中跟踪图块 [英] Keeping track of tiles in a* search
问题描述
我很难跟踪 getAdjacentTiles(..) 生成的图块.我已经确定了下面的 A* 实现的性能问题是我没有跟踪之前看到的图块，每次调用 getAdjacentTiles 都会返回新的图块(Node's) 而不是 openSet 或 closedSet 中的任何图块.我决定使用 Node 对象列表作为迄今为止创建的所有图块，并将其传递给 getAdjacentTiles 以确定它生成的图块是否已经被访问过.
我的问题是，我似乎无法正确跟踪这些图块.每当我的 A* 需要进行超过 4 次移动才能到达 end 位置时，它就会崩溃.我确定这与我如何尝试跟踪图块有关(再次是 Node 已经访问过)我不得不怀疑这个问题是我对 python 的了解，是当循环遍历 allTiles 集合时，我允许像在 getAdjacentTiles(...) 中那样做 .apped(tile)?
产生的错误(有时，仅当 A* 路径长于大约 3 步时..)
文件P3.py"，第 67 行，在 aStar 中openSet.remove(curNode)KeyError:<__main__.Node 实例在 0xa39edcc>来源
#执行 A* 搜索以找到通往污垢的最佳路径def aStar(self, current, end):开放集 = 集()开放堆 = []关闭集 = 集()allTiles = 设置()curNode = Node(0, current, self.manHatDist(current, end))openSet.add(curNode)allTiles.add(curNode)openHeap.append((curNode.cost,curNode))当 openSet 时:curNode = heapq.heappop(openHeap)[1]如果 curNode.pos == 结束:返回 self.getDirections(curNode)openSet.remove(curNode)closedSet.add(curNode)adjNodes = self.getAdjacentNodes(curNode.pos, allTiles)对于 adjNodes 中的图块:t = 瓷砖如果 t 不在 closedSet 中:成本 = (curNode.cost - self.manHatDist(curNode.pos, end)+ self.euclidDist(curNode.pos, current)+ self.manHatDist(t.pos, end))如果 t 不在 openSet 中或 cost <;成本:t.parent = curNodet.cost = 成本openSet.add(t)heapq.heappush(openHeap, (cost,t))allTiles.add(t)返回 []#获取到达此endNode的动作def getDirections(self, endNode):移动 = []tmpNode = 结束节点而 tmpNode.parent 不是 None:move.append(tmpNode.value)tmpNode = tmpNode.parent移动.反向()返回动作#从给定的瓷砖返回所有可能的移动作为节点对象def getAdjacentNodes(self, curPos, allTiles):allMoves = ['北','南','东','西']posMoves = []对于 allMoves 中的方向:if(self.canMove(direction, curPos)):posMoves.append(Node(direction, self.getLocIfMove(curPos, direction)))retNodes = []对于 posMoves 中的 posLocNode:设置 = 假对于 allTiles 中的 tile:如果(posLocNode.pos == tile.pos):设置 = 真retNodes.append(tile)如果(未设置):retNodes.append(posLocNode)返回 retNodes让我们启动交互式解释器，看看我们能找到什么.(你没有在问题中给出你班级的名字，所以我称之为Search.)
好的，第一个问题是这些 Node 实例不是不言自明的.我们不能对Node instance at 0x104895518"做任何事情，所以让我们在 Node 类中添加一个 __repr__ 方法:
def __repr__(self):返回 'Node({0.value}, {0.pos}, {0.cost})'.format(self)然后再试一次:
<预><代码>>>>Search().aStar((0,0), (2,2))回溯(最近一次调用最后一次):...文件q19128695.py"，第 25 行，在 aStar 中openSet.remove(curNode)KeyError:节点(东，(1, 2)，3.41421356237)好的，这提供了更多信息.让我们启动 Python 调试器 并执行 事后分析:
<预><代码>>>>导入 pdb>>>pdb.pm()>q19128695.py(25)aStar()->openSet.remove(curNode)(Pdb) 开放集设置([节点(北，(2，-1)，6.0)，节点(东，(2，2)，4.65028153987)，节点(西, (-1, 1), 5.0), 节点(北, (0, -1), 5.0),节点(南, (1, 3), 6.65028153987), 节点(南, (0, 3), 6.0),节点(东, (3, 0), 6.0), 节点(西, (-1, 0), 5.0),节点(北, (1, -1), 5.0), 节点(东, (3, 1), 6.65028153987),节点(西, (-1, 2), 6.0)])(Pdb) 封闭集设置([节点(0，(0，0)，4)，节点(南，(2，1)，3.41421356237)，节点(东, (1, 1), 3.0), 节点(南, (0, 1), 3.0),节点(东, (2, 0), 3.0), 节点(东, (1, 0), 3.0),节点(东, (1, 2), 3.41421356237), 节点(南, (0, 2), 3.0)])(Pdb) curNode节点(东, (1, 2), 3.41421356237)(Pdb) 在 closedSet 中的 curNode真的所以节点已经关闭了.这怎么会发生?好吧，如果节点被添加到 openSet 和 openHeap 两次，就会发生这种情况.然后它会从 openHeap 弹出两次(因为堆可以有多个相同的项目)，但它只能从 openSet 中删除一次.有问题的代码如下所示:
if t 不在 openSet 或 cost <;成本:t.parent = curNodet.cost = 成本openSet.add(t)heapq.heappush(openHeap, (cost,t))这个问题的第一个问题是，即使你已经不厌其烦地给你的 Node 对象 推送了对 和 (cost, t)>__lt____gt__ 方法.相反，只需将 t 推入堆:
heapq.heappush(openHeap, t)这需要在其他地方进行一些更改:而不是
openHeap.append((curNode.cost,curNode))当 openSet 时:curNode = heapq.heappop(openHeap)[1]你必须写
openHeap = [curNode]当 openSet 时:curNode = heapq.heappop(openHeap)现在，第二个问题(这是我的错——抱歉)，如果 t 已经在 openSet 中，那么我们不应该再次将它添加到堆中.相反，我们应该重新堆肥:
t_open = t 在 openSet如果不是 t_open 或 cost <;成本:t.parent = curNodet.cost = 成本如果 t_open:heapq.heapify(openHeap)别的:openSet.add(t)heapq.heappush(openHeap, t)回到调试器输出，回忆一下:
(Pdb) curNode节点(东, (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))['北'，'北'，'东'，'东']回复评论
你是如何从解释器中调用
Search().aStar(...)的?"我运行了解释器，然后在解释器提示下输入了那行代码.查看教程.所以欧几里得距离永远是一."是的，如果您在统一成本网格中搜索路径，那么邻居之间的欧几里得距离将始终相同.
现在想想，
curNode.cost - self.manHatDist(curNode.pos, end)总是等于零."那是不对的.在您的实现中，搜索节点的cost是 (i) 从一开始就到达该节点的成本，加上 (ii) 对到达成本的可接受估计从那个节点结束.所以如果你减去可接受的估计，那么你应该再次回到(i).
I am having a hard time keeping track of the tiles generated by getAdjacentTiles(..). I have identified the performance issue of my A* implementation below is that I do not keep track of the tiles that have seen before, every call to getAdjacentTiles returns new tiles (Node's) and not any of the tiles in openSet or closedSet. I decided to use a list of Node objects as all of the tiles created so far, and pass that to getAdjacentTiles to determine if a tile it produces has already been visited.
My problem is, that I cannot seem to keep track of these tiles properly. Whenever my A* needs to take more than about 4 movements to get to the end location it craps out. Which I am sure has to do with how I am trying to keep track of the tiles (again Node's that have been visited) I would have to suspect the issue is with my knowledge of python, am I allowed to do .apped(tile) like I do in getAdjacentTiles(...) when looping through the allTiles set?
Here's a link to the question that led me to this one
The error generated (sometimes, only when the A* path is longer than about 3 steps..)
File "P3.py", line 67, in aStar
openSet.remove(curNode)
KeyError: <__main__.Node instance at 0xa39edcc>
Source
#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
Let's fire up the interactive interpreter and see what we can find. (You didn't give the name of your class in the question, so I've called it 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, the first problem is that these Node instances are not self-explanatory. We can't do anything with "Node instance at 0x104895518", so let's add a __repr__ method to the Node class:
def __repr__(self):
return 'Node({0.value}, {0.pos}, {0.cost})'.format(self)
and try again:
>>> 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, that's more informative. Let's fire up the Python debugger and do a 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
So the node has already been closed. How could this have happened? Well, it could happen if the node had been added to openSet and openHeap twice. It would then be popped from openHeap twice (because heaps can have multiple identical items), but it can only be removed from openSet once. The code in question looks like this:
if t not in openSet or cost < t.cost:
t.parent = curNode
t.cost = cost
openSet.add(t)
heapq.heappush(openHeap, (cost,t))
The first problem with this, is that you push the pair (cost, t) even though you've gone to the trouble to give your Node objects __lt__ and __gt__ methods. Instead, just push t onto the heap:
heapq.heappush(openHeap, t)
This requires a couple of changes elsewhere: instead of
openHeap.append((curNode.cost,curNode))
while openSet:
curNode = heapq.heappop(openHeap)[1]
you'll have to write
openHeap = [curNode]
while openSet:
curNode = heapq.heappop(openHeap)
Now, the second problem (which is my fault—sorry), is that if t is already in openSet then we shouldn't add it to the heap again. Instead, we should re-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)
Going back to the debugger output, recall this:
(Pdb) curNode
Node(East, (1, 2), 3.41421356237)
That 3.41421356237 should be worrying you: shouldn't the cost always be an integer? It looks as though the cost calculation is still wrong. It says:
cost = (curNode.cost
- self.manHatDist(curNode.pos, end)
+ self.euclidDist(curNode.pos, current)
+ self.manHatDist(t.pos, end))
but that third line should say:
+ self.euclidDist(curNode.pos, t.pos)
So, with all those fixes in place, let's try again:
>>> Search().aStar((0,0), (2,2))
['North', 'North', 'East', 'East']
Replies to comments
"How did you call
Search().aStar(...)from the interpreter?" I ran the interpreter and then typed in that line of code at the interpreter prompt. See the tutorial."So the Euclidean distance will always be one." Yes, if you're searching for paths in a uniform-cost grid, then the Euclidean distance between neighbours will always be the same.
"Now that I think about it,
curNode.cost - self.manHatDist(curNode.pos, end)is always equal to zero." That's not right. In your implementation, thecostof a search node is (i) the cost of reaching that node from the start, plus (ii) an admissible estimate of the cost of reaching the end from that node. So if you subtract the admissible estimate then you should get back to (i) again.
这篇关于在*搜索中跟踪图块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
