Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год (999411), страница 43
Текст из файла (страница 43)
Скалярное произведение векторов будет минимальным, если элементы одного из них упорядочить по возрастанию, а другого — по убыванию. Пусть М М -- 4, т. е, необходимо разместить четыре элемента в четыре позиции. Предположим, что элементы первых строк матриц К и Р«в результате упорядочивания располагаются следующим образом: К, =- г, „гмь г„(гг а ( гх«( г,») и Р, е(х„«1«з, пхз (е(х«) с(ха ) с(хз). Тогда скалярное произведение (ЯыО,) -- г,ае(х« — ', «х«е(,» + гхзс(ха является нижней границей суммарной длины связей первого элемента при установке его в первую позицию (предполагаемое расположение неразмещенных элементов относительно первого показано на рис.
10.4). Нижняя граница суммарной длины связей неразмещенных элементов е„е„е, может быть вычислена как минимум скалярного произведения наддиагональных элементов матриц К и Р„без элементов первых строк. Обозначим его как (Я, 1Т). Очевидно, что при отсутствии начального размещения сумма нижних границ (Р„Т»„) -1- (»с, »») будет характеризовать сцену назначения> первого элемента в первую позицию. Выбор элемента и позиции его установки' может выполняться по специальной матрице В =- [[Ьп»[[~м -к>»п»» кь элементы которой определяют «цену назначения» Ого конструктивного элемента в»"-ю позицию при условии, что К элементов уже размещены. Матрица В формируется заново после размещения каждого конструктивного элемента.
Существуют различные стратегии выбора элемента и позиции по матрице В. Рассмотрим алгоритм, использующий принцип максимпна (см.,[П). Исходные данные для работы алгоритма — матрицы 1! и Р„, множества индексов размещенных и неразмещенных элементов »„»!»'х, множества индексов занятых я свободных позиций Т„и Т„. Основные пункты последовательного алгоритма размещения, использующего принцип максимипа. !, формируем матрицу оценок В. Для каждого (Е Х» и )Е Т„ вычисление элемента Ь; » заключается в выполнении следующих подпунктов: 1.!. Исключаем из Ой строки матрицы )2 элемент г,; и из )-й строки матрицы Р, элемент «(»». 1.2.
Элементы Ьй строки матрицы [1 и 7-й строки матрицы Р» разбиваем на вектора )с» и )с'„Р» и Р» в соответствии с принадлежностью индексов элементов !' Е»'„или / Е Уа, а индексов позиций» Е Т„или »'с 7ю 1.3. Выполняем сортировку элементов вектора )с; в соответствии с позициями их установки в векторе Р» (обозначим этот вектор»с»') и находим скалярное произведение Ь;;» == (%, В»), т. е. определяем суммарную длину соединений размещаемого элемента с размещенными по (!0.7) без линейного члена. 1.4. Упорядочиваем элементы вектора »с; по возрастанию, а вектора Р» по убыванию, обозначим полученные векторы »с» и В». 1.5. Находим нижнюю границу суммарной длины связей Ого элемента прн установке его в»по позицию с неразмещенными элементами как скалярное произведение векторов »(г н Р»', т.
е. Ь;л =. ()с[, Р»). 1.6. Считая Ьй элемент размещенным, из паддиагональных элементов матрицы»с, определяющих связанность неразмещениых кон. структивных элементов, формируем вектор )с' (гн „,: п, т Е Еl„',! Е т — и+ 1). 1.7. Считая»-ю позицию занятой, из наддиагоналнных элементов матрицы Р„формируем вектор расстояний незанятых позиций Р (с(„,„,:п,тЕТ„'.)Ет - п! 1). 1.8. Упорядочиваем элементы вектора»с по возрастанию, а вектора Р по убыванию. Обозяачим их»с'" и Р" . !.9. Находим нижнюю границу суммарной длины связей иераз» метенных элементов между собой: Ь,.» - ()с"', «»"'). 2В4 1.10. Вычисляем элемент Ь, » - Ь,» -«- Ь;,» 4 Ь;,».
2. В матрице В определяем минимальные элементы каждой строки и каждого столбца: В,. =! гп!и Ьс»); В, =-[ ппп Ьс;!. !»=- и»«-и» ~ » = ь л'-к 3. Выбираем максимальный из минимальных элементов строк и столбцов Ьс „— шах (Во В»). Здесь д и р — индексы размещаемого на данном шаге работы алгоритма элемента и позиции его установки. 4. Заносим индекс элемента в множество «», а позиции — в множество Т„, исключая их из,»„и Т„: У„-.У»[[д;.»„-:У„",д; Т, Т«() р; Т„=Т„,р.
5. Проверяем, все ли элементы размещены; [,»»[ - А'. Если условие вьиолняется, то переходим к и. 6, иначе — к и. 1. 6. Конец работы алгоритма. $«а.з. УЛУЧШЕНИЕ РАЗМЕЩЕНИЯ пеРестАИОВнОЙ мОдулей Алгоритмы этой группы используют ту же идею, что н итерационные алгоритмы улучшения компоновки (см, 4 9.3), Для улучшения некоторого начального размещения меняются местами те элементы, перестановка которых приводит к оптимизации критерия каче- а!» 2 5 Ж» 2 Г ства. Процесс заканчивается, ес- а е н, е е, е лп ие существует перестановок, 4 5 улучшающих критерий качества, плп когда разность значения Критерия для двмх соседних Рнс.
!0.3. Внрнннтм рнзнсщсннн»лснснптерапий будет меньше некото- тан рого заданного порога е. Реализащ»я итерационных алгоритмов связана с болыпим объемом вычислений, Поэтому применяют в основном алгоритмы, использующие парные и упорядоченные перестановки. Положим для определенности, что критерием качества размещения является минимум суммарной длины соединений Е (а). Соечинения элементов схемы определены матрицей »с, а расстояния между установочными позициями — матрнцей Р,.
Имеется некоторое начальное размещение. Элементы матрицы ц должны располагаться в соответствии с порядковыми номе- рамп (индексами) позиций их установки. Например, для начального размещения трех элементов (рис, !0.5, а) матрица О! 2 Р, ! 0 1, а в матрице )с первая строка должна характеризовать 2!О связность элемента е» с элементами е» и ео вторая строка — -элемента е» с элементами е» и е,, третья строка — элемента е, с элементами е, 205 (034~ У,...бр...Кр.. у,...д...р...,.......,р..
2 ! Р бр~! !!450 Переставляя элементы е; и е;, необходимо в матрице 22 менять местами соответствующие им строки и столбцы. Тот же результат, в смысле возможности оценки Р (а) поэлементным перемножением матриц»2 и 0„, можно получить, сохраняя неизменной матрицу й и располагая элементы матрипы 0„в соответствии с индексами установленных в них элементов. В этом случае для рнс. 10,5, а матрицы 11 и Рр соответственно будут иметь вид 021 201 1 1 0 045 4 Г) 3 530 В дальнейшем после изменения пози»»ий элементов е» и е; корректируем матрицу Ор посредством перестановки в ней строк и столбцов, определяющих расстояния переставляемых элементов до остальных.
Например, при перестановке элементов е, и еб, как показано на рис !0.5, б, в матрице Р, необходимо поменять местами первые и третьи строки и столбцы. Тогда матрица 0 1 1 102 ! 2 0 приращения функционала ЛР матрицы 11 н О„ при установке во вторую, е,— в третью и е,— Для данного размещения суммарная взвешенная длина соединений Р»у = г»2»(»2 '! г»3»Г»3 ' гуА4 ' г2Ф23 " г24п24+ 234»(32.
Поменяем местами элементы е, и е,. Тогда в матрице О„перестав»»м первые и третьи строки и столбцы и получим Для такого размещения значение функции качества Р, — г,х»1,', -Е г»3»13» 1- г»4»(34 + г23»(2» 1- г24»(24;. г34»(44. Найдем приращение Получим выражение для подсчета Рч — Р,. Запишем в общем виде элемента е, в первую позицию, 2»в в четвертую: 0 г»2 г»3 гу4 0 г23 »24 г„г„О г»4 »'4» г»2 г»3 0 О»(32 »23 О »(»3»(»2 »(43»(42 0 12» 0»(23 «24 »13!»Гу»2 " »134 '1»п»(42»(43 О »13»»134 0 »14» 0 функции качества ЛР -- г»2 (»Г»2 — »(32) + гы (»1»4 — »(34) + 223 (»123— »!»П) +»34 (»(34»Р»4).
После несложных преобразований получим ЛР— — (г„— г, ) (»(»2— — »(32) + (г„— г„) (»Г»4 — »(34). В общем виде ЛР=-Х(г»,.— г»,.) (»(ь.— »(»2.): 3Ф»,1. (10.9) р Здесь 3 — индекс элемента, не участвующего в перестановке. В итерационных алгоритмах парных перестановок используют различные способы упорядочивания переборов для уменьшения числа возможных перестановок. Один из таких способов заключается в следующем: для данного размещения определяется суммарная длина связей Р» каждого элемента с остальными как скалярное произведение соответствующих строк матриц 11 и 0„: Р»=-~~ гь, Гь»2 (10.10) »=1 Номера (индексы) элементов упорядочивают по убыванию Р;: Г = (»», », "., »м); Р» > Р - ...
> Рм. На очередном шаге алгоритма рассматривают возможные перестановки элемента»'„с элементами из подмножества (»„„»2„, ..., »»»). После окончания цикла итераций подсчитывают новые значения Р» и процесс может быть повторен. Основные пункты итерационного алгоритма парных перестановок. Исходными данными для работы алгоритма являются матрицы В и 0„. 1. Определяем порядок просмотра элементов. Для существующего размещения по (10.10) находим суммарную длину связей Р» каждого элемента. Упорядочиваем индексы элементов по убыванию Рь т.
е. формируем последовательность индексов элементов у =- 1»„ »„ ..., »4»). 2. Для текущего элемента последовательности » Е У по (10.9) определяем приращение ЛР;„;; 1Е.Г„„--- (» „, ..., »~). 3. Находим ЛР», » = шах ЛР»„,;. »'Ы24.4 4. Проверяем условие ЛР»,» ) О. Если условие выполняется, то 'Й '2 в последовательности » меняем местами индексы»2 и» 2, в противном случае переходим к п. 6. 5.
Корректируем матрицу В„, т. е. переставляем строки и столбцы с индексами»„и» . 6. Проверяем условие окончания цикла итераций !12„! =- О. Если условие выполняется, то переходим к п. 7, иначе выполняем 12 = я + 1 и переходим к п. 2. 7. Проверяем условие окончания итерационного процесса ЛР/Р2» ( а. Если условие выполняется, то переходим к и. 8, иначе— к п. 1. 8. Конец работы алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
