A solution to line routing problems on the continuous plane
A solution to line routing problems on the continuous plane
复制标题
DOI：
10.1145/62882.62883
复制
发表时间：
1988-06
期刊：
影响因子：
--
通讯作者：
Dave Hightower
中科院分区：
文献类型：
--
作者：
Dave Hightower
本文讨论了一种新的线路布线算法。该算法已在IBM 7094上用FORTRAN Ⅱ编程，在IBM 360/~5上用FORTRAN Ⅳ编程。它在迷宫、印刷电路板、基板、PERT图等布线问题中得到了很好的应用。该算法基于连续平面，与传统的基于离散平面的算法相比，其主要优点有两个方面：1。由于该算法是基于连续平面的，因此理论上对用于描述点的位置的精度程度没有限制。在实践中，唯一限制精度的因素是计算机中可能存储的最大（或最小）数字的大小。因此，例如，印刷电路板上的节点可以以mil精度输入。如果用现有的方法在一块9×9英寸的电路板上完成这项壮举，那么计算机中必须存储（和搜索）81，000，000个细胞的矩阵。2.该算法只存储线段，因此要找到路径，只需要研究当前定义的线段。通常使用传统方法，必须调查位于每个可能的最小路径上的每个单元。最终结果是，该算法比传统方法快得多。
This paper discusses a new linerouting algorithm. The algorithm has been programmed in FORTRAN II for the IBM 7094 and in FORTRAN IV for the IBM 360/~5. It has given good results when applied to many llne-routing problems such as mazes, printed circuit boards, substrates, and PERT diagrams. The main advantages of this algorithm, which is based on the continuous plane, over conventional algorithms based on the discrete plane are twofold: 1. Since the algorithm is based on the continuous plane, there is theoretically no limit to the degree of precision used to describe the position of points. In practice, the only factor restricting the precision is the magnitude of the largest (or smallest) number which may be stored in a computer. As a result, the nodes on a printed circuit board, for example, can be input with mil accuracy. If this feat were to be accomplished by existing methods on a 9×9 inch board, a matrix of 81,000,000 cells would have to be stored (and searched) in the computer. 2. The algorithm stores only line segments~ therefore to find a path, only the segments that are currently defined need be investigated. Usually with conventional methods, every cell that lies on every possible minimal path must be investigated. The net result is that this algorithm is much faster than the conventional method.