Some Variations of Lee's Algorithm
- 1 January 1976
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-25 (1) , 19-24
- https://doi.org/10.1109/tc.1976.5009200
Abstract
Lee's algorithm is a pathfinding algorithm, which is often used in computer-aided design systems to route wires on printed circuit boards. This paper discusses some variations of Lee's algorithm which can be used in certain contexts to improve its efficiency. First, it is shown that, by storing frontier cells in an array of stacks rather than a single list, costly searching operations can be eliminated without significantly increasing storage requirements. Second, it is shown that if each path's cost is the sum of the weights of its cells then retrace codes can be assigned to cells as soon as they are reached rather than when they are expanded. Third, it is shown that if the additional restriction is made that each cell's weight is not a function of the state of any nonneighbor cell, then an encoding scheme requiring only two bits/cell can be used for both rectangular and hexagonal grids.Keywords
This publication has 5 references indexed in Scilit:
- Correction to ``The Lee Path Connection Algorithm''IEEE Transactions on Computers, 1976
- The Lee Path Connection AlgorithmIEEE Transactions on Computers, 1974
- A Modification of Lee's Path Connection AlgorithmIEEE Transactions on Electronic Computers, 1967
- An Algorithm for Path Connections and Its ApplicationsIEEE Transactions on Electronic Computers, 1961
- A note on two problems in connexion with graphsNumerische Mathematik, 1959