Алгоритм Ли - Lee algorithm
В Алгоритм Ли одно возможное решение для проблемы с маршрутизацией в лабиринте на основе Поиск в ширину Он всегда дает оптимальное решение, если оно существует, но работает медленно и требует значительного объема памяти.
Алгоритм
1) Инициализация
- Выберите начальную точку, отметьте 0 - i: = 0
2) Волновое расширение
- ПОВТОР - пометьте всех непомеченных соседей точек, отмеченных i, с помощью i + 1 - i: = i + 1 UNTIL ((цель достигнута) или (точки не могут быть отмечены))
Шаг расширения волны
3) Обратная трассировка
- перейти к целевой точке REPEAT - перейти к следующему узлу, имеющему более низкую отметку, чем текущий узел - добавить этот узел к пути ДО ТОГО (начальная точка достигнута)
4) оформление
- Заблокировать путь для будущих проводок - Удалить все отметки
Конечно, волновое расширение отмечает только точки в маршрутизируемой области микросхемы, а не в блоках или уже подключенных частях, и для минимизации сегментации вы должны как можно дольше оставаться в одном направлении.
внешняя ссылка
Рекомендации
- Вольф, Уэйн (2002), Современный дизайн СБИС, Прентис Холл, стр. 518ff, ISBN 0-13-061970-1
- Ли, К. Я. (1961), "Алгоритм соединения путей и его приложения", Операции IRE на электронных компьютерах, ИС-10 (2): 346–365, Дои:10.1109 / TEC.1961.5219222
 | Эта статья про электронику заглушка. Вы можете помочь Википедии расширяя это. |