A*在Python优先级队列中搜索

Question

我正在尝试写一个A*搜索来解决Python中的迷宫，但是我正在努力寻找一个内置的优先级队列来解决这个问题。我现在使用的是PriorityQueue，但它没有提供更改项目优先级的功能，这是算法底部注释部分的一个问题(在else if语句中)。

有没有人知道我可以在else if块中做什么，或者什么内置的优先级队列可以给我提供这个功能？

def A_search(maze, start, end):
expanded = 0 # use to track number of nodes expanded by the algorithm
node1 = Node(start,0)
frontier = PriorityQueue()
frontier.put((dist_to_goal(node1,end) + node1.get_cost(), node1))
visited = []
in_frontier = [] # keep track of items in frontier, PriorityQueue has no way to peek
in_frontier.append(node1)
while(True):
    if(frontier == []):
        return(None,expanded)
    curr = (frontier.get())[1]
    in_frontier.remove(curr)
    expanded += 1
    if(curr.get_loc() == end):
        return(curr,expanded)
    visited.append(curr.get_loc())
    neighbors = find_neighbors(maze, curr.get_loc())
    for neighbor in neighbors:
        node_n = Node(neighbor,node1.get_cost()+1)
        node_n.parent = curr
        if(neighbor not in visited) and (node_n not in in_frontier):
            frontier.put((dist_to_goal(node_n,end) + node1.get_cost(), node_n))
            in_frontier.append(node_n)
        # else if node_n is in frontier w/ a higher path cost then replace it w/ current

Answer 1

在内置库中，您会发现最接近的是heapq。

更改优先级后，您需要调用heapq.heapify (耗费O(n)时间，但不会更改A*总体复杂性)或在O(log )时间使用内部heapq._siftdown函数。

Answer 2

更新项目优先级，在python官方文档中关于heapq模块的优先级队列实现说明中进行了讨论：https://docs.python.org/3.7/library/heapq.html#priority-queue-implementation-notes使用这些说明，我设法编写了我自己的PriorityQueue实现，它支持添加任务并更新它的优先级(如果存在)。它包括使用指向优先级队列中的任务的entry_finder dict。更新任务的优先级，简单地说就是将现有任务标记为已删除，并使用新的优先级插入它。在此实现中，您可以使用方法add_task

class PriorityQueue():
    REMOVED = '<removed-task>'
    def __init__(self):
        self.pq = []
        self.entry_finder = {}
        self.counter = itertools.count()


    def add_task(self, task, priority=0):
        if task in self.entry_finder:
            self.remove_task(task)
        count = next(self.counter)
        entry = [priority, count, task]
        self.entry_finder[task] = entry
        heappush(self.pq, entry)

    def remove_task(self, task):
        entry = self.entry_finder.pop(task)
        entry[-1] = self.REMOVED

    def pop_task(self):
        while self.pq:
            priority, count, task = heappop(self.pq)
            if task is not self.REMOVED:
                del self.entry_finder[task]
                return task
        return None