WikiDer > Бегущий по лабиринту

Maze runner

В автоматизация проектирования электроники, Бегущий по лабиринту это связь маршрутизация , который представляет все пространство маршрутизации в виде сетки. Части этой сети заблокированы компонентами, специализированными участками или уже существующей проводкой. Размер сетки соответствует шагу разводки в данной зоне. Цель состоит в том, чтобы найти цепочку ячеек сетки, которая идет от точки A до точки B.

Бегущий по лабиринту может использовать Алгоритм Ли. Он использует распространение волн style (волна - это все ячейки, до которых можно добраться за n шагов) во всем пространстве маршрутизации. Волна останавливается, когда цель достигнута, и путь определяется путем обратного прослеживания через ячейки.

Смотрите также

Рекомендации

  • Ли, К. Я. (1961), "Алгоритм соединения путей и его приложения", Операции IRE на электронных компьютерах, ИС-10 (2): 346–365, Дои:10.1109 / TEC.1961.5219222. Одно из первых описаний маршрутизатора-лабиринта.