Смысл процесса 3 и соответствующих ему операций блока 6 заключается в том, что при каждом цикле моделирования фронта волны предпочтение прежде всего отдается элементам, около которых нет ранее проложенных трасс.

4. Проверка условия {Фк }=70. В том случае, когда ни один элемент фронта не свободен от соседства занятых элементов.

вВод данных

Проверка услоВия

\нет

Проверка условия

г вычисление

координат множества элементов (Ф)

Проверка услоВия

(Фн°>)ФО

5 Присвоение путевых, координат

Проверка, условия

ве(Ф,)

Запись координат трассы АВ

Рис. 1.21. Структурная схема волнового алгоритма для проведения пути, минимально приближающегося к другим трассам

-фронт формируется из всех элементов, имеющих один соседний занятый элемент.

Из рис. 1.22 видно, что при распространении волны на множествах {Фк } на щестом щаге были достигнуты элементы с координатами (6,5), (7,6), (9,7), (3,14) и (4,15), на девятом шаге достигнут элемент (1,15). Дальнейшее распространение волны по элементам, не имеющим по соседству трасс, невозможно, тогда моделируется - фронт одновременно из всех элементов, имеющих по одному занятому соседнему элементу. В дальней-Н1ем, распространяя волну по элементам (7,5), (7,4) и т. д. удается провести- трассу через множество элементов, не имеющих ря-Дом проложенных проводников.

5. Проверка условия {Фк }¥=0. В результате этой процедуры в Л-фронт волны включаются элементы с двумя соседними занятыми элементами, а при их отсутствии - тремя.

Очевидно, что больше трех соседних элементов, на которых еше не моделировалось распространение волны при выбранной геометрии, быть не может, так как каждый элемент имеет только 4 соседних, причем минимум один из них принадлежит множеству элементов предыдущего фронта.

6. Операция присвоения путевых координат выполняется так же, как в предыдущих алгоритмах, но на различных подмноже-

Рис. 1.22. .Пример определения трассы с помощью волнового алгоритма для проведения пути, минимально приближающегося к другим трассам

ствах элементов, входящих в состав множества {Фк }, в зависимости от результатов, полученных при работе блоков 3, 4 и 5.

Блоки 7 и 8 аналогичны ранее рассмотренным.

Из примера на рис. 1.22 видно, что возможно провести кратчайшую трассу АВ с двумя пересечениями и длиной 7 или трассу без пересечений длиной . С помощью рассматриваемого алгоритма проложен проводник длиной 21, но расположенный в наименее заполненной области пространства платы.

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

W Будем считать, что при прокладке трассы разрешается пере-секать ранее проложенные соединения. Запрещенными элемен-Kj-aMH являются концы проводников и места их изгибов, т. е. элементы, которые заняты под переходы со слоя на слой.

Введем следующие обозначения: {Фк} - множество элементов /С-фронта, имеющих путевую координату того же направления.

ВВод данных

2 Вычисление

координат множества элементов (4>к)

3 Присвоение путевых координат множеству элементов (Фк)

Проверка условия

Б Выделение множества элементов (Ф,)

Б Выделение множества элементов (Ф,)

Проверка условия:

ве(Ф)

Проверка, условия

ве (Ф,,)

Запись иоорОинат трассы АВ

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

ЧТО и у элементов (/С-1)-фронта, по номерам которых присваиваются путевые координаты элементам /С-фронта.

{Ф} - множество элементов /С-фронта, имеющих путевую Координату другого направления, чем у элементов /С-1-фронта, Но Номерам которых присваиваются путевые координаты элементам /С-фронта.

Структурная схема алгоритма приведена на рис. 1.23.

Первые три блока принципиально ничем не отличаются от Описанных ранее.

fl 75