<<
>>

Формирование пространства решений

Пусть имеется эскиз трассировки T, который разбит на множество фрагментов F = {fi| i = 1,2, ...n} . Для полученного множества фрагментов построим граф пересечений R = (X, U), X = {xi| i = 1,2, ...n}, U = {ui| i = 1,2, ...n},где xiсоответ­ствует фрагменту fi, а две вершины xiи xj∙ связаны ребром Uk, если соответствующие им фрагменты fiи fjнаходятся в отношении конфликта, т. е. пересекаются друг с другом.

На рис. 11.11 представлен граф пересечений, построенный для эски­за трассировки, представленного на рис. 11.10.

Здесь ребра множества U показаны сплошными линиями. Рассмотрим граф R = (X, U), добавив к нему множество ребер W = {wk| к = 1,2, ...l}. Две вершины xiи xj∙ связываются реб­ром Wk, если соответствующие им фрагменты fiи fj∙ смежные на эскизе трассировки, т. е. инцидентны одному общему узлу. Если fiи fj будут в разных слоях, то в этом узле будет помещен

8 В. М. Курейчик, Б. К. Лебедев, О. Б. Лебедев

Рис. 11.11. Граф пересечений, построенный для эскиза трассировки

межслойный переход. На рис. 11.11 ребра множества Wпоказа­ны штрихпунктирными линиями. Число таких ребер равно числу узлов.

Полученный граф R = (X, U) состоит из некоторого мно­жества не связных между собой подграфов — компонент связ­ности. Каждому компоненту связности в исходном разбие­нииоднозначно соответствует некоторое множество фрагментов которое назовем конфликтно связной группой (КСГ)

i

Для графа R (см. рис. 11.10) образуются следующие кон­фликтно связанные группы:

Для каждой конфликтно связной группы Fi существует только две альтернативы Ai1и Ai2разнесения по слоям. На рис. 11.12 представлены альтернативы разнесения конфликтно связной группы участков F1 .

Каждое множество Fiраспадается на два подмножества Fi1 и Fi2, Fi1U Fi2=, Fi, где Fi1— множество фрагментов, размеща­емых в одном слое, а Fi2— в другом. Для нашего примера

Будем считать, что альтернативе Ai1соответствует размеще­ние Fi1в первом слое, a Fi2— во втором. Aльтернaтиве A2 соответствует противоположное размещение Fi1и Fi2.

Рис. 11.12. Альтернативы разнесения конфликтно связной группы участков

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

Очевидно, что конкретный набор альтернатив A = {A.

| i = = 1,2,...; k∈{1,2}} определяет конкретный вариант разнесения фрагментов по слоям и, как следствие, конкретный набор узлов, в которых помещаются межслойные переходы для реализации этого варианта разнесения фрагментов.

В связи с этим задача разнесения соединений по слоям сво­дится к поиску такого набора альтернатив A*, при котором число межслойных переходов P(A*) минимально, т. е.

На рис.11.13 представлено разнесение эскиза трас­сировки в соответствии с набором альтернатив A = = {A2, A2, A33, A;j, A∣, A∣}. При этом необходимы четыре межслойных перехода.

Следует отметить, что для некоторых конфликтно свзанных групп выбор альтернативы очевиден.

Рис. 11.13. Разнесение эскиза трассировки по слоям

Рассмотрим ситуацию А, при которой фрагменты конфликт­но связной группы Fi, смежные уже размещенным по слоям фрагментам. На рис. 11.14 размещенные фрагменты выделены жирными линиями, конфликтно связная группа Fi = (1,2,3). Выбирается та альтернатива, при которой число межслойных переходов минимально.

Рассмотрим ситуацию В, при которой часть фрагментов конфликтно связной группы Fiсвязана с уже размещенными, а часть — с еще неразмещенными (свободными) фрагментами. На рис. 11.15 фрагмент 3,принадлежащий конфликтно связной

группе Fj, еще не размещен, Fi

= (1,2).

Рис. 11.14. Эскиз трассиров­ки с размещенными участка­ми (ситуация А)

Рис. 11.15. Эскиз трассиров­ки с размещенными участка­ми (ситуация В)

Обозначим через n1число обязательных межслойных перехо­дов, возникающих в узлах, связывающих фрагменты конфликтно связной группы с уже размещенными фрагментами, при реализа­ции альтернативы Ai1, а через n2— при реализации альтернативы A2. Обозначим через miчисло узлов, связывающих фрагменты конфликтно связной группы со свободными фрагментами. Если при реализации A1число ni1≥ n2+ mi,то выбираем A2, а если при реализации A2число n2≥ n1 + mi,то выбираем A1.Другими словами, если при реализации альтернативы Ai1число обяза­тельных межслойных переходов больше или равно максимально возможному числу межслойных переходов при реализации Ai2, то выбирается Ai2, и наоборот.

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

11.4.

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

Еще по теме Формирование пространства решений:

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