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

На рис. 1.20 приведен пример определения трассы АВ с помощью описываемого алгоритма. Заштрихованными зонами показаны ранее проложенные проводники. Видно, что после 8 шагов распространение фронта волны во всех направлениях заблокировано множеством занятых и запрещенных элементов.

4. Формирование фронта волны, состоящего из множества элементов {Ск}. В случае невыполнений условия 3 происходит

ввод данных

2 Вычиспение координат шожестВа элементов (ф)

и Формирование фронта состоящего из мнон<естда зле-ментоЬ (С)

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

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

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

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

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

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

На рис. 1.20 показано, что в состав фронта не входят запрещенные элементы с координатами (2,4), (9,12) и (10,5).

5. Присвоение путевых координат. Эта процедура применяется к множеству незанятых элементов {F в случае выполнения условия 5, или к множеству занятых элементов {Ск} прИ невыполнении этого условия. В рассматриваемом примере



/рис. 1-20) приоритетный порядок присвоения путевых координат установлен такой же, как и в предыдущем алгоритме.

6. Проверка выполнения условия Бе{к}, т. е. проверяется, входит ли конечный элемент трассы В в множество элементов /(-фронта. В случае отрицательного результата проверки формируется новый фронт распространения волны. При этом, если в данном цикле моделирования волны действовала операция 4, то в состав фронта войдут толькО незанятые элементы, соседние

ччч,

УХ/ /X/

2 5 4 5 Б 7 8 Э

11 12 13 Ш 15 16 17

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

С Занятыми элементами предыдущеш фронта. На рис. 1.20 видно, что фронт после прорыва преграды не включает в свой состав: а) запрещенные элементы, в которых проводник меняет свое направление;

•б) занятые элементы, соседние с занятыми элементами предыдущего фронта с координатами (2,12), (6,4), (7,4), (9,9) и

.в) запрещенный элемент (10,9), через который проходят трассы.

Если условие 6 вьшолняется, то моделирование волны пре-•Ращается, соединение АВ может быть проведено.

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



Для проведения последующих трасс эти элементы становятся запрещенными [элемент с координатами (10,7) на рис. 1.20].

В рассматриваемом примере трасса АВ длиной d= 5-13 + + 110-7 =/11 проведена за 12 шагов. Потеря времени произошла за счет того, что алгоритм искал путь без пересечений. Вообще рассматриваемый алгоритм обладает тем недостатком, что не позволяет находить соединения кратчайшей длины среди всех соединений с одинаковым числом пересечений ранее проложенных трасс. Причина этого обстоятельства - в процессе поиска пути без пересечений волной сначала моделирующейся на всем пространстве незанятых элементов вокруг А и только после этого преодолевающей блокирующие трассы. В результате место преодоления преграды кратчайшим проводником может оказаться от конечного элемента В дальше, чем место прорыва другими проводниками. Поэтому другие проводники, естественно, достигнут элемента В раньше.

Рассмотренным модификациям волнового алгоритма присущ общий недостаток: прокладывая трассы, стремящиеся к одной из границ пространства платы; они одновременно прижимают трассы друг к другу (см. рис. 1.18 и 1.20). Это явление может вызвать блокировку конечных элементов трасс и служит причиной взаимных наводок между проводниками. В целях борьбы.с указанными недостатками разработана следующая модифика ция волнового алгоритма.

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

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

При описании алгоритма введем обозначение:

{Фк™} - подмножество элементов /(-фронта, имеющих соседние занятые и запрещенные элементы.

Рассмотрим структурную схему алгоритма (рис. 1.21).

1. Ввод данных. Операция, аналогичная для всех рассмотренных алгоритмов.

2. Вычисление координат множества элементов {Фк}- Этот блок также подобен ранее рассмотренным.

3. Проверка условия {Фк<-°ЦфО. В процессе этой проверки выявляется наличие в /(-фронте элементов, не имеющих занятых (запрещенных) соседних элементов. Если такие имеются, то К-фронт создается из них и только этим элементам приписываются путевые координаты. Для простоты изложения будем считать, что приоритетный порядок присвоения путевой координаты выбран таким же, как и в ранее рассмотренных примерах.



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.0153
Яндекс.Метрика