建筑疏散项目中Best First算法的队列排序实现疑问

问题背景 #

我正在建筑疏散项目中实现Best First算法，建筑包含4层楼、屋顶及0层，通过go_to_roof等函数控制电梯移动，目标是让电梯停在屋顶且所有居民完成疏散。

已实现BFS、DFS遍历逻辑，运行BFS可得到目标状态。针对Best First算法，已选定启发式准则为计算state[1:5]的和（state[-1]为电梯所在楼层，state[1]-state[5]为各楼层及屋顶的居民数），并完成expand_front函数中BEFS的排序逻辑，但不清楚在extend_queue函数中该如何处理队列的排序。

核心代码 #

状态转换示例函数 #

def go_to_floor1(state):
    if state[-1]<8 and state[1]>0:
        if state[1]>8-state[-1]:
            new_state = [1] + [state[1] + state[-1] - 8] + [state[2]] + [state[3]] + [state[4]] + [8]
        else:
            new_state = [1] + [0] + [state[2]] + [state[3]] + [state[4]] + [state[1] + state[-1]]
        return new_state

启发式函数 #

def sum_state(state):
        return sum(state[1:5])

expand_front函数（已确认BEFS逻辑正确） #

def expand_front(front, method):  
    if method=='DFS':        
        if front:
            print("Front:")
            print(front)
            node=front.pop(0)
            for child in find_children(node):     
                front.insert(0,child)
                
    elif method=='BFS':
        if front:
            print("Front:")
            print(front)
            node=front.pop(0)
            for child in find_children(node):     
                front.append(child)

    elif method == 'BEFS':
        if front:
            print("Front:")
            print(front)
            node = front.pop(0)
            for child in find_children(node):
                front.insert(0,child)
                front.sort(key=sum_state) 
                
    return front

extend_queue函数（BEFS部分待确认） #

def extend_queue(queue, method):
    # ...其他方法实现...
    elif method == 'BEFS':
        print("Queue:")
        print(queue)
        node = queue.pop(0)
        queue_copy = copy.deepcopy(queue)
        children = find_children(node[-1])
        for child in children:
            path = copy.deepcopy(node)
            path.append(child)
            queue_copy.append(path)
            queue_copy.sort(key=sum_state)
    
    return queue_copy

问题分析与修正建议 #

当前extend_queue的BEFS实现存在两个关键问题：

1. 排序对象错误：队列中的元素是完整路径（如[初始状态, 状态1, 当前状态]），而sum_state函数接收的是单个状态。直接用sum_state作为排序key会导致错误，应该取路径的最后一个元素（当前状态）来计算启发值。
2. 排序效率低下：每次添加一个子节点就排序一次，没必要，应该先把所有子节点对应的路径都添加到队列后，再进行一次整体排序。

修正后的extend_queue BEFS部分代码如下：

elif method == 'BEFS':
    print("Queue:")
    print(queue)
    node = queue.pop(0)
    queue_copy = copy.deepcopy(queue)
    children = find_children(node[-1])
    # 先批量添加所有子路径
    for child in children:
        path = copy.deepcopy(node)
        path.append(child)
        queue_copy.append(path)
    # 按路径最后一个状态的启发值升序排序（剩余居民越少越优先）
    queue_copy.sort(key=lambda x: sum_state(x[-1]))

补充说明 #

Best First搜索的核心是每次优先选择启发值最优（这里是剩余居民数最少）的节点进行扩展，因此队列需要始终保持按启发值升序排列。修正后的代码确保了：

• 排序时正确使用路径的当前状态计算启发值
• 减少排序次数，提升效率
• 队列始终维持正确的优先级顺序，保证每次取出的是当前最优节点

内容的提问来源于stack exchange，提问作者luffypilled