книги / Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Автоматизация конструкторского проектирования вычислительной техники
.pdfБ. Построение другой вспомогательной матрицы faxm для корректировки решений последней ЗОН и получение множества допустимых решений ИЗ.
В. Определение локального минимума ИЗ на ограниченном множестве допустимых решений путем полного перебора его
элементов. |
|
|
Пусть е*£ и И /<2)=*// |
||
О ш п ш ^ л ^ ^ |
|
||||
где |
' |
|
|
|
|
|
|
4 JM |
r i f J> |
|
15 > |
пщ |
> & |
- достаточно большое |
число, |
обозначаем |
|
мое ниже |
|
при i ± j |
|
|
|
Величиной |
|
определяется, |
таким |
образом, ре |
зультат группирования по 2, т.е. число элементов разных ти
пов в блоках |
i |
и J -Пусть |
в результате решения ЗОН мини |
|||||||
мизируется функционал fz - £ 3 j |
и полученное решение |
|||||||||
Afl |
представлено в |
форме (fe/: |
|
|
|
|||||
|
|
^ Z |
= |
|
Ь |
|
• *V ^ |
V ^/77JJm)}j |
|
|
где |
tg |
и j j |
определяет |
соответственно строку |
и столбец мат |
|||||
рицы |
либо |
/^ п р и ч е м |
|
П у |
с т ь и |
ре |
||||
шено £ - / ЗОН при использовании матриц стоимостей |
|
|||||||||
|
|
Требуется построить |
матрицу /^^Чфи условии, -что мно |
|||||||
жество |
A f^r |
уже известно |
и записан? в виде |
(7): |
|
|||||
|
|
|
|
|
|
|
Cc7j |
|
-)}• |
(7) |
|
Для этой дели необходимо выписать из Afe4 решение ЗОН, |
|||||||||
т.е. элементы, заключенные в круглые |
скобки в |
(7), поставить |
||||||||
их в |
соответствие строкам |
И/^столбцами Ж^выбрать эле |
||||||||
менты множества |
|
(8): |
любой элемент «''•^искомой |
|||||||
матрицы определить по |
|
|
^ |
|
||||||
|
|
|
Сесмс |
& & |
к) Vt j ^ S f V i |
|
(8) |
|||
|
|
|
=Jj пто ■*£ п у ■»AtJ. |
|
|
|
||||
|
Обоснование метода. Пусть заданы следующие пары: |
|
||||||||
|
|
|
|
|
|
|
и C*Ajjk)& fif&. |
|
О ) |
|
|
Пары вида |
(9) |
назовем £2£Н££1имыми, если выполняют |
|||||||
ся следующие условия: |
|
|
“ // |
• В нротМв- |
5 1
ном случае их будем назьшать несовместимbiwji. Множество совместимых пар вида (9) будем называть полным, если в результате их объединения, т.е. применения операции (J над всеми парами этого множества, получается множество ( ft2r ..
Иначе множество совместимых пар называется неполньш. Неполное совместимое подмножество множества (6) будем на зывать максимальным, если добавление к нему любой пары из
(б) превращает данное подмножество в несовместимое. Подмножество £ будем называть дополнением_ максималь
ного неполного совместимого множества */J |
сМ2)3если |
|
Имеют место следующие утверждения. |
|
|
Лемма JL. Еслил7 = ^/1 И существует такое |
решение ЗОН с |
|
матрицей |
в нем содержится полное множество совме |
стимых групп, то это множество является допустимым реше нием исхош ой задачи.
То, что полное множество совместимых групп удовлетво ряет ограничениям (2), (3) и (4 ), следует йэ его определе ния и того факта., что каждое подмножество в круглых скоб
ках в |
(7) содержит различные индексы. |
||
ЛеMMa^2. Ерли Xj> есть |
решение задачи о назначениях с |
||
матрицей стоимости |
{пъ четно), то мощность макси |
||
мального совместимого подмножества |
Hg(iHg с М^) удовлетво |
||
ряет следующему неравенству: |
|
||
|
Рассмотрим два |
крайних случая. |
|
Случай^. Решение ЗОН Х& состоит только из циклов чет |
|||
ной длины. |
|
|
|
Случай_2. Решение |
является |
множеством только не |
|
четных циклов и притом длины 3. |
|
||
В случае I мощность полного совместимого подмножест |
|||
ва |
множества Мг есть |
не что иное как мощность наиболь |
|
шего внутренне устойчивого множества £ графа решения за |
дачи, которое получается перечислением каждой второй верши
ны. П о э т о м у Т а к |
как каждая вершинам? |
может быть |
|
выражена двумя различными индексами, то |
|
Очевидно, |
|
что это значение является |
наибольшим. |
^ |
|
В случае 2 f£ l- m /3 |
и поэтому |
/77 |
Величина яв- |
5 2
ляется нижней границей 'M^l, так как не существуетнечет ных циклов меньшей длины. Поэтому /м£ / &/ту.
Непосредственно из приведенных определений и леммы 2 вытекает:
Если решение задачи о назначениях с мат рицей ^^представимо множеством циклов четной длины, то максимально внутренне устойчивое множество (МВУМ) этих циклов является допустимым решением исходной задачи (1^— (4), причем число допустимых решений определяется количе ством различных МВУМ.
Следствие 2. Мощность дополняющего множества & при удовлетворяет «следующему неравенству:
О* /V I < ”/з . |
|
Отметим следующие свойства матриц № се*. |
|
^ BO^JCTBO^I. М а т р и ц а п р и |
является симметриче |
ской, а при е>2 - несимметрической. Каждая ее строка и каждый столбец содержит в - f запрещенных-элементов, недо пустимых в решении некоторой ЗОН (недопустимый элемент соответствует двойному вхождению того же индекса в соот ветствующий элемент матрицы
Свойству.2.- Для каждой ^^сущ ествует решение ЗОН. Решение с матрицей стоимости tf/W может быть представле но множеством Не- Множество Не состоит из пь подмно жеств, мощность каждого из которых равна € t иначе любое подмножество - это скомпонованная группа из е элементов. Объединения некоторых из этих групп либо сами являются до пустимыми решениями ИЗ, либо группы могут быть скоррек тированы путем введения некоторых дополняющих подмножеств для получения допустимых решений ИЗ.
tfe |
Дэл^чение |
|
|
Множество |
представим |
в виде |
|
|
|
|
|
|
|
Gfj /«*v &*mJ j |
где |
% у -а я |
группа; |
tGyf* e |
для всех J- Отметим, что |
две |
различные |
группы |
fy. и Sej |
обладают следующим свойст |
вом: |
|
|
|
0 £ / Gf; /7 GC;/ £ &,
5 3
Построим другую матрицу 1/т хт |
по правилу: |
UGe:l |
||||
при (? j |
и |
= л' |
при с у - |
|
|
|
Очевидно, что |
элемент Vij>o |
определяет для групп Qg. и |
||||
мощность дополняющего множества для того, чтобы скор |
||||||
ректированная группа Get U Ct'ej была допустимым решением ИЗ. |
||||||
Если же |
v ij-O , то множество QqC/Gq уже является |
допусти |
||||
мым, Общее число множеств Gg. UGej при i,j~ /Jmfrfj) |
равно |
|||||
-М{/л-1)/2 |
и встает |
вопрос о том, |
какие,из |
них выбрать. Мони |
||
но использовать несколько стратегий: 1) |
просмотреть все |
frrcm-f)/2 множества; 2) выбрать те множества, |
которые соот |
||
ветствуют некоторой |
совокупности минимальных |
в |
некотором |
смысле элементов. Дополняющие множества JP |
в |
общем слу |
|
чае для групп Gei и |
Gej получаются по формуле |
(1 0 ): |
|
Z) |
т } \ (йе^ UGej)* |
|
|
Для нахождения множества допустимых решений Хд ИЗ необходимо: а) определить лдля групп фу и ^подмножество
заменить <л*//7Gej дополняющим множеством D в
гругше Gei либ° |
’ т*е* получить |
либо |
|
eXpCGe; (Gcj) - |
скорректированная группа,соответст |
||
вующая Gfga £ j))jB) повторить шаги а и б для всех i YLJ . |
|||
Для определенности при выборе групп по матрице \Х бу |
|||
дем пользоваться |
стратегией 2 (см, выше), |
решая дополни |
|
тельно ЗОН с матрицей |
V и при минимизации соответствую |
щего функционала. Решение этой задачи уожно использовать для корректировки и получения Множества допустимых реше ний ИЗ. Может показаться, что в случае л =2 это нецелесо образно, так как'вычислительная сложность стратегии 2 0(ms) (имеется в вицу венгерский алгоритм [3 ]), а при выборе стратегии 1 получим результат не хуже пртг объеме вычисле ний (7(т2).Выбор стратегии 2 может быть оправданным в смыс ле единства реализации метода и в том, что она дает возмож
ность получить группы при Л >£ (этот случай |
здесь не рас |
||
сматривается), |
|
исходная |
|
матрица т |
решение ЗОН обозначено |
||
кружками). |
5 4
|
1 2 3 4 5 6 7 8 9 |
10 |
|
|
1 2 3 4 5 6 7 8 9 |
10 |
||||||||||
г |
0 0 1 1 0 0 0 1 0 1 |
|
1 |
- 6 8©7.6 9 7 7 7 |
||||||||||||
2 0 1 0 1 0 0 0 0 1 0 |
|
2 |
6 - 6 7 6 6 7®5 7 |
|||||||||||||
3 1 1 0 1 1 1 0 0 0 0 |
|
3 8 6 - 7 8 9© 8 7 9 |
||||||||||||||
4 1 0 1 0 1 0 0 0 0 1 |
|
4 ©7 7 - 6 7 7 7 6 8 |
||||||||||||||
5 1 1 1 0 0 0 0 0 1 1 |
|
|
7 6 8 7 - 7 8 8©8 |
|||||||||||||
« = 6 0 0 0 0 0 0 1 1 1 1 |
|
*6 6 6 9 7 7 - 8 7 6© |
||||||||||||||
7 1 1 0 0 1 1 1 0 0 0 |
|
7 |
9 7©7 8 8 - 8 7 9 |
|||||||||||||
8 0 0 1 1 1 0 1 0 1 0 |
|
8 7 0 8 7 8 7 8 - 87 |
||||||||||||||
9 i i o o o o o o i i |
|
|
9 |
7 5 7 6©6 7 8 - |
8[ |
|||||||||||
го |
0 0 1 1 0 1 1 0 1 1 |
|
to |
7 7 9 8 8©9 7 8 - ' |
||||||||||||
/$ = { (1.4). |
(2,8), |
(3.7), |
(4,.t), |
(5,9), (6,1.0), |
(7,3), |
|||||||||||
^ (8,2), |
(9,5), |
(10,6)} |
|
|
|
|
|
|
||||||||
1 |
1 2 3 4 5 6 7 8 9 |
|
TO |
|
|
|
|
|
|
|||||||
- |
8 8 - © 8 |
9 |
8 8 9 |
(1.4) |
ffj - |
/П -,4,5), |
|
|||||||||
2 8 - 8 8 8 8 8 - 8 ® |
(2,8) |
(3,7 ,9 ), |
||||||||||||||
(2 .8 .1 0 ) |
, |
|||||||||||||||
|
9 7 |
- |
8 9 |
9 - |
8 ® 9 |
(3,7) |
(1 ,4 ,3 ), |
|
(5,6,9), |
|||||||
|
- |
8 ® - 8 8 9 8 8 9 |
(4 .1) |
|
||||||||||||
|
(6 .8 .1 0 ) |
, |
(2,3 ,7 ), |
|||||||||||||
|
7 6 8 6 - © 8 |
8 - 8 |
(5.9) |
|||||||||||||
|
(2,7,8), |
|
(4,5 ,9 ), |
|||||||||||||
6 |
7 8109 9 -10(8)9 - |
|
|
|
||||||||||||
(6 |
. 10 ) (1,6,10 )j. |
|
|
|||||||||||||
7 |
9 © - |
8 9 9 - |
8 8 |
9 |
(7,3) |
|
|
|
|
|||||||
8 8 - |
8 8 8 8 ® - 8 8 (8.2) |
|
|
|
|
|||||||||||
9 |
7 6 |
8 © - |
7 8 |
8 - 8 |
(9.5) |
|
|
|
|
|||||||
10 © 8 1 0 9 9 - 1 0 8 9 - |
( 10,6 ) |
|
|
|
||||||||||||
|
г |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
го |
|
|
|
|
|
|
1 |
- эго |
- - - 1 0 © 9 |
го |
(1,4,5,6) |
^=(1.4,5,6,8); |
|||||||||||
2 |
to - ® |
9 |
эго |
_ - |
9 |
- |
(2,7,8,10) |
£,,=(2.3,7,8,10) |
||||||||
3 |
to |
9 - |
9 © 1 0 |
_ 9 - |
- |
(3,7,9,10) ^=(3,5,7,9,10) |
||||||||||
|
_ 9 |
- |
- - г о г о г о © го |
(1,3,4,5) |
fy,=(i,3,4,5.9); |
|||||||||||
1/1/(я 5 |
9 эго — . _ |
© 9 |
- го |
(4,5,6,9) |
<*,=(4.5,6,7,9);. |
|||||||||||
6 |
• 9 1 0 Ш 0 - го - 10 - |
(1,6,8,10) |
6,,=(1,4,6,8,10) |
|||||||||||||
7 |
га |
- - |
9 |
9 © |
- 9 - |
9 |
(2,3,7,9) £,,.=( 2,3 ,6 ,7 ,9 ); |
|||||||||
8 |
го 1 _ 9 эго — - 9 1 |
(2,3,7,8) |
|
|
|
|||||||||||
9 |
® |
- |
8 - - |
9 |
9 |
8 - |
9 |
(2,4,5,9) |
|
|
|
|||||
10 |
|
© 1 0 9 1 0 - 1 0 |
-го - |
(1,6,8,10) |
И |
|
|
|||||||||
<*,= (2 .3 ,7 ,8 ,1 0 ); |
<*,= |
( l , 2,4 ,5 ,9 ); |
(1,2,6,8,10). |
55
|
|
1 2 3 4 5 6 7 8 9 |
10 |
Можно образовать следу |
|||
1 |
- И 3 3 4 © 1 |
3 3 |
ющие пары групп: |
||||
2 |
|
1 - 3 1 1 2 3 5 |
©3 |
Gez и G*$j |
и Gcd |
||
3 |
1 3 - 3 3 0 3 3 |
2 1 |
и &ем) |
Qcs и 6*/** |
|||
4 |
|
3 1 3 - 3 2 2 |
©4 1 |
которые являются наибо |
|||
5 |
|
3 1 3 3 - |
2 3 1 3 |
© |
лее ''близкими* |
к допу |
|
/Лг 6 |
4 2 © 2 |
2 - 1224 |
стимым. |
|
7 ©3323 1- 3 2-2
81 5 3 0 1 2 3 - 1 3
93 0 2 4 3 2 2 1 - 2
103 3 11©4 2 3 2 -
Врезультате выполнения шагов а), б), в) и применения
(10)получится ((//€ !> ):
|
^/=А0> ; |
6, ав, |
~(2 |
а2={в}; |
M V P ° J * |
4 = /2 ); |
а^пве, |
=(3Ь |
^ = /6 } ; |
/Гй |
= (1,4,5,8,10), |
(2,3,6,7,9); |
'(1,4,5,6,8), (2,3,7,9,10);
всгиЬя = (3,6,7,8,10), |
(1,2,4,5,9); |
|
||
* * * « ! . - ( 3 , 4 , 5 , 7 , 9 ) , |
( 1 , 2 , 6 , 8 , 1 0 ) ; |
|||
***°4ь- ( 4 , 5 , 6 , 7 , 9 ) , |
( 1 , 2 , 3 , 8 , 1 0 ) . |
|||
Для получения оптимального (в локальном смысле) реше |
||||
ния Х9 необходимо для каждого допустимого решения 6 ^ 06^ |
||||
вычислить |
значение |
целевого функционала |
F и выбрать |
|
множество Ge£.U0ejo , |
минимизирующее. А. (Для |
рассматрива |
||
емого примера ^ = 18). |
|
|
||
В^чис/штельная |
|
|
|
ложения. Так как венгерский алгоритм для решения ЗОН име ет сложность 0(т 3) [3] , то при <*/2 -кратном его применении в предлагаемом методе получим оценку 0(т+)Л\щ больших т метод требует значительных затрат машинчоготвремени, поэто му в реальной системе для подготовки программ сборки ис пользуется последовательный алгоритм сложности 0(fn2) ^ хо де предварительного эксперимента сравнивались результаты этих двух методов при п = 2 щИз 15 сравнений только в двух случаях функции цели оказались одинаковыми, а во всех ос тальных описанный метод дал лучшие результаты {т> изменя лось от 10 до 3 0 ).
5 6
Объем вычислений в предлагаемом методе можно умень шить на порядок, если на этапе А использовать эвристические процедуры сложности 0ст*)ъщ решения ЗОН. Нет принципиаль ных затруднений учитывать заданное число блоков того же ти па и повторяемость того же элемента в блоке. В этом случае
(4) превратится в неравенство. ДОотод в общем случае являет ся локально оптимальным. Если же при компоновке групп по два блока решать не ЗОН, а вспомогательную задачу нахожде ния минимального совершенного паросочетания в полном неори ентированном взвешенном графе с матрицей соединений то получим для этого случая оптимальное решение.
Эксперимент проводился Авиженисом. Ряд полезных заме чаний быловысказано Палубецкасэм при обсуждении метода. Автор выражает им искреннюю благодарность.
Ли т е р а т у р а
1.СЕЛЮТИН В.А. Машинное конструирование электронных
устройств. - ДО» : Советское радио, 1977. - 384 с.
2. ГИЛЬБУРД М.М. Об эвристических методах решения задач разбиения множества взаимосвязанных объектов. - Ав томатика к телемеханика, 1984, N? 1г с. 107 -113 .
3. КРИСТОФИДЕС Н. Теория графов (алгоритмический подход). - M.s Мир, 1978. - 432 с.
УДК |
6 8 1 .3 2 3 .6 5 |
СИНТЕЗ ТОПОЛОГИЧЕСКИХ УКЛАДОК С МИНИМИЗАЦИЕЙ ЧИСЛА МЕЖСЛОЙНЫХ ПЕРЕХОДОВ
Р.П. Б а з и л е в и ч , Ю.М. Г рес ьк о
На этапе топологической трассировки двухслойных струк тур при синтезе укладок множества £ электрических соеди нений решаются две основные задачи: определение для каждо го слоя наибольших множеств взаимэнепересекаюшихся соеди нений [1J и минимизация числа межслойных переходов для нереализованных соединений. Эти задачи взаимосвязаны: из вестно, что для реализации в двух слоях каждого из не во-
57
шедших в плоские укладки соединений без учета метрических ограничений достаточно одного перехода. Но в рамках реаль ных задач трассировки такие решения практически неприемле мы, ибо приводят к значительному усложнению топологическо го рисунка, деформации и удлинению трасс. Поэтому при даль нейшем рассмотрении задачи минимизации числа межслэйных переходов ограничимся следующим условием: любые два соеди нения • Ej находящиеся в отношении пересечения, при, ус ловном наложении их топологических укладок не могут иметь более одного пересечения. Это условие позволяет ценой прием лемого проигрыша по числу переходов упрощать поиск решения и улучшать качество монтажа.
1.
Предположим, что поверхность монтажно-коммутационного поля описана моделью в виде дискретного топологического ра бочего поля, состоящего из множества граней (макроцискретов), вершины которых соответствуют контактам соединений [IJ, Пусть на предварительном этапе топологического реше ния задачи все соединения уложены на такой модели без уче та наличия пересечений между ними. Тогда задача сводится к определению минимального числа переходов, которые обеспе
чивают такую геометрическую реализацию трасс, когда их уча стки между межслойными переходами не пересекаются. Для решения задачи в целом предварительно необходимо разрабо тать методы и алгоритмы ее решения в пределах одной или нескольких смежных граней, образующих некоторую область*;. Рассмотрим формальную постановку задачи и пути поиска ре шения.
Пусть задано множество X точек пересечения соединений множества £ш )с £ с контуром области со. В множество X могут входить, в частности, контакты этих соединений, форми рующие грани дискретно-топологического рабочего поля, обра
зующие область |
Элементы множества X образуют цикли |
ческий кортеж А |
W .Учитывая принятое ранее ограничение, |
необходимо синтезировать такие две плоские укладки соедине ний £Уо/>.,для построения которых требуется минимальное чис ло межслойных переходов.
2.
Для решения задачи выделения плоских укладок без пере ходов в качестве математической модели обычно используется граф пересечений и поиск сводится к нахождению наибольших внутренне устойчивых множеств его вершин. Соединения каж дой полученной укладки можно построить независимо. Появле ние же в укладках фрагментов соединений с переходными от верстиями, которые топологически связывают обе укладки, су щественно усложняет задачу и требует такой математической модели, которая однозначно описывает структуру взаимного расположения соединений на двух слоях.
На рис. X представлено некоторое топологическое распо ложение в области от множества соединений Е (u/)jчьи выво ды образуют по контуру циклический кортеж Л .ш (Х).Вполне естественно, что система точек пересечения этих соединений внутри области неоднозначна. Достаточно некоторого тополо гического перемещения произвольного соединения, чтобы ее изменить. Для описания данной топологической ситуации, од нозначно определяющей систему точек пересечения соединений и образованных внутренних граней, возможно использование различных моделей. Так, достаточно для каждого соединения
б £ (cuj задать кортеж |
Л, или задать |
множество |
WC&j |
внутренних граней, образованных отрезками |
соединений, |
с оии- |
5 9
санием характеристик их смежности и списков отрезков соеди нений, их образующих,
.Ситуацию внутри области со опишем плоским графом сов мещенной топологической укладки G^CZyi/),множество Z вер шин которого соответствует условным точкам пересечения со единений множества E(co)>* ребра - отрезкам этих соедине ний, находящихся между двумя вершинами.
Соединения множества Е(аг) могут быть раскрашены ввдва цвета тогда и только тогда, когда множество i/i/Cco) не содер жит иечетиых граней, И как следствие - в графе ffZ ^образо ванном двумя плоскими укладками, все грани множества И£(си] четные, В противном случае была бы невозможной бихроматическая раскраска соединений множества £ Ссо)*
Для раскраски в |
два цвета соединений |
множества ЕС<о)^об |
разующих граф |
с нечетными гранями, |
необходимо такие |
грани трансформировать в четные путем введения* дополнитель ных вершин, соответствующих переходам со слоя на слой (рис, 2, б, д). Введение каждой новой вершины-перехода из меняет степень двух смежных граней, инцидентных ребру, на котором эта вершина расположена.
На рис. 2а представлено 6 соединений, образующих две плоские укладки. На рис, 2 б, в, г, д постепенно изменяется место расположения одного из контактов на кортеже -Л-о> CV таким образомь что число пеоесечений возрастает. Это приво дит .к возникновению новых нечетных граней (заштрихованы). При последовательной раскраске в два цвета соединений, об разующих нечетную грань, на последнем из них возникает кон фликт: O H D оказывается смежным с раскрашенными в разные цвета соединениями. Соединения, образующие четную грань, однозначно раскрашиваются в два цвета, которые сохраняют ся в последующих четных гранях.
Для заданг го графа существует множество вариан тов трансформации нечетных граней в четные с различным чис лом переходов, каждому из которых однозначно соответствует свой вариант бихрэматической раскраски соединений. Числом переходов /о графа будем считать то минимальное чис ло переходов, с вводом которого все его грани становятся четными. В общем случае для графа & со может существовать множество различных бихроматических раскрасок соединений с числом^. Для получения суб оптимальных раскрасок предла гается использовать следующий подход:
6 0