Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Применение алгоритмов проектирования для решения задачи размещения элементов

Используя заданный список цепей, построим граф схемы G (X,U).Если построение графа затруднительно, необходимо построить электрическую схему устройства, а затем приступить к построению графической модели.

Граф G (X,U) схемы представлен на рис.3.3:

 
 

 

 


 

Рисунок 3.3. – Графическая модель схемы.

Коммутационное поле состоит из десяти позиций, но мы будем работать с полем 3х3, т.к. вершина Х1 в размещении не участвует. Используем регулярное размещение элементов.

 

1 2 3
4 5 6
7 8 9

 

Рисунок 3.4. – Графическая модель коммутационного поля.

 

Далее сформируем две матрицы: матрицу смежности R и матрицу координатных длин D.Результаты представим в виде таблиц для удобства восприятия.

Матрица смежности R примет вид:

Таблица 4.

  DD1 DD2 DD3 DD4 DD5 DD6 DD7 DD8 DD9 ρi
DD1
DD2
DD3
DD4
DD5
DD6
DD7
DD8
DD9

 

В последний столбец матрицы смежности R вносим расчетное значение локальной степени вершины ρi, которое в дальнейшем будет применяться для определения теоретической границы суммарной длины проводников Lгр. Локальная степень вершины ρi определяется количеством ребер, инцидентных данной вершине.

Для построения матрицы координатных длин рассчитываются расстояния между соответствующими позициями. Расстояния измеряются в шагах координатной сетки. Расстояние между соседними позициями принимают равным одному шагу. В последнем столбце таблицы указывают суммарное количество координатных длин di для каждой позиции.

Матрица координатных длин D будет представлена в виде:

Таблица 5.

  di
1

 

Процесс размещения. В качестве меры приближения решения задачи к оптимальному необходимо применить сравнение общей длины проводников L(G), полученной после некоторого размещения с оценкой теоретической границы.

Для практического вычисления и оценки граничного значения длины связейLгр все элементы треугольных матриц R и D упорядочивают в возрастающем (для R) и убывающем (для D) порядке. Затем по-членно суммируют произведение RxD этих упорядоченных последовательностей.

Формула для расчета теоретического граничного значения длины имеет вид:

Lгр =1,2•(ΣRij·Dij) (3.1)

Расчет сводим в таблицу:

Таблица 6.

R D RxD R D RxD

 

Lгр = 1,2•18= 21,6 ≈22

Для получения оптимального варианта размещения элементов суммарная длина связей всех проводников не должна превышать значения Lгр, т.е.L(G) < 22

Начальное размещение элементов DD1…DD9 на коммутационном поле печатной платы с установочными позициями 1…9 производим, используя алгоритм обратного размещения. Для этого:

1.Упорядочиваем элементы локальной степени вершины ρiматрицыRпо возрастанию.

2.Упорядочиваем элементы di матрицы координатных длин D по убыванию.

3.Проводим назначение элементов по позициям, назначая элемент DD9 в позицию 1, DD1 – в позицию 3 и т.д., учитывая при этом условие минимума скалярного произведения ρ·d.

Данные сводим в таблицу:

Таблица 7.

  DD9 DD1 DD6 DD7 DD8 DD2 DD4 DD5 DD3
ρ
позиция
d

 

Результаты данного алгоритма отражаем размещением элементов на коммутационном поле:

DD9 1 DD6 2 DD1 3
DD7 4 DD8 5 DD2 6
DD4 7 DD5 8 DD3 9

 

Рисунок 3.5- Начальное размещение элементов на коммутационном поле.

 

Расчет суммарной длины связи начального размещения ΣLнр производится по формуле:

ΣLнр=L1+ L2+ L3+ L4+ L5+ L6+ L7+ L8+ L9, где (3.2)

L1= r12·d12 + r13·d13 + r14·d14 + r15·d15 + r16·d16 + r17·d17 + r18·d18 + r19·d19;

L2= r23·d23 + r24·d24+ r25·d25 + r26·d26 + r27·d27 + r28·d28 + r29·d29;

L3= r34·d34+ r35·d35 + r36·d36 + r37·d37 + r38·d38 + r39·d39;

L4= r45·d45 + r46·d46 + r47·d47 + r48·d48 + r49·d49;

L5= r56·d56 + r57·d57 + r58·d58 + r59·d59;

L6= r67·d67 + r68·d68 + r69·d69;

L7= r78·d78 + r79·d79;

L8= r89·d89;

L9=0.

Здесь rmn– количество ребер, соединяющих соответствующие вершины;

dmn– расстояние между соответствующими вершинами в шагах на конкретном варианте размещения.

Произведем расчет суммарной длины проводников для варианта начального размещения:

L1= 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1·2=2;

L2= 1·1 + 1·3+ 0 + 0 + 0 + 0 + 0=4;

L3= 3·2+ 3·1 + 0 + 0 + 0 + 0 = 9;

L4= 0 + 3·3 + 0 + 0 + 0 = 9;

L5= 0 + 1·2 + 2·1 + 0 = 4;

L6= 0 + 0 + 1·1 = 1;

L7= 1·1 + 0 = 1;

L8= 1·2 = 2;

L9=0.

Результаты суммируются по формуле (1), в итоге получим ΣLнр=32.

Сравнение полученного значения со значением теоретической границы суммарной длины (Lгр = 22) показывает, что начальное размещение элементов не оптимально и требуется улучшить полученный результат, т.е. достичь такого варианта размещения, когда

ΣLнр<Lгр

Далее, применяя алгоритм парных перестановок, который заключается в по-парной перестановке элементов на коммутационном поле, отыскиваем такой вариант размещения, для которого ΣL(G)<22.


Последнее изменение этой страницы: 2016-03-16; Просмотров: 22; Нарушение авторского права страницы


lektsia.com 2007 - 2017 год. Все права принадлежат их авторам! (0.085 с.) Главная | Обратная связь