1

我正在审查这个堆栈溢出帖子 Python - Speed up an Star Pathfinding Algorithm

我试图确定这条线for tile in graph[current]:代表什么。即graph[]代表什么。我觉得 graph 应该代表整个网格，但我第二次猜测这是因为我们将 current 作为参数提供给 graph 上的 [] 运算符，所以它必须返回一些东西，但我不确定它应该是什么。也许我们可以前往的瓷砖直接与当前相邻？

还有这个语法是什么意思current = heapq.heappop(openHeap)[1]？

import heapq

def aStar(self, graph, current, end):
  openSet = set()
  openHeap = []
  closedSet = set()

  def retracePath(c):
    path = [c]
    while c.parent is not None:
        c = c.parent
        path.append(c)
    path.reverse()
    return path

  openSet.add(current)
  openHeap.append((0,current))
  while openSet:
      current = heapq.heappop(openHeap)[1]
      if current == end:
          return retracePath(current)
      openSet.remove(current)
      closedSet.add(current)
      for tile in graph[current]:
         if tile not in closedSet:
             tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
             if tile not in openSet:
                 openSet.add(tile)
                 heapq.heappush(openHeap, (tile.H,tile))
             tile.parent = current
  return []
4

1 回答 1

0

我相信该graph变量是某种字典，其中键是当前图块，值是所有有效相邻图块的列表。这样，图中的每个节点都可以通过简单的 dict 查找轻松访问。

作者在原始帖子中链接到的 Wikipedia 上的伪代码支持这一假设——功能等效的行被列为for each neighbor in neighbor_nodes(current)

该行current = heapq.heappop(openHeap)[1]所做的是返回文字 tile 对象。如果您观察线openHeap.append((0,current))和heapq.heappush(openHeap, (tile.H,tile))，您可以观察到作者正在添加一个包含两个元素的元组，openHeap其中第一个元素是启发式元素，第二个元素是文字平铺对象。

因此，该行current = heapq.heappop(openHeap)[1]与编写相同：

temp = heapq.heappop(openHeap)
current = temp[1]

...或写作：

h, current = heapq.heappop(openHeap)

函数本身正在做的heaqpq.heappop()是返回堆中的最小元素。据推测，它使用元组中的第一个元素进行索引，因此将返回具有最小启发式的打开图块作为廉价的 O(1) 操作。

于 2013-09-29T17:56:38.250 回答