http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=Lee_algorithmLee algorithm - Revision history2026-05-04T16:01:49ZRevision history for this page on the wikiMediaWiki 1.43.1http://debianws.lexgopc.com/wiki143/index.php?title=Lee_algorithm&diff=4422496&oldid=previmported>Citation bot: Add: s2cid. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 781/25002023-11-28T12:59:07Z<p>Add: s2cid. | <a href="/wiki143/index.php?title=En:WP:UCB&action=edit&redlink=1" class="new" title="En:WP:UCB (page does not exist)">Use this bot</a>. <a href="/wiki143/index.php?title=En:WP:DBUG&action=edit&redlink=1" class="new" title="En:WP:DBUG (page does not exist)">Report bugs</a>. | Suggested by Corvus florensis | #UCB_webform 781/2500</p>
<p><b>New page</b></p><div>{{Short description|Algorithm based on breadth-first search to solve mazes}}<br />
{{Main|Routing (electronic design automation)}}<br />
<br />
The '''Lee algorithm''' is one possible solution for [[maze router|maze routing problems]] based on [[breadth-first search]].<br />
It always gives an optimal solution, if one exists, but is slow and requires considerable memory.<br />
<br />
==Algorithm==<br />
1) Initialization<br />
- Select start point, mark with 0<br />
- i := 0<br />
2) Wave expansion<br />
- REPEAT<br />
- Mark all unlabeled neighbors of points marked with i with i+1<br />
- i := i+1<br />
UNTIL ((target reached) or (no points can be marked))<br />
<br />
[[Image:lee waveprop.png|thumb|Wave Expansion step]]<br />
<br />
3) Backtrace<br />
- go to the target point<br />
REPEAT<br />
- go to next node that has a lower mark than the current node<br />
- add this node to path<br />
UNTIL (start point reached)<br />
4) Clearance<br />
- Block the path for future wirings<br />
- Delete all marks<br />
<br />
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.<br />
<br />
==External links==<br />
* http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf<br />
<br />
==References==<br />
* {{Citation<br />
|first= Wayne<br />
|last= Wolf<br />
|title= Modern VLSI Design<br />
|year= 2002<br />
|pages= 518ff<br />
|publisher= Prentice Hall<br />
|isbn= 0-13-061970-1<br />
}}<br />
* {{Citation<br />
|last=Lee<br />
|first= C. Y.<br />
|title= An Algorithm for Path Connections and Its Applications<br />
|journal= IRE Transactions on Electronic Computers<br />
|volume= EC-10<br />
|issue= 3<br />
|pages= 346–365<br />
|year= 1961<br />
|doi=10.1109/TEC.1961.5219222|s2cid= 40700386<br />
}}<br />
* {{Citation<br />
|last=Rubin<br />
|first= F<br />
|title= The Lee Path Connection Algorithm<br />
|journal= IRE Transactions on Electronic Computers<br />
|volume= C-23<br />
|issue= 9<br />
|pages= 907–914<br />
|year= 1974<br />
|doi=10.1109/T-C.1974.224054|s2cid= 32651989<br />
}}<br />
<br />
{{DEFAULTSORT:Lee Algorithm}}<br />
[[Category:Electronic engineering]]<br />
[[Category:Electronic design automation]]<br />
[[Category:Electronics optimization]]<br />
Remzi Osmanli<br />
<br />
{{Electronics-stub}}</div>imported>Citation bot