- Lee algorithm
The Lee algorithm is one possible solution for
maze routing problem s.1) Initialisation - Select start point, mark with 0 - i := 02) Wave expansion - REPEAT - Mark all unlabeled neighbors of points marked with i with i+1 - i := i+1 UNTIL ((target reached) or (all points 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
External links
* [http://www.princeton.edu/~wolf/modern-vlsi/Overheads/CHAP10-1/sld026.htm Example]
References
*Further information in Wayne Wolf, Modern VLSI Design, Prentice Hall, ISBN 0-13-061970-1, Page 518ff
*Lee, C.Y., "An Algorithm for Path Connections and Its Applications", IRE Transactions on Electronic Computers, vol. EC-10, number 2, pp. 364-365, 1961
Wikimedia Foundation. 2010.
