一种有效的两端线网布线方法

摘要

提出了一种基于计算几何学的面向两端线网的布线算法。对于给定的布线平面，该算法首先根据障碍情况构造了包含最短路径信息的强连接图，然后引入绕障碍长度作为参数，以决定搜索走向，算法保证能找到最短布线路径，并使其时空复杂度得到了极大的改善。