在 A*（A 星）算法中实现开集时使用 min() 获取最小值或对数组进行排序然后弹出 Python 中的第一个值？
Using min() to get minimum value or sort the array and then pop the first value in Python when implementing open set in A* (A star) algorithm?
我正在 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()”使用什么算法从数组中获取最小值？
这个数据结构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).
中插入和删除元素
我正在 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()”使用什么算法从数组中获取最小值？
这个数据结构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).