在*搜索中跟踪磁贴 [英] Keeping track of tiles in a* search
问题描述
我很难跟踪getAdjacentTiles(..)生成的图块.我已经确定了下面我的A *实现的性能问题是，我没有跟踪以前看到的图块，每次对getAdjacentTiles的调用都会返回新的图块(Node)，而不是其中的任何图块openSet或closedSet.我决定使用Node对象的列表作为到目前为止创建的所有图块，并将其传递给getAdjacentTiles以确定它生成的图块是否已经被访问过.
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.
我的问题是，我似乎无法正确跟踪这些磁贴.每当我的A *需要进行约4次以上的动作才能到达end位置时，它都会突然消失.我确定这与我试图跟踪磁贴(再次访问的Node)有关.我不得不怀疑问题出在我对python的了解上，我是否可以做<像我在getAdjacentTiles(...)中循环遍历allTiles设置时所做的那样?c
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?
生成的错误(有时，仅当A *路径的长度超过大约3个步骤时..)
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>
来源
#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.)
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>
好的，第一个问题是这些Node实例不是不言自明的.我们无法对"0x104895518处的节点实例"执行任何操作，因此让我们在Node类中添加__repr__方法:
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)
，然后重试:
>>> 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调试器，然后执行
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
因此该节点已经关闭.这怎么可能发生?好吧，如果将节点两次添加到openSet和openHeap中，可能会发生.然后将从openHeap弹出两次(因为堆可以包含多个相同的项)，但是只能从openSet删除一次.有问题的代码如下:
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))
第一个问题是，即使麻烦给Node对象__lt__和__gt__方法，也要推入对(cost, t).相反，只需将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]
你必须写
openHeap = [curNode]
while openSet:
curNode = heapq.heappop(openHeap)
现在，第二个问题(对不起，这是我的错)是，如果openSet中已经存在t，那么我们就不应再将其添加到堆中.相反，我们应该重新堆砌:
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)
那个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))
但是第三行应该说:
+ 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']
回复评论
-
您是如何从口译员那里呼叫
Search().aStar(...)的?"我运行了解释器，然后在解释器提示符下键入了这一行代码. 参见教程.
"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.
现在考虑一下，curNode.cost - self.manHatDist(curNode.pos, end)始终等于零."那是不对的.在您的实现中，搜索节点的cost是(i)从起点到达该节点的成本，加(ii)从该节点到达终点的成本的可接受估计.因此，如果您减去可接受的估算值，则应再次返回(i).
"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, the cost of 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屋！
