3. 迷宫布线算法（Lee算法）：基本原理、BFS搜索过程、算法复杂度分析
各位同学，今天我们来聊聊EDA布线里最经典、也最基础的一个算法——迷宫布线算法，也就是大家常说的Lee算法。
说实话，我入行做的第一个布线器，用的就是Lee算法。那时候刚毕业，觉得这算法太简单了，不就是个BFS嘛。结果真上手调起来，才发现坑不少。嗯，今天我就把当年踩过的坑，连同这个算法的精髓，一起讲给你们听。
3.1 基本原理：为什么叫“迷宫”？
你想想看，芯片上密密麻麻的金属层，各种标准单元、宏单元、电源网络……留给布线的空间，是不是就像个迷宫？
Lee算法的核心思想，说白了就是：把布线区域看成一张网格，从起点开始，一层一层往外“波”出去，直到碰到终点。
这个“波”的过程，就是广度优先搜索（BFS）。
核心要点：
- 网格化：将布线区域离散成均匀的网格单元
- 障碍标记：已占用的网格（已有走线、单元引脚等）标记为障碍
- 波传播：从起点开始，逐层向外扩展，每层标记一个波前编号
- 回溯：当波前碰到终点时，从终点反向回溯，找到最短路径
我个人习惯把Lee算法叫做“波传播算法”，因为它的传播过程，真的很像水波扩散。你往平静的水面扔一颗石子，波纹一圈一圈往外扩——Lee算法就是这么干的。
3.2 BFS搜索过程：一步一步来
咱们用一个具体的例子来走一遍流程。假设有一个5x5的网格，起点在(1,1)，终点在(4,4)，中间有个障碍物在(3,3)。
第一步：初始化
把起点标记为波前编号0。所有障碍物标记为-1（不可通过）。其他空闲网格标记为未访问。
网格状态（数字表示波前编号，-1表示障碍）：
[ 0 ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][ -1][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ]
第二步：第一波传播
从起点(1,1)出发，检查它的四个邻居（上、下、左、右）。如果邻居是空闲且未访问，就标记为波前编号1。
第一波后：
[ 0 ][ 1 ][ ][ ][ ]
[ 1 ][ 1 ][ ][ ][ ]
[ ][ ][ -1][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ]
第三步：继续传播
接着处理所有波前编号为1的网格，继续向外扩展。每扩展一层，编号加1。
第二波后：
[ 0 ][ 1 ][ 2 ][ ][ ]
[ 1 ][ 1 ][ 2 ][ ][ ]
[ 2 ][ 2 ][ -1][ ][ ]
[ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ]
就这样一层一层往外扩，直到某一波碰到了终点(4,4)。
我的经验： 在实际项目中，我遇到过波传播到一半，发现终点被障碍物完全包围的情况。这时候算法会跑完整个网格，然后告诉你“无解”。我曾经在一个复杂的芯片设计中，就因为一个电源环把关键路径堵死了，Lee算法跑了整整10分钟才报无解。后来我加了个提前终止条件——如果波前面积超过某个阈值，直接判定无解，省了不少时间。
第四步：回溯路径
当终点被波前碰到时，从终点开始，沿着波前编号递减的方向，反向走回起点。每一步都选择编号减1的邻居，这样走出来的就是最短路径。
回溯路径（用P表示）：
[ P ][ P ][ ][ ][ ]
[ ][ ][ P ][ ][ ]
[ ][ ][ -1][ P ][ ]
[ ][ ][ ][ ][ P ]
[ ][ ][ ][ ][ P ]
3.3 算法复杂度分析：为什么慢？
Lee算法的复杂度，其实很好算。咱们来拆解一下。
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 波传播（BFS） | O(N × M) | O(N × M) |
| 路径回溯 | O(L) | O(1) |
| 整体 | O(N × M) | O(N × M) |
其中N和M是网格的行数和列数，L是路径长度。
你想想看，如果芯片规模很大，比如10000x10000的网格，那Lee算法在最坏情况下要遍历1亿个网格。这还不算完，每个网格还要检查四个邻居……
为什么说Lee算法“慢”？
- 全网格遍历： 最坏情况下，波要扩散到整个网格才能找到终点
- 内存开销大： 每个网格都要存储波前编号，大芯片动辄几GB内存
- 单源单目标： 一次只能布一条线，不能并行
注意： 我曾经在一个项目中，用Lee算法布一条长线，网格是5000x5000，结果跑了将近3分钟。后来我改用A*算法，同样的线只用了不到1秒。所以Lee算法虽然保证找到最短路径，但实际工程中，如果网格太大，建议考虑优化版本或者换算法。
3.4 优缺点总结
说了这么多，咱们来总结一下Lee算法的优缺点。
| 优点 | 缺点 |
|---|---|
| 保证找到最短路径（如果存在） | 时间复杂度高，O(N×M) |
| 实现简单，容易理解 | 内存开销大，需要存储整个网格 |
| 能处理任意形状的障碍物 | 单次只能布一条线 |
| 可以扩展到多层布线 | 对大规模网格效率低 |
我的建议： 如果你刚开始做布线器，先用Lee算法把流程跑通。等后面遇到性能瓶颈了，再考虑优化。比如用双向BFS（从起点和终点同时传播），或者用A*算法加启发式搜索。我当年就是这么一步步过来的。
好了，迷宫布线算法就讲到这里。下一章咱们聊聊A*算法，看看它是怎么在Lee算法基础上“开挂”的。