Lee algorithm
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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== Initialization Select start point, mark with 0 i := 0 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)) 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) 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.eecs.northwestern.edu/~haizhou/357/lec6.pdf ==References== Remzi Osmanli
Text derived from https://en.wikipedia.org/w/index.php?oldid=1332939881 under CC BY-SA 4.0; modifications have been made.