<<
>>

Формирование плана методом свертки

Процесс синтеза плана при планировании кристалла включа­ет два этапа. На первом этапе синтезируется дерево разрезов. Задать дерево разрезов — это, во-первых, задать структуру этого дерева, т. е. задать последовательность бинарных разрезов, во- вторых, для внутренних вершин дерева, соответствующих разре­зам, указать тип разреза H или V. В-третьих, пометить листья дерева номерами областей [6.1].

Второй этап заключается в метризации плана, т. е. в опре­делении размеров областей, удовлетворяющих дереву разрезов и ограничениям [6.14].

Если модули имеют фиксированные размеры и ориентацию, то процесс метризации плана осуществляется путем последова­тельной бинарной свертки областей по дереву разрезов, начиная от листьев дерева. Каждой внутренней вершине дерева разрезов будет соответствовать область, полученная в результате бинар­ной свертки поддерева, имеющего корнем эту внутреннюю вер­шину. Будем считать, что разрез с номером i разрезает вершину

di(область Ui).Вначале свертки каждой вершине di,являю­щейся листом дерева разрезов, ставится в соответствие область riс размерами xi= hi, yi= wi,равными размерам модуля mi. В процессе свертки начальные размеры каждой области riмогут изменяться в сторону увеличения. Поставим в соответствие каж­дой внутренней вершине diдерева разрезов область Ui, которая образуется путем свертки поддерева разрезов, имеющего своим корнем вершину di.

Пусть в соответствии с деревом разрезов Dвершины diи djявляются дочерними вершинами вершины d⅛ и пусть для областей uiи uj∙, соответствующих diи dj∙, определены нижние границы их размеров (xi, yi), (xj, yj∙).

Процесс бинарной свертки представляет собой слияние обла­стей uiи uj∙, формирование области uk, определение размеров для ukи новых размеров для uiи uj∙.

Возможны два случая (аналогичных друг другу) в зависи­мости от того, каким индексом Vили Hпомечена вершина d⅛. Введем два инфиксных оператора: V и H. Запись u⅛ = uiHuj означает, что области uiи ujсливаются по горизонтали в одну область uk.Если uk= uiVuj∙, то области uiи uj∙ сливаются по вертикали.

На рис. 6.2, а показано слияние для случая V, а на рис. 6.2, б — для случая H.

Обозначим через max(xι,x2) максимальное значение из Xi и x2. При слиянии по горизонтали (рис. 6.2, α) yk= max(yi, yj∙); xk= xi+ xj; yiи yj∙ будет иметь размер, равный max(yi,yj∙).

При слиянии по вертикали (рис. 6.2, б) yk= yi+ yj∙; xk= = max(xi, xj∙); xiи xj∙ будет иметь размер, равный max(xi, xj∙).

Отметим, что после слияния изменение размеров одной из областей Uiнеизбежно влечет за собой изменения размеров некоторых областей, входящих в состав Ui.

Рис.

6.2. а — слияние областей для случая V, б — слияние областей для случая H

Рассмотрим два правила, в соответствии с которыми будем производить изменение размеров внутренних областей.

Если область uiувеличивается в размере yiна величину Δy = yj — yi,(рис. 6.3, а), то на эту же величину увеличиваются все вертикальные размеры всех областей внутри ui, границы которых примыкают (совпадают) к верхней границе области ui (правило 1).

Если область uiувеличивается в размере xiна величину Δx = Xj — xi(рис. 6.3, б), то на эту же величину увеличиваются все горизонтальные размеры всех областей внутри ui,границы которых примыкают (совпадают) к правой границе области ui.

Рис. 6.3. а — изменение конфигурации при слиянии по вертикали, б — изме­нение конфигурации при слиянии по горизонтали

Пусть для примера (рис. 6.1) при фиксированных размерах модулей (Д, В, С, D, Е, F, G, H, I) после метризации план с раз­мещенными в областях модулями имеет вид, представленный на рис. 6.4. Будем различать размеры (hi, wi)модуля miот размеров (xi, yi)области ri,в которую помещен модуль (блок) mi.

4 1

Рис. 6.4. План с размещенными блоками

Размеры областей в соответствии с последовательной сверт­кой, определяются следующим образом:

1. us = mHHm1 xs = max(wH, wι) = wι; x∏ = xi = xs = wι. ys = h∏ + hi; ун = h∏; yi = hi.

Назовем выражения, определяющие размеры полученного в результате свертки прямоугольника, расчетными. В нашем слу­чае расчетные выражения имеют вид:

При окончательном определении размеров (ho, wo) описываю­щего прямоугольника Rвозможны три ситуации.

1. Если выполняется ограничение —

т. е. размеры прямоугольника R совпадают с раз­мерами Ui.

Рис. 6.5. а — увеличение размеров по условию 2, б — увеличение размеров по условию 3

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

Как видно из примера, размеры описывающего прямоуголь­ника зависят от размеров отдельных блоков.

В полученных выражениях уменьшить общие размеры (ho, wo) можно, уменьшив в первую очередь размеры модулей, являющихся составными частями выражений, определяющих величины ho и wo.

В работе используется два подхода к уменьшению общей площади Srпрямоугольника R, Sr = ho ∙ wo.

При первом подходе размеры модулей фиксированы. Можно изменять ориентацию модулей. Для заданного дерева разрезов

отыскиваются ориентации модулей, обеспечивающие при свертке минимальные значения показателя F = Sr.

При втором подходе размеры модулей могут изменяться в со­ответствии с ограничениями (6.1)-(6.3). Для заданного дерева разрезов отыскиваются размеры модулей, соответствующих огра­ничениям (6.1)-(6.3) и обеспечивающих при свертке минималь­ное значение показателя F = Sr.

6.3.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Формирование плана методом свертки:

  1. Текст как результат взаимодействия плана выражения и плана содержания
  2. Метод формирования тремерной рабочей сцены при использовании нескольких оптико-электронных датчиков
  3. 3.1. Формирование стратегии развития системы персональных финансов
  4. Алгоритм формирования тремерной рабочей сцены при использовании нескольких оптико-электронных датчиков
  5. §1.4 Психологические особенности формирования профессионально-личностной компетентности менеджера коммерческой организации
  6. ХАЛЫН АННА ЮРЬЕВНА. ФОРМИРОВАНИЕ СИСТЕМЫ СТРАТЕГИЧЕСКОГО УЧЕТА НА ИННОВАЦИОННЫХ ПРЕДПРИЯТИЯХ. ДИССЕРТАЦИЯ на соискание ученой степени кандидата экономических наук. Ростов-на-Дону - 2014, 2014
  7. Анализ методов и устройств трехмерного технического зрения и методов калибровки
  8. 1.2.1 Вариационные методы
  9. Геометрические методы
  10. 3. Понятие и виды методов государственно-управленческой деятельности
  11. Методы вычисления параметров и сопоставления характерных точек объектов
  12. Изопериметрический метод