Lee algorithm
Algorithm based on breadth-first search to solve mazes
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.
01Algorithm
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.
Sources and credits
This article is adapted from the Wikipedia article “Lee algorithm”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Images, from Wikimedia Commons:
- Lee waveprop.png by Ian Kilgore, CC BY 3.0
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.