Android-приложение для поиска дешевых авиабилетов: play.google.com
Главная -> Печатный монтаж

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [23] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

Смысл процесса 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. Операция присвоения путевых координат выполняется так же, как в предыдущих алгоритмах, но на различных подмноже-

. 9

.

у/

?7 18

Рис. 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



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [23] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69



0.1817
Яндекс.Метрика