摘要: 集成电路（ IC ）一直在迅猛发展。制造工艺由超深亚微米（ VDSM ）进入到纳米（ nanometer ）阶段，作为物理设计（ physical design ）重要阶段之一的布线（ routing ），其算法研究与工具设计面临新的挑战。最小直角 Steiner 树（ RSMT ）构造问题是布线中的一个基础问题，它以线长最短为目标。 Garey 和 Johnson 证明了 RSMT 问题是一个 NP-Complete 问题，这说明不存在多项式时间求解精确解的算法。好的布线树可以在布线中起到良好的支持作用，从而在较短的时间内得到较优的布线结果。因此，需要有效的布线树构造算法在运行时间和性能上尽可能同时达到优化。 本文根据蚁群优化策略（ ACO ），提出了一个 RSMT 的构造算法，称为 ACO-Steiner 。开始，为给定的端点构造 Hanan 网格。然后，再在每个端点上放置一只蚂蚁。每只蚂蚁每次在 Hanan 网格的一条边上移动，并通过下面介绍的策略决定下一个到达的结点。即：每只蚂蚁各自维护一个访问结点列表，记录已经访问过的结点，以此避免重复访问同一个结点。当蚂蚁 A 遇到蚂蚁 B ，蚂蚁 A 死亡，并将 A 的访问结点列表中的所有结点加入到 B 的访问结点列表中。每步移动完成后，蚂蚁会在经过的路线上留下一些信息素，这些信息素也会随着时间的推移蒸发。 随后，我们发现把蚂蚁的移动限制在 Hanan 网格上降低了算法效率。于是采用一种多步移动的加速策略提高算法性能，该策略将蚂蚁严格根据 Hanan 网格移动的限制去掉，允许每只蚂蚁一次移动多格，大大提高了算法性能。 我们在 Sun 工作站上的 Unix 环境下实现了该算法，并将实验结果与当前最快的启发式算法 BGTC 和最好的精确算法 GeoSteiner3.1 做了比较。结果表明， ACO-Steiner 能够在很短的时间内求得高质量的解。 对于实际电路中常见规模的线网（端点个数小于 50 ）， ACO-Steiner 能达到最优解，当端点数目大于 50 的时候， ACO-Steiner 能够将线长控制在精确解的 1% 误差以内，而且保持快的运行速度，而当端点个数为 1000 的时候， geoSteiner3.1 已经不能处理。同时，我们的 ACO-Steiner 能够构造出比 BGTC 更有优的线长结果。 由于我们的 ACO-Steiner 算法本身所具有的优良特性，使得它容易被扩展到其他问题的求解当中，如绕障碍的直角最小 Steiner 树问题，以及减少布线拥挤的总体布线问题等。