3. 搜索空间剪枝：A*算法的启发函数优化与动态加权策略

各位好，今天我们聊一个实战中特别关键的话题——搜索空间剪枝。说白了，就是让A*算法跑得更快，同时尽量别丢精度。

我记得刚入行那会儿，做一个仓储机器人的路径规划。地图稍微大一点，A*就跑不动了。老板站在我身后，看着那个转圈的loading图标，那眼神我到现在都记得。后来我才明白，问题出在启发函数上。

3.1 启发函数：A*的灵魂

A*算法的核心公式很简单：f(n) = g(n) + h(n)。g(n)是从起点到当前点的实际代价，h(n)是当前点到目标点的估计代价。这个h(n)，就是启发函数。

启发函数的设计，直接决定了搜索效率。我个人的习惯是，先问自己三个问题：

• h(n)是否可采纳？ 即h(n) ≤ 实际代价。如果h(n)高估了代价，A*就退化成贪心算法，可能找不到最优解。
• h(n)是否一致？ 即满足三角不等式。一致性能保证A*第一次扩展节点时就是最优路径。
• h(n)的计算成本高不高？ 如果计算h(n)比扩展节点还慢，那就得不偿失了。

3.2 常见的启发函数优化方法

在实际项目中，我常用的优化手段有这么几种：

3.2.1 曼哈顿距离 vs 欧几里得距离

对于网格地图，曼哈顿距离是最常用的。但如果你允许对角线移动，曼哈顿距离会严重低估实际代价。这时候，我建议用对角距离：

function diagonalDistance(node, goal) {
    let dx = Math.abs(node.x - goal.x);
    let dy = Math.abs(node.y - goal.y);
    let D = 1;      // 直线移动代价
    let D2 = Math.sqrt(2); // 对角线移动代价
    return D * (dx + dy) + (D2 - 2 * D) * Math.min(dx, dy);
}

嗯，这里要注意：D2的值取决于你的移动代价设置。如果对角线移动代价是1.4，那就用1.4。别死记硬背。

3.2.2 打破对称性

你有没有遇到过这种情况？A*在开阔地带来回震荡，明明一条直线就能过去，它非要左右试探。这是因为对称路径太多，启发函数区分不出来。

我曾经在一个仓库项目中吃过这个亏。地图里全是货架，通道笔直，A*跑起来像喝醉了酒。后来我加了一个小技巧——微调启发函数：

function breakingTies(node, goal) {
    let h = diagonalDistance(node, goal);
    // 加一个微小的偏移量，打破对称性
    let p = 1 / 25;  // p值通常取 1/25 到 1/100
    return h * (1 + p);
}

这个p值不能太大，否则会破坏可采纳性。我一般取1/50左右，效果不错。

3.3 动态加权策略

动态加权，说白了就是让A*在搜索初期更激进，在接近目标时更保守。这个思路来自一个经典论文——ARA*（Anytime Repairing A*）。

我个人的实现方式是这样的：

function weightedAStar(start, goal, map) {
    let w = 2.5;  // 初始权重
    let openSet = new PriorityQueue();
    openSet.push(start, 0);
    
    while (!openSet.isEmpty()) {
        let current = openSet.pop();
        
        if (current === goal) {
            return reconstructPath(current);
        }
        
        // 动态调整权重：距离目标越近，权重越小
        let distToGoal = heuristic(current, goal);
        let maxDist = heuristic(start, goal);
        let ratio = distToGoal / maxDist;
        let dynamicW = 1 + (w - 1) * ratio;
        
        for (let neighbor of getNeighbors(current, map)) {
            let tentativeG = current.g + cost(current, neighbor);
            let f = tentativeG + dynamicW * heuristic(neighbor, goal);
            // ... 更新openSet
        }
    }
}

你看，权重w随着距离目标的比例动态变化。刚开始离得远，权重高，搜索偏向贪心；快到了，权重接近1，保证最优性。

3.4 实战中的取舍

说了这么多，我们来总结一下。在实际项目中，我通常会根据场景选择不同的策略：

场景	推荐策略	预期效果
小地图（< 100x100）	标准A* + 对角距离	秒级响应
中等地图（100x100 ~ 500x500）	动态加权 + 打破对称性	速度提升3-5倍
大地图（> 500x500）	分层A* + 动态加权	速度提升10倍以上
动态障碍物环境	D* Lite + 动态加权	实时重规划

嗯，这个表格是我多年经验总结出来的。你想想看，如果地图只有50x50，你搞什么动态加权？标准A*就够了。别为了炫技而炫技。

3.5 一个完整的优化案例

最后，我分享一个我在AGV调度项目中用过的完整优化方案。这个方案把搜索时间从平均120ms降到了15ms：

1. 启发函数：使用对角距离 + 1/50的对称性打破因子
2. 动态加权：初始权重2.0，按距离比例线性衰减到1.0
3. 剪枝策略：如果当前节点的f值已经超过当前最优解的1.2倍，直接跳过
4. 缓存机制：对频繁查询的路径段，缓存中间结果

说白了，就是多管齐下。每个优化点贡献一点，加起来就是质的飞跃。

好了，这一章就到这里。下一章我们聊聊如何用跳点搜索（JPS）进一步加速A*，那玩意儿在网格地图上简直是神器。