The Lee path connection algorithm

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 al-gorithm under the most general path cost function, using the mini-mum number of states possible, six states per cell. Then methods for reducing the number of calculations by increasing the number of states are presented. Storing computed cell masses is introduced as a method for reducing the amount of calculation for each iteration of the algorithm. Adding the distance from the goal to the path cost function, and expanding the most recently encountered cell, are shown to sub-stantially reduce the number of iterations needed. Index Terms-Cell coding, heuristic search, Lee algorithm, path cost function, printed circuit board, rectangular grids, shortest path problem, wire routing. I