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.25).

1. Ввод данных. В запоминающее устройство заносятся координаты конечных элементов трассы \Ха, уа\ и 1>в, Ув\.

2. Вычисление приоритетных направлений распространения лучей выполняется по следующим формулам:

, , f 1 при Ха -Х >- О

10приХа-Хз<0

(1.12)

1 при у-у>0 .0 при у~у,<0

Могут встретиться 4 ситуации приоритетных направлейий распространения лучей, приведенные в табл. 1.20.

Таблица 1.20.

Приоритетные направления распространения а-луча

вверх - вправо

вверх - влево

вниз - вправо

вниз - влево

Приоритетное направление распространения а-луча

вправо - вверх

влево - вверх

вправо - вниз

влево - вниз

Приоритетное направление распространения Р-луча

вниз - влево

вниз - вправо

вверх - влево

вверх - вправо

Приоритетное направление распространния Р-луча

влево - вниз

вправо - вниз

влево - вверх

вправо - вверх

Для примера, приведенного на рис. 1.26,

assign (5-16) = 0,

fi=.sign(12-6)=l.

Следовательно, Лрлуч должен распространяться вниз -вправо. Это означает, что главным приоритетным направлением является направление, когда элемент /С-фронта имеет ту же абсциссу, что и элемент (/С-1)-фронта, а ординату на 1 меньше, о случае если это направление блокируется занятым или запрещенным элементом, движение луча выполняется по направле-*1Ию, при котором элемент /С-фронта имеет ту же ординату, что и элемент (/С-1)-фронта, а абсциссу на 1 больше. Распространение луча в этом направлении осуществляется до тех пор, пока е освободится путь для главного приоритетного направления.



Лг-луч должен распространяться в направлении вправо - вниз, т. е. у него приоритетные направления поменялись местами и главным стало направление вправо.

Б-лучи имеют приоритетные направления распространения обратные тем, которые приписаны Л-лучам.

3. Вычисление координат множества элементов {Фк}- Как было сказано выше, множество {Фк} включает при двухлучевом алгоритме не более 4 элементов.

4. Проверка выполнения условия {к}#0, т. е. проверяется, имеются ли в составе фронта лучей свободные элементы. Если

13 П 11 Ю 9 8 7 Б 5

3 Z 7

12 3 4 5 6-1

9 10 77 12 13 П 15 1Б 17 18 19 20

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

ИХ нет, то распространение лучей прекращается и трасса заносится в список непроведенных соединений.

На рис. 1.26 видно, что после 5 шагов Вг-луч дальше распространяться не может, так как оба его приоритетных направления заблокированы занятыми элементами.

. 5. Присвоение путевых координат множеству свободных элементов /(-фронта производится, как было описано.

6. Проверка выполнения условия Uab {Fk}, т. е. определяется, имеет ли хотя бы один элемент из числа входящих в Д-фронт признаки разноименных лучей. В приведенном примере на девятом шаге этим свойством будут обладать элементы с координатами (12, И), и (13, И), в которых произошла встреча Лг-луча и Вглуча. Сле)1,овательно, можно приступать к определению координат трассы АВ (блок 7). Исходным элементом при этом может быть выбран первый из подвергнутых анализу и удовлетворяющий условию 6.



Если условие 6 не выполняется, то алгоритм моделирует следующий фронт распространения лучей.

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

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

С целью расширения возможности двухлучевого алгоритма шожно ввести некоторые усложнения в него, которые проиллюстрируем на примере Бг-луча (см. рис. 1.26).

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

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

Для Вг-луча сначала возвращают фронт в элемент с коорди-шатами (13, 6) и пытаются распространить луч вверх. Через .i шаг он снова блокируется. Тогда фронт возвращается в элемент (14, 6) и луч распространяется через элементы (14, 7), <14, 8), (14, 9), (13, 9) ИТ. д. до встречи с Лрлучом.

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

С помощью двухлучевого алгоритма можно также решить задачу построения трассы с наименьшим числом пересечений. Для этого в алгоритм необходимо ввести дополнительный блок, который/при невыполнении условия {Рк}=?0 (блок 4) разрешает Л-лучам пересечь препятствие. Если при дальнейшем распро- *транении Л-лучи опять окажутся заблокированными, то дается разрешение на пересечение преграды В-лучам и т. д.

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



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