Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год (999411), страница 38
Текст из файла (страница 38)
Включаем в множество вершин Хг формируемого куска б~ некоторую вершину х, т. е. Х1-— — (ха). 2. Определяем мйожество вершин, смежных вершинам Хь т. е. ГХь 3. Для каждой вершины подмножества Х' =- (х;: х; Е ГХ, д х;6ЕХ,) подсчитываем показатель 6 (х;). 4. Находим 6 (х,) = — ш(п 6 (х;); х; р ГХ~егхг 6~ Хь 5.
Вершину х, включаем в множество Хь т. е. выполняем Х, = =- Х1() х,. 6. Проверяем !Х,! "' пгь где па~ — число элементов в йй подсхеме. Если условие выполняется, то переходим к п, 2, иначе — к п, 7, 7. Кусок б~ сформирован. 8. Конец работы алгоритма. Последовательный алгоритм разбиения гиперграфа схемы. На текущем шаге алгоритма в качестве кандидатов на включение в формируемое подмножество Х~ будем рассматривать только вершины, связанные с вершинами, уже вошедшими в Хь Гиперграф задаем в виде множества вершин Х =- (х;Й = 1, А~), множества ребер У =- =- (иД = 1, М) и многозначных отображений Х в (7, т..
е. ГХ = = — (Гхгб = 1, .Ч), и У в Х, т. е. ГУ = (ГиД =- 1,64), причем Гхг -- Уг ~ У вЂ” множество ребер, содержащих вершину х;, и Гик —— =-- Хк о= Х вЂ” множество вершин, инцидентных ребру ик. Множество вершин — кандидатов на включение в Хг определяется следующим образом: по отображению Л' в У находим множество ребер, содержащих вершины подмножества Х~ . .ГХ, — Г ~ У. Затем по отображению У в Х получаем множество вершин, инцидентных ребрам подмножества (7': Гбп == Х' о: — Х. Кандидатами на включение в Х, будут вершины, удовлетворяющие условию х1 ~ Г Г ег х; е= Х',Хь евг Очередную вершину хз выбирают по минимуму ребер ип содержаьцих хотя бы по одной вершине из Х, Ох; и Х ', (Х,() х ).
Для таких ребер должно выполняться условие В ха, хп ~ Г иу (к, Е= (Х~ () хД д хр . = Х',(Хг () х,)). На основании (9.5) количество ребер, для которых выполняется это условие: 5 (Х,()хг)=-.~Г (Х,()хг) () Г (Х', (ХсО хЩ, (9.8) Основные пункты алгоритма последовательного разбиения гиперграфа: 1. Включаем в формируемое множество Х~ некоторую вершину х:Х,=-(х ). е) ,Г' ' а,'„3 е,; 2 е 3 4' х- г х, е з-; кс 1 взх ',а Е х хз ь Рис. 9.3.
Мультиграф схемы, данной иа рис. 9.1, и ае компоновав последовательными алгоритмамя разрезания мультиграфа и гпперграфа 1аз 2, По отображению Х в У определяем множество ребер У', ин- цидентных вершинам подмножества Хь т. е. ГХ, = У' ~ Ц, 3. По отображению У в Х находим множество вершин, соединяе- мых этими ребрами ГУ' =- Х' с= Х, 4. Для варианта включения каждой вершины множества Х» = = (х,: к; Е ГУ' гг х; ~ Х' ХД подсчитываем по (9.8) 5 (Х, () х;).
5. Определяем вершину хп для которой значение 5 (Х~ () х,) ми- нимально. 6. Проверяем условие 5 (Х~ О х,) ~ йь где /г~ — число внешних выводов 1-й части схемы. Если условие выполняется, то переходим к и. 7, иначе — к п. 9. 7. Вершину х, включаем в формируемое множество: Л', = Х, () х,. 8. Проверяем условие !Х~! гпь где т, — число элементов 1-й части схемы. Если условие выполняется, то переходим к п. 2, иначе— к п.
10. 9. Дальнейшее формирование подмножества Х, невозможно из-за нарушения ограничения по числу внешних выводов, переходим к п, 11. !О. Подмножество Хг сформировано. 1!. Конец работы алгоритма. Проиллюстрируем работу обоих последовательных алгоритмов на примере разбиения схемы (см. рис. 9.1) на два узла по три элемента в каждом. Модель этой схемы в виде мультиграфа показана на рис. 9.3, а. Напомним, что при переходе от схемы к графу каждан цепь представ- ляется полным подграфом, построенным на вершинах, инцидентных этой цепи, а мультиграф получается объединением полных подграфов. Работа алгоритма разрезания мультиграфа: 1.1.
Пусть на первом шаге Хз =- (х,). 2.1. Множество вершин, смежных Х„будет ГХ, = (хз, х4 хз). 3.1. Для Х = (х„х4, хз) подсчитываем показатели б (х;): 6 (хз) =- 4 — 1 =- 3; 6 (х,) =- 6 — 2 = 4; б (х,) =- 6 — 1 =- 5. 4,1. Выбираем вершину х,. 5,1, Включив последнюю в Х„получим Хз = (х„х,). 6.1. Кусок не сформирован, переходим к п. 2. 2.2. ГХ, == (х„х„х„х„х,.). 3.2. Для Х' = (х„х„х,) подсчитываем 6 (хз) = 3 — 1 = 2; б(х,)=-6 — 3=-3; 6(х,)=6 — 2=-4. 4.2. Выбираем вершину х,. 5.2. Включаем последнюю в Х, = (х„хз, хз).
6.2. Кусок сформирован, заканчиваем работу алгоритма. Результат разрезания показан на рис. 9.3, б. Число внешних выводов 5 =-- 6, суммарное число межсоединений В =- 3. Кенигово представление гиперграфа схемы (см. рнс. 9.1) показано на рис. 9.2. Множество вершин гиперграфа Х = — (х,, хз, х„х„хз, х,), множество ребер У = (и„й„йз, и„йз), отображение Х в У: Гх, =- (й„и„и,); Гх, = (й„и4); Гхз = (и,); Гх, = (й„из, й,); Гхз =- (и„и„й,); Гх, =- (из), отображение У в Х: Гйз = (х„хз); Гиз =- (хз, х4), Гиз -- (х,, х„хз); Гй, = (хз, хз, хз, хз); Гйз = (хз, хз). Работа алгоритма разбиения гиперграфа (без проверки условия п. 6): 1.1.
Пусть на первом шаге Хз = (х,). 2.1. Множество ребер, инцидентных вершинам подмножества, будет ГХз = У' = (йо и„из). 3.1. Множество вершин, соединяемых этими ребрами: ГУ' = = Х = (ХИХз,Х4,Хз). 4.1. Множество вершин — кандидатов на включение в Х,: Х" = = (х„х„х ). Подсчитываем 5 (Хз!!хз) -- 5;: 54 — !Г (хо хз) П ПГ (х„х,, х„х,)! =- ! (и„и„из йз) П (й йз йз йз)! = = !(й„из йз)! — 3; 54 — !Г (х„Х,) П Г (хз, хз хз, х,)! = = ! (й„и„из, йз) П (й„из, ио йз)! =- ! (й„йз йз)! = 3; 5 =- !Г (хз, х,) () Г (х,, хз, х„х,) ! = ! (й„й„и „й„й,) П П (йз, йм йз йз, йз)! == ! (й„йз йз йз йз)! = 5 5.1.
Выбираем вершину х,. 6.1 — 7.1. Включив последнюю в Х,, получим Х, =- (х,, х,). 3.1. Проверяем !Хз! = 2( 3, переходим к п. 2. заз 2.2. Множество ребер, инцндентных вершинам Х,: ГХ, = У' =— = (й,, й„из, й,). 3.2. Множество вершин ГУ' = Х' = (хз хз хз хз. хз). 4.2. Множество вершин Х" = (х„х„хз). Подсчитываем: 5, = !Г (х„х„х,) Д Г (х„х„х,) ! =- ! (и„й„и з, й,) П П (йз йз йз йз)! — ! (йм йз йз)! = 3' 5, = !Г (х„х„х,) Д Г (х„х„х,) ! =- ! (й„й„из, й,) П П (йз, й„й,)! = ! (йз, и,)! = 2; 5, = !Г (хз х„хз) П Г (хз х4 хз) ! = ! (й„йз, из, из, йз) П П (йз й з из, йз)! = ! (йи и з, йз, йз)! = — 4. 5,2. Выбираем вершину хз.
6.2 — 7.2. Включаем вершину х4 в Х, = (хз, х„хз). 8.2. Подмножество Х, сформировано, заканчиваем работу алгоритма. Результат разбиения показан на рис. 9.3,в. Число внешних выводов 5 = 4, суммарное число межсоедннений Я = 2. Как видим, компоновка схемы алгоритмом разбиения гиперграфа существенно лучше, чем алгоритмом разрезания мультиграфа, как по критерию числа внешних выводов 5, так и по критерию числа межсоединений Я. В работе П1! отмечается, что результаты работы последовательных алгоритмов зависят от назначения первой вершины и последующих вершин с равнымн оценками.
$ Р.З. ИТЕРАЦИОННЫЕ АЛГОРИТМЫ КОМПОНОВКИ Алгоритмы этой группы предназначены для улучшения некоторой исходной компоновки методом парных или групповых перестановок элементов из одной части схемы в другую таким образом, чтобы оптимизировать целевую функцию с учетом заданных ограничений. Начальная компоновка может быть получена вручную или последовательным алгоритмом.
Рассмотрим идею парных перестановок. Положим для определенности, что лучшему варианту компоновки соответствует минимум некоторого показателя Р. Пусть множество элементов схемы Е разбито на два узла — соответственно подмножества А и В. Обозначим исходный вариант компоновки йз, а значение целевой функции Рз. Предположим, что выбрана пара элементов азЕА и Ьз ь В, таких, что их перестановка приводит к уменьшению значения целевой функции. После перестановки а; и 5; получаем вариант компоновки йз и значение целевой функции Рз, причем АРз =- Р, — Р, ) О.
Процесс повторяется до тех пор, пока существуют перестановки, уменьшающие значение Р. В результате получаем последовательность вариантов компоновки Йз, йз, йз, ..., Й„ которым соответствует монотонно убывающая последовательность значений целевой функция Р:>Рз Р ...)Р,. 1В5 а) б) 6) ее а) Е Еа Еа Емсн Рис. 9.6. Пример группового об- мена: и — нето«на« номнононна: б — ре- зультат обмена (9.12) 1ВУ Такой итерационный процесс может привести к локальному оптимуму (Рг., йь), что иллюстрируется рис. 9.4, а. Пройти локальный оптимум позволяет метод групповых перестановок. Рассмотрим один из способов определения группы.
Для всех пар элементов а; ~А и Ь, Е Е В определяется приращение ЛР. Выбирается пара элементов, обозначим их а, и Ь„с максимальным ЛР н временно осуществляется их перестановка (значение ЛР может быть положительным, отрицательным и равным нулю). Процесс повторяется «яр раз до тех пор, пока все элементы подмножеств А и В не поменяются местами. Строится зависимость ЛР от шага обмена (рис. 9.4, б). По полученной кри- Рис. 9.4. Изменение зиачеиия целевой фуихции Р, приращения ЛР и их сумма Р ( — — — ЛР, — Р) г вой определяется шаг обмена йа, прн котором Р =- т; ЛР, - 0 и мак1=1 симальна (Т = 1, 2, ..., й). Выполняется обмен группы аг, а„..., а«а из узла А на группу Ь„Ь«, ..., Ь». из узла В. Пример группового обмена (см.
[!9)), улучшающего критерий межэлементных связей, показан на рис. 9.5. Здесь цифрами около линий, соединяющих элементы, указано число связей между ними. Обмен любой пары элементов не уменьшает число межсоединений. Перенос же элементов е, н е, в узел В, а элементов е, н е, в узел А приведет к уменьшению межузловых связей с 6 до 2, Итерационные алгоритмы компоновки обеспечивают лучшее качество решения, чем последовательные, однако требуют больших затрат машинного времени. Для окончания итерационного процесса может быть задано число итераций или их требуемая точность в виде условия ЛР1/Рг ( е. Рассмотрим итерационные алгоритмы улучшения компоновки схемы по ее мультиграфу и гиперграфу, осуществляющие только парные перестановки. Итерационный алгоритм компоновки по мультиграфу схемы.
Пусть мул ьтиграф О = (Х, (т) разрезан на два куска 6'=(Х', У') и 6' = 6~6'. Для каждой вершины ха Е Х мультиграфа вводится характеристика (см. 1101), которая количественно оценивает связность этой вершины с другими, лежащими вне данного куска, по отношению к вершинам, лежащим внутри его. Эта характеристика для вершины х1 определяется так: ~ г,(6') — О(6'), если ха ~Х', (9.9) а (х1)= ~ Г1 (О') — Га (О'), ЕСЛИ Х1 6: Х ' Х'; (9.10) где г, (6') — количество ребер, соединяющих вершину ха с вершинами куска 6', г, (6') — количество ребер, соединяющих вершину х; с вершинами куска О'. Перестановка двух вершин ха~ Х' и х; ~ Х',Х' приводит к уменьшению числа ребер, попадающих в разрез: если вершины ха и хг не смежны, при а (х;) + а (х,) » 0; если вершины х; и х; смежны, при а (ха) + а (хг) -» 2 лг1 1, где п«1 1 — количество ребер, связывающих вершины х, и х;.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
