王永忠， 徐天羿， 李佳骏， 千月欣， 王楷文

(中国民用航空飞行学院 空中交通管理学院， 四川 广汉 618307)

大规模集成电路是利用半导体技术把大量电子元件集成在特定的极小空间或平面内，具有特定功能。由于集成电路内部元器件数目巨大，需要借助电子设计自动化工具(EDA)来完成电路设计与实现[1]。在集成电路设计的多个阶段中，“物理设计”作为其中的重要阶段，需要把器件摆放在合适的位置，然后用金属线连接器件实现连接关系。建立连接关系是EDA工具需要解决的重要问题，简单来说就是“自动布线问题”。在自动布线过程中，因为要考虑金属线的寄生电阻对整条线路性能的影响，所以需要使自动布线长度最小化。

本文的主要目的是在一个横向的自动布线区域内，使用最短最优的路径规划模型，将顶部和底部用金属线经过特定方格进行连接。众所周知，多层电路板上的金属线只能被允许沿着直线或直角(方格)放置，连接特定的方格(引脚)以至于不引起短路或者断路情况的发生[2]，只有当空间相邻电路板层间采用通孔连接的时候，共用方格才不会导致短路或断路，否则不能同时占用一个方格。连接过程中，要求整体连接路径最短，互不交叉，用金属线将相应的引脚连通起来。假设“上引脚坐标”和“下引脚坐标”的第i个数分别为ai和bi，它们表示需要连接第1行的第ai个格点与第n行的第bi个格点。

1 自动布线建模

1.1 自动布线模型理论介绍

Dijkstra算法[2]最早于1959年提出，用于找到指定的两个节点相互之间的最短路径，也可用于从指定点到剩下各点的最短距离，此算法目前为止被认为是求解无权网络最短路问题的最佳方案。……