The Lee Path Connection Algorithm
- 1 September 1974
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-23 (9) , 907-914
- https://doi.org/10.1109/t-c.1974.224054
Abstract
The Lee path connection algorithm is probably the most widely used method for finding wire paths on printed circuit boards. It is shown that the original claim of generality for the path cost function is incorrect, and a restriction, called the pathconsistency property, is introduced. The Lee algorithm holds for those path cost functions having this property. Codings for the cells of the grid are proposed which will allow the correct operation of the algorithm under the most general path cost function, using the minimum number of states possible, six states per cell. Then methods for reducing the number of calculations by increasing the number of states are presented.Keywords
This publication has 9 references indexed in Scilit:
- Automation of etching-pattern layoutCommunications of the ACM, 1971
- The minimum route problem for networks with turn penalties and prohibitionsTransportation Research, 1969
- Bi-Directional and Heuristic Search in Path Problems [Thesis]Published by Office of Scientific and Technical Information (OSTI) ,1969
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968
- A Modification of Lee's Path Connection AlgorithmIEEE Transactions on Electronic Computers, 1967
- Topographic simulation as an aid to printed circuit board designPublished by Association for Computing Machinery (ACM) ,1967
- An Algorithm for Path Connections and Its ApplicationsIEEE Transactions on Electronic Computers, 1961
- On finding minimum routes in a network with turn penaltiesCommunications of the ACM, 1961
- A note on two problems in connexion with graphsNumerische Mathematik, 1959