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

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

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

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

Рис. 5. Построение пути минимальной длины по алгоритму Акерса при распространении волны в четырех направлениях.

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

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

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

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

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

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

Для источников A и B взято по два луча с взаимно противоположными направлениями. Поскольку разности координат (x_A - x_B) > 0 A B и (y_A - y_B) > 0 , то для луча A⁽¹⁾ допустимое направление движения вначале вниз, а в случае преграды – влево; для луча B⁽¹⁾ – вверх, вправо; для A⁽²⁾ – влево, вниз; для B⁽²⁾ – вправо, вверх. Если ячейка B будет расположена не слева от A, а справа, то путевые координаты влево и вправо надо поменять местами.

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

Рис. 6. Построение пути минимальной длины по лучевому алгоритму.

этом шаге поступил луч. На втором шаге луч B⁽²⁾ справа оказывается заблокированным, поэтому он меняет направление «вправо» на направление «вверх» – просматривается ячейка с координатами (4,4). На третьем шаге лучи A⁽²⁾ и B⁽²⁾ оказываются заблокированными и меняют свое направление. На шестом шаге лучи A⁽¹⁾ и B⁽²⁾ встретились в ячейке C с координатами (7,3).

Путь строится из ячейки C по путевым координатам в направлении ячеек A и B. Если бы ячейки (3,5) и (5,4) были заняты, то лучи B⁽¹⁾ и B⁽²⁾ оказались бы заблокированными, и решение найдено не было, хотя путь из A в B провести можно.

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

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

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

7. Выводы.

В результате выполнения работы была исследована эффективность алгоритмов трассировки печатных и пленочных соединений; освоены особенности алгоритмизации и программирования задач трассировки печатных соединений на современных ЭВМ волновыми и лучевым алгоритмами; приобретен навык построения математических моделей объектов конструирования, реализации и исследования их при решении задачи трассировки в САПР. Для конкретного примера были получены пути минимальной длины: по алгоритму Ли при распространении волны в четырех направлениях - 12 ед., в восьми - 8 ед., по алгоритму Акерса - 12 ед., по лучевому алгоритму - 12 ед.