Бегущий по лабиринту
 | Эта статья нуждается в дополнительных цитатах для проверки . ( декабрь 2006 г. ) |
В электронного проектирования автоматизации «бегущий по лабиринту» соединений — это метод маршрутизации , который представляет все пространство маршрутизации в виде сетки. Части этой сети заблокированы компонентами, специализированными участками или уже существующей проводкой. Размер сетки соответствует шагу проводки на участке. Цель — найти цепочку ячеек сетки, идущую из точки А в точку Б.
Бегущий по лабиринту может использовать алгоритм Ли . Он использует волновой стиль распространения (волна — это все ячейки, до которых можно добраться за n шагов) по всему пространству маршрутизации. Волна останавливается, когда цель достигнута, а путь определяется путем обратного отслеживания по ячейкам.
См. также
[ редактировать ]Ссылки
[ редактировать ]- Ли, CY (1961), «Алгоритм соединений путей и его приложения», Транзакции IRE на электронных компьютерах , EC-10 (2): 346–365, doi : 10.1109/TEC.1961.5219222 . Одно из первых описаний лабиринтного маршрутизатора.
 | Эта статья, посвященная электронике, незавершена . Вы можете помочь Википедии, расширив ее . |