logo标签列表

Python heapq替换优先级

python
10

我正在尝试使用Python的heapq实现Dijkstra算法。如果发现通向该单元格的更短路径，该算法需要更改单元格的值。

我使用以下检查来实现：

if curr_cell[0] + val < prev_cell[0]:  # value of new path is less than old value
    new_cell = (curr_cell[0] + val, prev_cell[1], curr_cell[1])
    heap[index] = new_cell
    heapify(heap)

然而，当在较大的迷宫上运行我的程序时，这需要很长时间，可能是由于heapify()调用造成的。

有没有更有效的方法来改变堆条目的优先级？

5个回答
13

heapq库不能高效地支持更新优先级，因为没有有效的方式来搜索堆。如果你用O(n)时间搜索堆并手动替换元素，然后可以使用_siftup()和_siftdown()函数来恢复堆的不变性。

另外，这里有一个兼容的实现，我写了一个使用字典来允许O(1)查找堆索引的实现。

https://github.com/elplatt/python-priorityq

6
一个可能的解决方案是将条目标记为已删除，并添加一个新的具有修订优先级的条目。 文档 提供了一个示例实现：
pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')
你能帮我理解itertools.count()的用法吗？我不太明白它。 - MarksCode
itertools.count() 简单地生成连续的数字。将计数器添加到类似 [priority, count, task] 的条目中可以确保具有相同优先级的条目按照它们添加的顺序进行处理。我想，对于 Dijkstra 算法，您可以跳过这一步。 - Eugene Yarmash
2
嗨，尤金，我已经在官方文档中检查过了，但我有一个问题。这个实现不会在堆的大小方面成本高昂吗？如果您经常更新优先级，那么这不会使堆的大小非常大吗？是否有一种更有效的方法可以使用heapq的私有方法来完成这项工作？ - Silver
@SilverSlash：是的，它确实可以，但内存很便宜 :) 你也可以使用私有的 _siftup() / _siftdown() 函数在不向堆中插入新项的情况下以 O(log n) 的时间复杂度完成操作，但这需要你维护堆中每个项的位置。 - Eugene Yarmash
1
0
数组的索引需要 O(n) 的时间...使用筛选有什么优势呢？Dijkstra 算法假装有一个 O(log n) 的更新函数。 - Matteo Tosato
-2

heapq提供的heapify()例程需要线性时间。

因此，您应该使用数据结构来更改记录的优先级，并且堆化在O(logn)中发生，而不是每次更改优先级时都要花费O(n)的heapify()。

您可以使用Queue提供的PriorityQueue。

10
PriorityQueue 不支持删除元素或更改优先级。 - Jeff Learman
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接