Lee algorithm
The Lee algorithm is one possible solution for maze routing problems based on breadth-first search. It always gives an optimal solution, if one exists, but is slow and requires considerable memory.
Algorithm
1) Initialization
- Select start point, mark with 0 - i := 0
2) Wave expansion
- REPEAT - Mark all unlabeled neighbors of points marked with i with i+1 - i := i+1 UNTIL ((target reached) or (no points can be marked))
![](../I/Lee_waveprop.png.webp)
Wave Expansion step
3) Backtrace
- go to the target point REPEAT - go to next node that has a lower mark than the current node - add this node to path UNTIL (start point reached)
4) Clearance
- Block the path for future wirings - Delete all marks
Of course the wave expansion marks only points in the routable area of the chip, not in the blocks or already wired parts, and to minimize segmentation you should keep in one direction as long as possible.
External links
References
- Wolf, Wayne (2002), Modern VLSI Design, Prentice Hall, pp. 518ff, ISBN 0-13-061970-1
- Lee, C. Y. (1961), "An Algorithm for Path Connections and Its Applications", IRE Transactions on Electronic Computers, EC-10 (3): 346–365, doi:10.1109/TEC.1961.5219222
- Rubin, F (1974), "The Lee Path Connection Algorithm", IRE Transactions on Electronic Computers, C-23 (9): 907–914, doi:10.1109/T-C.1974.224054, S2CID 32651989
Remzi Osmanli
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.