python - Python 优先级队列中的 A* 搜索

Question

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

有人知道我可以在 else if block 中做什么，或者内置的优先级队列可以为我提供此功能吗？

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* 整体复杂性)或使用内部 heapq._siftdown code> 函数的时间复杂度为 O(log n)。