Lee algorithm
From Wikipedia, the free encyclopedia
 |
This article may require cleanup to meet Wikipedia's quality standards. (Consider using more specific cleanup instructions.) Please help improve this article if you can. The talk page may contain suggestions. (September 2010) |
Main article: Routing (electronic design automation)
The Lee algorithm is one possible solution for maze routing problems based on Breadth-first search.
1) Initialisation
- 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))
3) Backtrace
- go to the target point
REPEAT
- go to next node that has a lower mark than the actual 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.
[edit] External links
[edit] References
- Wolf, Wayne, 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 (2): 346–365
 |
This electronics-related article is a stub. You can help Wikipedia by expanding it. |
