1

来自 Java，我正在尝试在 python 中实现A* 算法，但我无法对图中 f 分数相等的顶点进行排序。我正在尝试使用 这样做heapq，经过一些调试后，我注意到如果我想推送一个 f 分数等于堆中其他一些预先存在的顶点的顶点，那么顺序就会混乱。我现在正在考虑实施我自己的优先级队列。我想知道这是如何工作的。

行为说明如下：

>>> mylist = [1, 2, 5, 4, 3]
>>> heapq.heapify(mylist)
>>> mylist
>>> [1, 2, 3, 4, 5]
>>> heapq.heappush(mylist, 1)
>>> mylist
>>> [1, 2, 1, 4, 5, 3]

这是我为上下文实现的实际代码：

class Node(object):

def __init__(self, name, x_coordinate, y_coordinate, obstacle_flag=False):
    self.name = name  # possible values should only be ' ', 'A-Z', '*'
    self.coordinates = (x_coordinate, y_coordinate)  # this will uniquely identify the node
    self.obstacle = obstacle_flag  # if the name is '*' the obstacle is set to True
    self.neighbors = {}  # list of neighbors of this node
    self.set_obstacle()

...

class Vertex(Node):
def __init__(self, name, x_coordinate, y_coordinate, obstacle_flag):
    super(Vertex, self).__init__(name, x_coordinate, y_coordinate, obstacle_flag)
    self.g_actual_cost = 10000  
    self.h_cost = 0  # the cost given by the heuristic function
    self.previous_vertex = None
    self.total_cost = self.g_actual_cost + self.h_cost

def __lt__(self, other):
    return self.total_cost < other.total_cost

def __eq__(self, other):
    if isinstance(other, Vertex):
        return self.total_cost == other.total_cost
    return NotImplemented
4

2 回答 2

2

顺序没有乱。堆应该具有所有索引：

a[i] <= a[2*i + 1]
a[i] <= a[2*i + 2]

这并不意味着数组已排序。在您的情况下，堆不变式仍然得到满足，您可以将其作为优先级队列使用。

>>> heap = [1, 2, 1, 4, 5, 3]
>>> import heapq
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
2
>>> heap
[3, 4, 5]
于 2020-12-04T00:43:48.257 回答
2

“堆”并不意味着“排序”（如果是，您无法及时为任意值构建它O(n)）。这意味着它满足堆不变量，对于像 Python 这样的最小堆，这只是意味着最小值在顶部（如果有平局，则任意值获胜），并且每个节点的子节点总是等于或大于比节点。i通过查看 index2*i+1和，您可以在 index 处找到节点的子节点2*i+2，因此在您的示例中，将P每个父节点及其每个子节点放在下面C，我们有：

[1, 2, 1, 4, 5, 3]
#P  C  C
#0  1  2

[1, 2, 1, 4, 5, 3]
#   P     C  C
#   1     3  4

[1, 2, 1, 4, 5, 3]
#      P        C
#      2        5  (only one child since heap lacks another element)

如您所见，在每种情况下，该P值都小于或等于其所有子项；保持堆不变，这是 , 等继续工作所必需heappop的heappush。

请注意，对于像您的Vertex类这样的对象，比较基于一个值，但对象具有其他状态，堆是不稳定的；两个相同的对象total_cost可以按任意顺序出现，无论哪个先放在堆中。为避免此问题，您必须通过“装饰”每个值来添加自己的后备比较。一个简单的方法是：

 from itertools import count

 original_list = [Vertex(...), Vertex(...), ...]  # Define initial list of vertices
 numbermaker = count()
 decorated_list = [(v, next(numbermaker)) for v in original_list]
 heapq.heapify(decorated_list)

 # When you want to add new elements:
 heapq.heappush(decorated_list, (Vertex(...), next(numbermaker)))

 # When you want to get the top of the heap's value:
 top = decorated_list[0][0]  # First [0] gets decorated top, second strips decoration

 # When you want to pop off the top:
 top = heapq.heappop(decorated_list)[0]
于 2020-12-04T00:51:40.313 回答