0

我正在研究 Python 中的 A* 路径查找算法，并将数据很好地放入具有此 dtype 的 2D NumPy 数组中：

numpy.dtype([
  ('open', bool),
  ('closed', bool),
  ('parent', object),
  ('g', int),
  ('f', int)
])

按照维基百科的“A* 搜索算法”条目中的伪代码，我需要解释一下：

current := the node in openset having the lowest f_score[] value

该位将为我提供最低“f”值的索引（工作数组定义为 pathArray）：

numpy.unravel_index(numpy.argmin(pathArray['f']), pathArray['f'].shape)

...并且这一位将找到“打开”为 True 的所有索引：

numpy.where(pathArray['open'])

如何将这些条件一起使用，找到“open”为真的最低“f”值？

4

2 回答 2

1

除了使用np.argminon pathArray['f']，您可能还想使用 on pathArray[pathArray['open']]['f']。当然，您必须调整结果，以便可以将其与pathArray['f']...一起使用

另一种方法是pathArray沿'f'字段排序，然后找到第一个pathArray_sorted['open']为“真”的条目。

于 2012-10-04T07:59:19.410 回答
0

我不太熟悉，numpy但我仍然“认为”这不能使用内置函数来完成。但我仍然会尝试解释。这Wikipedia意味着您需要 a 之类的东西priority queue才能做到这一点：

current := the node in openset having the lowest f_score[] value

您需要非常快地完成此操作，我建议构建一个二进制堆并将其用作您的优先级队列。这可以在 python 中轻松完成。这是一篇很好的文章，解释了heaps它们priority queues在 python 中的实现。
祝你好运

于 2012-10-04T05:04:07.340 回答