python - 在 A*(A 星)算法中实现开集时，使用 min() 获取最小值或对数组进行排序，然后在 Python 中弹出第一个值？

Question

我正在用 Python 实现 A*(A 星)算法。

如您所知，我们有“开放集”，其中包含我们计划探索的节点列表。

在该算法中，我们从开放集中获得具有最低 F(n) 值(估计总成本)的节点。

我们经常使用 PriorityQueue，但出于某种原因，我不明白为什么 PriorityQueue 不获取具有最低值的节点。

所以我创建了一个名为“frontier”的数组列表(Python 中的常规列表)并将“开放集”保留在那里。

有两种方法可以像 PriorityQueue 一样使用它。

currentNode = min(frontier)

从开放集中获取最小值。

或者我们可以在每次向数组中添加新节点时对数组进行排序，然后使用“pop”获取最低值。

#adding a node
frontier.append(someNode)
sorted(frontier)

#taking out the node
currentNode = frontier.pop(0)

哪个更快？

使用 min() 还是先排序再使用 pop() ？

Python 中的“min()”使用什么算法从数组中获取最小值？

Answer 1

这个数据结构s需要执行三个操作，分别是

• 获取具有最低F(n)的元素
• 添加一个元素
• 删除一个元素

最简单的实现方法是有一个普通列表并使用 min(s) 获取最小值或 min(range(len(values)), key=s .__getitem__) 获取索引。

这在 O(n) 中运行，因为它查看每个元素一次。将元素添加到列表末尾的运行时间为 O(1)，从任意索引中删除的运行时间为 O(n)，因为所有连续的元素都需要移动。

每次都对数组进行排序的想法稍差一些，因为排序在 O(n log n) 中运行。您可以通过将 min 元素排序到列表末尾来节省一些时间，可以在 O(1) 中将其删除，但总的来说它会更慢。

最好的解决方案是有一个堆或优先级队列。它在顶部维护最小元素，可以在 O(1) 中检索它，并允许在 O(log n) 中插入和删除元素。