Проектирование печатных плат. Овчинников В.А - 8 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

8
приближенно определять как расстояние от вертикального (горизонталь-
ного) ряда, в котором установлен этот элемент, до контактной группы.
Для некоторого размещения суммарная взвешенная длина соедине-
ний
∑
=
∑
=
∑
=
+=
N
1i
N
1j
N
1i
i
m
i
h
ji,
d
ji,
r
2
1
L(a) ,
где d
i,j
– элемент матрицы D
r
, определяет расстояние между позициями ус-
тановки конструктивных элементов e
i
и e
j
; m
i
– номер вертикального ряда,
в котором расположен элемент e
i
.
Теперь задача заключается в минимизации L(a) на множестве раз-
мещений А. Это один из вариантов задачи квадратичного назначения, точ-
ное решение которой можно найти, например, методом ветвей и границ.
Алгоритмы, реализующие этот метод, можно использовать на практике
при N=15…20.
2. Последовательные алгоритмы размещения
Решающее правило большинства последовательных алгоритмов раз-
мещения по связности основано на предположении, что наиболее связан-
ные элементы следует располагать максимально близко друг к другу. На
каждом шаге алгоритма выбирают в соответствии с некоторой оценкой
очередной элемент и позицию для его установки. Выбор элемента и пози-
ции можно осуществлять раздельно (по разным
оценкам) или одновремен-
но. Более просты алгоритмы, реализующие принцип раздельного выбора.
Позиции некоторых элементов могут быть заранее указаны разработчиком
исходя из схемотехнических требований. Например, мощные элементы с
большим коэффициентом разветвления следует располагать в первом ряду
от выходных контактов платы субблока. Если фиксированных элементов
нет, то должно быть задано правило выбора
начального элемента и пози-
ции его установки. Например, начальное размещение можно получить ус-
тановкой в центральную позицию элемента с максимальным числом связей
или в ряду позиций, ближайших к контактной группе элементов, имеющих
максимальную связность с нею.
Рассмотрим алгоритмы, использующие принцип разделения выбора
элемента и позиции его установки. На основании оценки степени
связно-
сти элементов определяют очередной размещаемый элемент, затем по
оценке качества позиции
– место установки. Для выбора размещаемого
элемента используют различные оценки степени связности. Рассмотрим
некоторые из них.
Пусть на k-м шаге алгоритма размещено Ek = E элементов, т.е. име-
ется некоторое частичное размещение. Множества элементов Е и устано-
вочных позиций Т распадаются на непересекающиеся подмножества раз-

Страницы