Алгоритм Ли

Алгоритм Ли — одно из возможных решений задач маршрутизации в лабиринте, основанное на поиске в ширину . Он всегда дает оптимальное решение, если оно существует, но работает медленно и требует значительного объема памяти.

Алгоритм

1) Инициализация

 - Select start point, mark with 0
 - i := 0

2) Волновое расширение

 - 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))

3) Обратная трассировка

   - 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)

4) Клиренс

 - Block the path for future wirings
 - Delete all marks

Конечно, отметки волнового расширения указывают только на маршрутизируемую область чипа, а не на блоки или уже подключенные части, и для минимизации сегментации следует как можно дольше сохранять одно направление.

Внешние ссылки

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

Ссылки

Вольф, Уэйн (2002), Современный дизайн СБИС , Прентис Холл, стр. 518 и далее, ISBN 0-13-061970-1
Ли, CY (1961), «Алгоритм соединений путей и его приложения», Транзакции IRE на электронных компьютерах , EC-10 (3): 346–365, doi : 10.1109/TEC.1961.5219222 , S2CID 40700386
Рубин, Ф. (1974), «Алгоритм соединения пути Ли», Транзакции IRE на электронных компьютерах , C-23 (9): 907–914, doi : 10.1109/TC.1974.224054 , S2CID 32651989

Ремзи Османлы

Эта статья, посвященная электронике, незавершена . Вы можете помочь Википедии, расширив ее .