A*算法节点扩展行为与BFS一致，求问题排查与修复方案

我正在开发一个图搜索算法可视化项目，已经实现了A*算法，但它的节点扩展行为却和BFS算法完全一致。

效果对比 #

• 我的A*节点扩展效果：
• BFS节点扩展效果：
• 期望的A*搜索效果：（参考自一款路径可视化工具）

我的A*算法实现代码 #

async astar(start, target){
    let openList = new PriorityQueue()
    let openListId = []
    let closedList = []
    openList.push(start, 0)
    openListId.push(start.x + "_" + start.y)
    this.setGCost(start.x,start.y, 0)

    while(!openList.isEmpty()){
        let current = openList.dePop().node
        this.removeValueFromArray(openListId, current.x + "_" + current.y)
        closedList.push(current.x + "_" + current.y)
        c.changeRectangleColor(current.x,current.y, "blue")
        await this.sleep(200)
        if(this.isEqual(current,target)){
            return []
        }

        const adjacent = this.getAdjacent(current.x,current.y)
        for(let i = 0;i < adjacent.length;i++){
            let neighbour = adjacent[i].end
            if(closedList.includes(neighbour.x + "_" + neighbour.y) || this.checkWall(neighbour)){
                continue
            }

            let tentative_gSCore = this.getGCost(current.x, current.y) + this.distanceBetween(current,neighbour)

            let tentativeBetter
            if(!openListId.includes(neighbour.x + "_" + neighbour.y)){
                openList.push(neighbour)
                openListId.push(neighbour.x + "_"+ neighbour.y)
                tentativeBetter = true
            }else if(tentative_gSCore < this.getGCost(neighbour.x,neighbour.y)){
                tentativeBetter = true
            }else {
                tentativeBetter = false
            }

            if(tentativeBetter){
                this.setGCost(neighbour.x,neighbour.y,tentative_gSCore)
                this.setHeuristic(neighbour.x,neighbour.y, this.heuristic(neighbour,target))
                let fcost = (this.getGCost(neighbour.x,neighbour.y) + this.getHeuristic(neighbour.x,neighbour.y))
                this.setfScore(neighbour.x,neighbour.y,fcost)
                
            }
        }

    }
    return null
}

问题原因分析 #

A*算法的核心是基于f值（g+h）的优先队列调度，你的代码存在两个关键错误：

1. 优先队列未传入正确优先级：向openList添加节点时，第一次加入neighbour只调用了openList.push(neighbour)，没有传入计算好的fcost作为优先级参数，导致优先队列退化为普通队列，节点按插入顺序取出，行为和BFS完全一致。
2. 节点加入队列的顺序错误：先将节点加入队列，之后才计算fcost，导致初始优先级完全错误。

修复方案 #

1. 调整节点入队顺序，传入正确优先级：先计算fcost，再将节点和fcost一起传入优先队列的push方法。
2. 处理节点更新后的优先级问题：由于多数优先队列实现不支持动态更新节点优先级，可允许重复节点入队，后续处理时如果发现节点已在closedList或有更优的g值，直接跳过即可。

修改后的核心代码片段：

let tentativeBetter
// 先判断是否需要更新，再处理入队逻辑
if(!openListId.includes(neighbour.x + "_" + neighbour.y)){
    tentativeBetter = true
}else if(tentative_gSCore < this.getGCost(neighbour.x,neighbour.y)){
    tentativeBetter = true
}else {
    tentativeBetter = false
}

if(tentativeBetter){
    this.setGCost(neighbour.x,neighbour.y,tentative_gSCore)
    const hValue = this.heuristic(neighbour,target)
    this.setHeuristic(neighbour.x,neighbour.y, hValue)
    let fcost = tentative_gSCore + hValue
    this.setfScore(neighbour.x,neighbour.y,fcost)
    
    // 传入fcost作为优先级，加入优先队列
    openList.push(neighbour, fcost)
    if(!openListId.includes(neighbour.x + "_" + neighbour.y)){
        openListId.push(neighbour.x + "_"+ neighbour.y)
    }
}

额外注意：需要确认你的PriorityQueue实现是按最小优先级值取出节点（因为A*需要优先扩展f值最小的节点），如果队列是按最大优先级排序，可传入-fcost作为优先级参数。

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