리 알고리즘

Lee 알고리즘은 폭 우선 검색에 기초한 미로 라우팅 문제에 대한 가능한 해결책 중 하나입니다.최적의 솔루션이 있으면 항상 제공되지만 속도가 느리고 상당한 메모리가 필요합니다.

알고리즘.

1) 초기화

- 시작점 선택, 0으로 표시 - i : = 0

2) 파동팽창

- 반복 - i로 표시된 점의 레이블이 없는 모든 인접을 i+1로 표시 - i := i+1 TILL(목표 도달) 또는 (점 표시 불가)

3) 역추적

- 대상 지점으로 이동 REPECT - 현재 노드보다 낮은 마크를 가진 다음 노드로 이동 - 이 노드를 경로 INTIL(시작점에 도달)에 추가합니다.

4) 클리어런스

- 향후 배선을 위해 경로 차단 - 모든 마크 삭제

물론 웨이브 확장은 칩의 라우팅 가능 영역에만 표시되며 블록이나 이미 배선된 부품에는 표시되지 않습니다.분할을 최소화하려면 가능한 한 한 한 한 방향으로 유지해야 합니다.

외부 링크

• http://www.eecs.northwestern.edu/~haishou/357/lec6.pdf

레퍼런스

• Wolf, Wayne (2002), 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, doi:10.1109/TEC.1961.5219222
• Rubin, F (1974), "The Lee Path Connection Algorithm", IRE Transactions on Electronic Computers, C-23 (9): 907–914, doi:10.1109/T-C.1974.224054

렘지 오스만리