АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО РАЗМЕЩЕНИЯ.

⇐ ПредыдущаяСтр 4 из 7Следующая ⇒

Алгоритм включает такую последовательность действий.

1. Сформировать матрицу расстояний D, элементы которой будем определять по формуле ортогональной метрики:

d_ij = |x_i - x_j| + |y_i - y_j| . (3.2)

2. Для каждой строки матрицы D определить суммарное значение:

3. Ввести матрицу связности R и ее размерность n.

4.Для каждой строки матрицы связности R определить сумму элементов:

5. Найти минимальное значение d_i, если B=i, то пометить столбец j=B.

6. Найти максимальное значение r_i , если Е=i, то удалить столбец j=B.

7. Разместить элемент Е в позицию В.

8. Найти минимум d_i среди оставшихся (m – 1) элементов; просмотреть строку с минимальным d_i и найти минимальный d_ij среди помеченных элементов. Здесь j=B. Определить, какой элемент расположен в позиции j; вновь присвоить B=i, j=B и пометить столбец j.

9. Рассмотреть строку Е в матрице R и найти максимальный r: присвоить E=i, j=E и пометить столбец j.

10. Найти число помеченных столбцов k; если k<n, идти к 8, иначе – к 11.

11. Подсчитать суммарную длину соединений.

Ручной расчет

В качестве модели печатной платы возьмем решетку графа из предыдущей работы и по формуле

d_ij = |x_i - x_j| + |y_i - y_j|

вычислим матрицу расстояний D:

1 2 3 4 5 6

1 0 1 4 3 4 5 17

2 1 0 3 2 3 4 13

3 4 3 0 1 2 3 13

4 3 2 1 0 1 2 [9]

5 4 3 2 1 0 1 11

6 5 4 3 2 1 0 15

Позиция 4

Схему соединения корпусов представим в виде мультиграфа для которого построим матрицу связности R:

1 2 3 4 5 6

1 0 2 0 0 0 1 3

2 2 0 1 0 2 0 5

3 0 1 0 1 1 0 3

4 0 0 1 0 3 0 4

5 0 2 1 3 0 0 [6]

6 1 0 0 0 0 0 1

Вершна 5

Суммирование элементов r_ij в строках матрицы дает локальную степень каждой вершины графа.

Среди S d_ij находим минимальное число,

J=1. Звездочками помечают все элементы этого столбца матрицы

D. Среди S r_ij находим максимальное число, J=1

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

1 2 3 4 6

1 0 2 0 0 1

2 2 0 1 0 0

3 0 1 0 1 0

4 0 0 1 0 0

5 0 2 1 3 0

6 1 0 0 0 0

Отсюда D

1 2 3 4* 5* 6

1 0 1 4 3 4 5 17

2 1 0 3 2 3 4 13

3 4 3 0 1 2 3 13

4 3 2 1 0 1 2

5 4 3 2 1 0 1 [11]

6 5 4 3 2 1 0 15

Вершина 9 позиция 5 преобразовываем. Получаем.R

2 3 4 6

1 2 0 0 1

2 0 1 0 0

3 1 0 1 0

4 0 1 0 0

5 2 1 3 0

6 0 0 0 0

Отсюда матрица D

1 2 3 4* 5* 6

1 0 1 4 3 4 5 17

2 1 0 3 2 3 4 [13]

3 4 3 0 1 2 3 [13]

4 3 2 1 0 1 2

5 4 3 2 1 0 1

6 5 4 3 2 1 0 15

Видим что позиция 2,3 имеюют число 13, выбираем меньшую по порядку,продолжаем преобразование. Получаем матрицу R

2 4 6

1 2 0 1

2 0 0 0

3 1 1 0

4 0 0 0

5 2 3 0

6 0 0 0

Отсюда матрица D

1 2* 3* 4* 5* 6

1 0 1 4 3 4 5 17

2 1 0 3 2 3 4

3 4 3 0 1 2 3 [13]

4 3 2 1 0 1 2

5 4 3 2 1 0 1

6 5 4 3 2 1 0 15

Тоже делаем с 3 строкой , Получаем R и D

2 6

1 2 1

2 0 0

R= 3 1 0

4 0 0

5 2 0

6 0 0

1 2* 3* 4* 5* 6

1 0 1 4 3 4 5 17

2 1 0 3 2 3 4

D= 3 4 3 0 1 2 3

4 3 2 1 0 1 2

5 4 3 2 1 0 1

6 5 4 3 2 1 0 [15]

Выбираем 6 позицию ,преобразовываем,получаем R

1 1

2 0

R= 3 0

4 0

5 0

6 0

1* 2* 3* 4* 5* 6

1 0 1 4 3 4 5 17

2 1 0 3 2 3 4

D= 3 4 3 0 1 2 3

4 3 2 1 0 1 2

5 4 3 2 1 0 1

6 5 4 3 2 1 0

Оставшийся модуль попадает на свободное место. Суммарная длина равна 26. Сравним результат с результатом прикладной программы САПР.

Рис.4 Матрицы схемы последовательного размещения.

Рис.5 Результат размещения программой.

АЛГОРИТМ ПРЕДВАРИТЕЛЬНОГО РАЗМЕЩЕНИЯ

Алгоритм включает такую последовательность действий [3]:

1. Для каждой строки матрицы R определить сумму элементов в каждой

строке матрицы r_i = S r_ij , j = 1,…, n.

j=1

2. Найти минимум среди r₁, i = k.

3. Поместить элемент k в первую по порядку 1,…,n незанятую позицию 1.

4. В матрице R вычеркнуть k-ю строку, а элементы k-го столбца без вычеркнутого n_k элемента с отрицательным знаком переписать с k-го на 1-е место.

5. Если число строк в матрице не равно нулю, идти к 2.

6. Вычислить матрицу расстояний D.

7. Подсчитать суммарную длину соединения L по формуле (3.1).

Конец.

Ручной расчет

Необходимо по критерию минимума суммарной длины соединений разместить n ячеек в n позиций

Матрица смежности графа имеет вид

1 2 3 4 5 6

1 0 1 0 0 0 0 1

2 1 0 2 0 0 0 3

3 0 2 0 1 2 0 5

4 0 0 1 0 1 1 3

5 0 0 2 1 0 3 6

6 0 0 0 1 3 0 4

Минимальное значение 1эл-т, это означает ,что первая ячейка должна быть закреплена. Матрица R2

1 2 3 4 5 6

2 -1 0 2 0 0 0 1

3 0 2 0 1 2 0 5

4 0 0 1 0 1 1 3

5 0 0 2 1 0 3 6

6 0 0 0 1 3 0 4

Минимальное значение имеет 2 эл-т. Матрица R3

1 2 3 4 5 6

3 0 -2 0 1 2 0 1

4 0 0 1 0 1 1 3

5 0 0 2 1 0 3 6

6 0 0 0 1 3 0 4

Минимальное значение имеет 3 эл-т. Матрица R4

1 2 3 4 5 6

4 0 0 -1 0 1 1 1

5 0 0 2 1 0 3 6

6 0 0 0 1 3 0 4

Минимальное значение имеет 4 эл-т. Матрица R5

1 2 3 4 5 6

5 0 0 -2 -1 0 3 0

6 0 0 0 1 3 0 4

Минимальное значение имеет 5 эл-т. Матрица R6

1 2 3 4 5 6

6 0 0 0 -1 -3 0 - 4

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

Рис.6 Матрицы предварительного размещения.

Рис.7 Результат предварительного алгоритма размещения

Дата добавления: 2019-07-17; просмотров: 323; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 345 6 7 Следующая ⇒

Мы поможем в написании ваших работ!