Some Variations of Lee´s Algorithm

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.