АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО РАЗМЕЩЕНИЯ
Алгоритм включает такую последовательность действий. 1. Сформировать матрицу расстояний D, элементы которой будем определять по формуле ортогональной метрики: dij = |xi - xj| + |yi - yj| . (3.2) 2. Для каждой строки матрицы D определить суммарное значение: 3. Ввести матрицу связности R и ее размерность n. 4.Для каждой строки матрицы связности R определить сумму элементов: 5. Найти минимальное значение di, если B=i, то пометить столбец j=B. 6. Найти максимальное значение ri , если Е=i, то удалить столбец j=B. 7. Разместить элемент Е в позицию В. 8. Найти минимум di среди оставшихся (m – 1) элементов; просмотреть строку с минимальным di и найти минимальный dij среди помеченных элементов. Здесь j=B. Определить, какой элемент расположен в позиции j; вновь присвоить B=i, j=B и пометить столбец j. 9. Рассмотреть строку Е в матрице R и найти максимальный r: присвоить E=i, j=E и пометить столбец j. 10. Найти число помеченных столбцов k; если k<n, идти к 8, иначе – к 11. 11. Подсчитать суммарную длину соединений.
ПРИМЕР 3.1
Дано монтажное пространство (печатная плата) (рис.3.1,а), в котором име-ется 7 свободных позиций с координатами центров позиций соответственно: x1=2, y1=1; x2=2, y2=2; x3=3, y3=2; x4=4, y4=2; x5=1, y5=3; x6=2, y6=3; x7=4, y7=4. На эти позиции необходимо разместить по критерию минимальной суммарной длины связей семь микросхем, соединенных в соответствии со схемой рис.3.2, а. Решение В качестве модели печатной платы возьмем решетку графа (рис. 3.2, б) и по формуле dij = |xi - xj| + |yi - yj| вычислим матрицу расстояний D:
1 2 3 4 5 6 7 1 0 1 2 3 3 2 5 16 2 1 0 1 2 2 1 4 [11] 3 2 1 0 1 3 2 3 12 D = 4 3 2 1 0 4 3 2 15 5 3 2 3 4 0 1 4 17 6 2 1 2 3 1 0 3 12 7 5 4 3 2 4 3 0 21 .
Определим сумму элементов S dij в каждой i-й строке матрицы и запи- J=1 шем ее справа от матрицы. Сумма показывает суммарную удаленность i-й позиции от всех остальных. Схему соединения корпусов представим в виде мультиграфа (рис. 3.2, б), для которого построим матрицу связности R:
1 2 3 4 5 6 7 1 0 3 0 2 2 0 1 8 2 3 0 3 0 5 0 0 [11] 3 0 3 0 2 0 0 0 5 R = 4 2 0 2 0 0 0 0 4 5 2 5 0 0 0 3 0 10 6 0 0 0 0 3 0 3 6 7 1 0 0 0 0 3 0 4 .
Суммирование элементов rij в строках матрицы дает локальную степень каждой вершины графа. Среди S dij находим минимальное число, оно равно 11 и соответствует J=1 позиции №2. Звездочками помечают все элементы второго столбца матрицы D. Среди S rij находим максимальное число, оно равно 11 у вершины №2. J=1 Поэтому 2-й модуль, имеющий наибольшее количество связей, размещаем в позицию №2, которая наиболее удалена от остальных позиций платы. После этого 2-й столбец матрицы R исключаем из дальнейшего рассмотрения. Имеем
1 3 4 5 6 7 1 0 0 2 2 0 1 2 3 3 0 [5] 0 0 3 0 0 2 0 0 0 R = 4 2 2 0 0 0 0 5 2 0 0 0 3 0 6 0 0 0 3 0 3 7 1 0 0 0 3 0
1 2* 3 4 5 6 7 1 0 1 2 3 3 2 5 16 2 1 0 1 2 2 1 4 3 2 [1] 0 1 3 2 3 [12] D = 4 3 2 1 0 4 3 2 15 5 3 2 3 4 0 1 4 17 6 2 1 2 3 1 0 3 12 7 5 4 3 2 4 3 0 21 .
Среди оставшихся S dij находим минимальное число. Оно равно 12 сразу J=1 у двух позиций: №3 и №6. Берем 1-ю по порядку позицию №3. Помечаем все элементы третьего столбца матрицы D. Проходим вторую строку матрицы R и находим, что в ней максимальный элемент 5, который находится в 5-м столбце. Следовательно, модуль №5 размещаем в позицию №3, а 5-й столбец матрицы R из дальнейшего рассмотрения исключается. Получили
1 3 4 6 7 1 0 0 2 0 1 2 3 [3] 0 0 0 3 0 0 2 0 0 R = 4 2 2 0 0 0 5 2 0 0 3 0 6 0 0 0 0 3 7 1 0 0 3 0
1 2* 3* 4 5 6 7 1 0 1 2 3 3 2 5 16 2 1 0 1 2 2 1 4 3 2 1 0 1 3 2 3 D = 4 3 2 1 0 4 3 2 15 5 3 2 3 4 0 1 4 17 6 2 [1] 2 3 1 0 3 [12] 7 5 4 3 2 4 3 0 21 На следующем шаге отыскиваем min из S d6j =12 в строке №6. J=1 Просматриваем шестую строку матрицы D и среди помеченных элементов 2-го и 3-го столбцов выбираем минимальный. Так определяем, к какой из уже занятых позиций, позиция №6 находится ближе всего: min[d62, d63] = d62 = 1 – ко 2-й. Во второй позиции уже находится модуль №2. Поэтому просматриваем вторую строку матрицы R и выбираем максимальный элемент r21 = 3. Он соответствует 1-му модулю, поэтому элемент №1 размещаем в позицию №6. Исключаем из дальнейшего рассмотрения первый столбец матрицы R. Получили матрицы
3 4 6 7 1 0 2 0 1 2 3 0 0 0 3 0 2 0 0 R = 4 2 0 0 0 5 0 0 [3] 0 6 0 0 0 3 7 0 0 3 0
1 2* 3* 4 5 6* 7 1 0 1 2 3 3 2 5 16 2 1 0 1 2 2 1 4 3 2 1 0 1 3 2 3 D = 4 3 2 [1] 0 4 3 2 [15] 5 3 2 3 4 0 1 4 17 6 2 1 2 3 1 0 3 7 5 4 3 2 4 3 0 21 .
Далее выбираем min из S dij = 15 в 4-й строке. В четвертой строке матрицы J=1 D среди помеченных элементов d42, d43, d46 минимальный d43 = 1.Это говорит о том, что до позиции №4 ближе всех позиция №3, в которой уже размещен модуль №5. Поэтому просматриваем пятую строку матрицы R и среди оставшихся в ней элементов находим минимальный: r56 = 3 в шестом столбце. Тогда модуль №6 размещаем в позицию №4 и исключаем из дальнейшего рассмотрения столбец №6 матрицы R:
3 4 7 1 0 2 1 2 [3] 0 0 3 0 2 0 R = 4 2 0 2 5 0 0 0 6 0 0 3 7 0 0 0
1 2* 3* 4* 5 6* 7 1 0 [1] 2 3 3 2 5 [16] 2 1 0 1 2 2 1 4 3 2 1 0 1 3 2 3 D = 4 3 2 1 0 4 3 2 5 3 2 3 4 0 1 4 17 6 2 1 2 3 1 0 3 7 5 4 3 2 4 3 0 21 . Вновь выбираем минимальную из оставшихся сумм: S d1j = 16 для пози- J=1 ции №1. Просматриваем первую строку матрицы D и среди помеченных элементов {d12, d13, d14, d16} находим min: это d12 = 1. Значит, от позиции №1 наименее удалена позиция №2, в которой находится модуль №2. Помечаем все элементы первого столбца матрицы D. Просматриваем вторую строку матрицы R и выбираем максимальный элемент r23 = 3 для элемента №3. Его устанавливаем в 1-ю позицию, а 3-й столбец матрицы исключаем из дальнейшего рассмотрения: 4 7 1 [2] 1 2 0 0 3 2 0 R = 4 0 0 5 0 0 6 0 3 7 0 0
1* 2* 3* 4* 5 6* 7 1 0 1 2 3 3 2 5 2 1 0 1 2 2 1 4 3 2 1 0 1 3 2 3 D = 4 3 2 1 0 4 3 2 5 3 2 3 4 0 [1] 4 [17] 6 2 1 2 3 1 0 3 7 5 4 3 2 4 3 0 21 . Далее выбираем min S d1j = 17, соответствующую позиции №5. Среди по- J=1 меченых элементов пятой строки матрицы D {d51, d52, d53, d54, d56} находим, минимальный: d56 = 1. Помечаем все элементы пятого столбца матрицы D. В шестой позиции размещен элемент №1. Поэтому просматриваем первую строку матрицы R, находим max rij=2 для модуля №4. Размещаем модуль №4 в позицию №5, исключаем из дальнейшего рассмотрения четвёртый столбец матрицы R:
1 1 1 2 0 3 0 R = 4 0 5 0 6 3 7 0
а) б) Рис.3.1 Рис.3.2
1 2 3 4 5 6 7 1 0 1 2 3 3 2 5 2 1 0 1 2 2 1 4 3 2 1 0 1 3 2 3 D = 4 3 2 1 0 4 3 2 5 3 2 3 4 0 1 4 6 2 1 2 3 1 0 3 7 5 4 3 2 4 3 0 21
Последний седьмой модуль, следовательно, попадает в оставшуюся свободной седьмую позицию. Результат размещения дан на рис. 3.3.
Рис.3.3.
Суммарная длина соединений получилась равной 35 условным единицам.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (650)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |