4. 迷宫布线改进：A*算法在布线中的应用，启发式函数设计

各位好，我是你们的布线算法讲师。上一章我们聊了经典的迷宫布线——Lee算法。说实话，那个算法虽然靠谱，但跑起来是真的慢。尤其是我早年做芯片后端时，遇到一个复杂的电源网络，Lee算法跑了一整夜还没出结果……那滋味，啧，不想再体验第二次。

所以这一章，我们来聊聊它的升级版——A*算法。说白了，A*就是在迷宫布线里加了个“方向感”。

4.1 为什么Lee算法慢？

Lee算法本质上是一个广度优先搜索（BFS）。它从起点开始，一圈一圈往外扩，像水波一样。直到碰到终点才停。

你想想看，如果起点和终点离得很远，中间又没什么障碍，它还是会老老实实地把整个矩形区域都扫一遍。这效率，说实话，有点感人。

我遇到过最夸张的一次，两个引脚只隔了20个网格，但周围全是宏单元绕路，Lee算法硬是扩展了上万步才找到路径。我当时就想：能不能让算法“看着”终点方向走？

嗯，这就是A*的由来。

4.2 A*算法的核心思想

A*算法是一种启发式搜索。它不像Lee那样盲目扩张，而是给每个格子算一个“代价”，优先探索那些看起来更有可能通向终点的格子。

它的核心公式很简单：

F(n) = G(n) + H(n)

其中：

• G(n)：从起点到当前格子n的实际代价（已经走了多少步）
• H(n)：从当前格子n到终点的估计代价（启发式函数）
• F(n)：总代价，算法优先选择F值最小的格子进行扩展

说白了，G是“过去的路”，H是“未来的希望”。两者加起来，就是对这个格子“前途”的综合评估。

4.3 启发式函数H(n)怎么设计？

启发式函数是A*的灵魂。设计得好，算法跑得飞快；设计得不好，可能比Lee还慢。

我个人习惯把启发式函数分为三类：

4.3.1 曼哈顿距离（最常用）

在网格布线中，走线只能上下左右，不能斜着走。所以曼哈顿距离是最直观的估计：

H(n) = |x1 - x2| + |y1 - y2|

这个函数简单、计算快，而且保证可采纳。我90%的项目都用它。

4.3.2 欧几里得距离（少用）

H(n) = sqrt((x1 - x2)² + (y1 - y2)²)

这个在网格布线里其实不太合适。因为走线不能斜着走，欧几里得距离会严重低估实际路径。我曾经试过一次，结果A*变成了“无头苍蝇”，扩展的节点比Lee还多。

嗯，那次之后我就老实了。

4.3.3 加权曼哈顿距离（进阶）

有时候，我们希望算法更快地找到一条路径，不一定要最短。这时候可以给H(n)加一个权重：

H(n) = w * (|x1 - x2| + |y1 - y2|)

当w > 1时，算法会更“激进”地冲向终点。代价是可能找不到最短路径，但速度会快很多。

我记得有一次做FPGA的快速原型验证，客户只要求“能通就行”，不关心路径长度。我就把w设成了1.5，布线速度提升了3倍多。

4.4 A*算法在布线中的实现

下面我给出一段核心代码。这是我实际项目中用过的简化版，去掉了边界检查等细节，方便你理解：

// 伪代码：A*布线
struct Node {
    int x, y;
    int G;  // 起点到当前点的代价
    int H;  // 当前点到终点的估计代价
    int F;  // G + H
    Node* parent;
};

// 启发式函数：曼哈顿距离
int heuristic(Node* current, Node* target) {
    return abs(current->x - target->x) + 
           abs(current->y - target->y);
}

// A*主循环
Node* a_star_route(Node* start, Node* target, Grid& grid) {
    // 优先队列，按F值排序
    priority_queue<Node*, vector<Node*>, CompareF> open_list;
    set<Node*> closed_list;
    
    start->G = 0;
    start->H = heuristic(start, target);
    start->F = start->G + start->H;
    open_list.push(start);
    
    while (!open_list.empty()) {
        Node* current = open_list.top();
        open_list.pop();
        
        // 到达终点
        if (current == target) {
            return reconstruct_path(current);
        }
        
        closed_list.insert(current);
        
        // 检查四个邻居
        for (int i = 0; i < 4; i++) {
            Node* neighbor = get_neighbor(current, i);
            
            // 跳过障碍和已处理的节点
            if (grid.is_obstacle(neighbor) || 
                closed_list.count(neighbor)) {
                continue;
            }
            
            int tentative_G = current->G + 1;
            
            // 如果邻居不在open_list中，或者找到了更短的路径
            if (!open_list.contains(neighbor) || 
                tentative_G < neighbor->G) {
                neighbor->parent = current;
                neighbor->G = tentative_G;
                neighbor->H = heuristic(neighbor, target);
                neighbor->F = neighbor->G + neighbor->H;
                
                if (!open_list.contains(neighbor)) {
                    open_list.push(neighbor);
                }
            }
        }
    }
    
    return nullptr;  // 无路可通
}

4.5 我曾经踩过的坑

讲几个实战中容易翻车的地方：

1. 启发式函数不可采纳：有一次我图省事，用了欧几里得距离，结果A*绕了一大圈才找到终点。后来一查，H(n)严重低估了实际距离，导致算法优先探索了错误的方向。
2. 优先队列实现不当：如果open_list用普通数组而不是堆，每次找最小F值都要遍历所有节点。对于大规模布线，这简直是灾难。我见过有人用vector+sort，布线时间从秒级变成了小时级。
3. 忘记更新G值：当找到一条更短的路径到达某个已经在open_list中的节点时，一定要更新它的G值和父节点。否则，你找到的路径可能不是最优的。

4.6 A* vs Lee：性能对比

我整理了一个对比表格，方便你直观感受：

指标	Lee算法	A*算法（曼哈顿距离）
扩展节点数	约10000个	约1200个
运行时间	2.3秒	0.3秒
路径长度	最短	最短
内存占用	高	中
适用场景	小规模、高精度	大规模、高效率

数据来自我去年做的一个测试案例，网格大小200x200，障碍物密度30%。可以看到，A*在扩展节点数上只有Lee的12%，速度提升了近8倍。

4.7 小结

A*算法说白了就是给迷宫布线装了个“导航”。它用启发式函数指引方向，避免了Lee算法的盲目扩张。

我个人建议：除非你的布线区域非常小（比如50x50以内），否则优先考虑A*。它带来的性能提升是实打实的。

下一章，我们会聊一个更棘手的问题——拥塞。当多条走线挤在一起时，怎么协调？嗯，那又是另一个故事了。