Построение пути минимальной длины

Пусть задано множество ячеек дискретного поля, на котором построено некоторое число проводников. Требуется построить новый проводник между точками A и B так, чтобы он не пересекал ранее построенные проводники и имел минимально возможную длину (рис.7.8).

              Рис.7.8.                                           Рис.7.9.

Распространение волны начинаем из источника – точки A, вес которой положим равным нулю. Строим расширяющийся фронт волны влияний, распространяющийся на все соседние свободные с этой точкой ячейки. Каждая ячейка фронта генерирует следующий фронт волны, который занимает все соседние свободные с первым фронтом ячейки и т. д. Вес ячейки k-го фронта считается равным весу соседней ячейки (k – 1)-го фронта плюс единица, т. е. . Процесс распространения волны продолжаем до тех пор, пока не достигнем ячейки с точкой B (целью). Процесс поиска пути из A в B в соответствии с рассмотренным алгоритмом для данного варианта трассировки показан на рис.7.8. В каждой ячейке указаны приписанные ей на этапе распространения волны путевые координаты и веса. Ячейка B достигается при построении 16-го фронта волны.

Проведение пути начинаем с ячейки B (цели). Просматриваем окрестность точки цели (приемника) и находим ячейку, которая в наиболее приоритетном направлении имеет вес на единицу меньше. Перемещаемся в эту ячейку и отмечаем след перехода. Процесс продолжаем до тех пор, пока след не приведет в точку A. На рис.7.9 показан вновь проведенный путь. Из него видно, что построенный проводник действительно является кратчайшим между точками A и B, причем его относительная длина равна весу, присвоенного ячейке B.

В данном случае путевая координата несет избыточную информацию. Действительно, при проведении пути использовались только данные о весе просматриваемой ячейки, а приоритет его проведения учитывался последова-тельностью просмотра этих ячеек.

Достоинства волнового алгоритма: возможность нахождения пути мини-мальной длины в любом лабиринте, если существует хотя бы один путь в нем.

Недостатками волнового алгоритма Ли являются малое быстродействие и большой объем оперативной памяти ЭВМ, необходимый для хранения инфор-мации о текущем состоянии всех ячеек коммутационного поля.

Алгоритм Акерса

Наиболее экономичный способ кодирования состояний ячеек коммутаци-онного поля предложен Акерсом [1 – 4]. При распространении волны ячейки поля получают отметки в соответствии с базовой последовательностью 1, 1, 2, 2, 1, 1, 2, 2, … . Данная последовательность характерна тем, что в ней любой член имеет разных соседей слева и справа. Вначале все незанятые ячейки, соседние с ячейкой-источником, помечаются 1, затем все ячейки фронта  помечаются так же 1. Далее отметка 2 присваивается ячейкам фронта  и т. д. (рис.7.10).

Для построения пути в общем случае необходимо найти требуемую под-по-следовательность отметок базовой последовательности. Это легко может быть сделано по отметке ячейки-цели и отметке соседней с ней ячейки. В нашем случае цель достигнута первой 1, поэтому надо искать ячейку с отметкой 2. Их две: внизу и слева. Воспользуемся приоритетом. Вначале просматриваем ячейку снизу от цели. Поскольку ее вес равен 2, путь строим в нее. В ней вновь анализируем соседние ячейки в порядке приоритета. Ищем ячейку с весом 2. Это опять нижняя ячейка. Далее надо аналогично искать ячейку с весом 1.

Вариант соединения контактов A и B при этом заданном приоритете дан на рис.7.10.

В методе Акерса ячейка поля может находиться в следующих состояниях: пустая, занятая, иметь отметку 1 или 2. Таким образом, на каждую ячейку поля достаточно всего два двоичных разряда памяти.

Лучевой алгоритм

Основная идея алгоритма, предложенного Л. Б. Абрайтисом [1 – 4], заклю-чается в исследовании поля для определения пути между ячейками A и B по некоторым заранее заданным направлениям, подобным лучам. Это позволяет сократить число просматриваемых алгоритмом ячеек, а, следовательно, и время на анализ и кодировку их состояний, однако снижает вероятность нахождения пути сложной конфигурации и усложняет учет конструктивных требований к технологии печатной платы.

Рис.7.10.

Работа алгоритма заключается в следующем. Задается число лучей, распро-страняемых из ячейки A и B, а также порядок присвоения путевых координат. Обычно число лучей для каждой из ячеек (источников) принимают одинаковым (часто равным двум). Лучи , , …,  и , , …,  считаются одноименными, если они распространяются из одноименных источников A или B. Лучи  и  являются разноименными по отношению друг к другу. Распространение лучей происходит одновременно из обоих источников до встречи двух разноименных лучей в некоторой точке C.

Путь проводится из ячейки C, в которой встретились лучи по путевым координатам, и проходит через ячейки, по которым распространялись лучи.

При распространении луча может возникнуть ситуация, когда две соседние ячейки будут заняты. В этом случае луч считается заблокированным и его рас-пространение прекращается.

Рассмотрим работу лучевого алгоритма на примере (рис.7.11).

Для источников A и B взято по два луча с взаимно противоположными направлениями. Поскольку разности координат  и , то для луча  допустимое направление движения вначале вниз, а в случае преграды – вправо; для луча  – вверх, влево; для  – вправо, вниз; для  – влево, вверх. Если ячейка B будет расположена не справа от A, а слева, то путевые координаты вправо и влево надо поменять местами.

На первом шаге алгоритма просматриваются ячейки с координатами (3,8), (9,3), (4,9) и (8,2). Поскольку эти ячейки оказались свободными, в них ставятся путевые координаты, которые указывают назад, т.е. на те ячейки, из которых на

Рис.7.11.

этом шаге поступил луч. На третьем шаге луч  сверху оказывается забло-кированным, поэтому он меняет направление «вверх» на направление «влево» – просматривается ячейка с координатами (8,4). На четвертом шаге луч  оказывается заблокированным, а лучи  и  встретились в ячейке C с координатами (5,4). Луч , пройдя через все поле, оказывается заблоки-рованным в ячейке с координатами (10,1).

Путь строится из ячейки C по путевым координатам в направлении ячеек A и B. Если бы ячейка (7,2) была занята, то лучи  и  оказались бы заблокированными, и решение найдено не было, хотя путь из A в B провести можно.

Достоинства алгоритма: получение соединений минимальной длины и высокое быстродействие.

Недостаток: не всегда находит решение, хотя оно может существовать, при трассировке двухслойных плат с ортогональной коммутацией с помощью лучевого алгоритма удается построить до 70% трасс, а остальные проводят, используя волновой алгоритм или вручную.

Поэтому лучевой алгоритм целесообразно применять для трассировки плат с небольшой степенью заполнения ячеек или в начальной стадии трассировки совместно с волновым алгоритмом. В этом случае удается значительно экономить время.

ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ