<<
>>

Процедуры уменьшения пространства решений

Проанализируем наборы разрешенных магистралей. На осно­ве этого анализа сформулируем правила «отсечки» (ПО) и пра­вила проверки (ПП). Правила «отсечки» позволяют уменьшать набор разрешенных магистралей. Правила проверки (ПП) позво­ляют реализовать трассировку соединений в канале с заданной шириной.

Назовем множество Fk C F множеством конфликтно связных фрагментов (МКФ), если любые два фрагмента fi∈Fk находятся в горизонтальном конфликте и не могут быть помещены в одну магистраль.

Множество максимальных по мощности конфликтно связных фрагментов формируются следующим образом. Через контакты проводят вертикальные сечения канала. Все фрагмен­ты, пересекающие некоторое сечение, составляют множество конфликтно связанных фрагментов. На базе максимальных по мощности множество конфликтно связанных фрагментов можно формировать ограниченные по мощности множество конфликтно связанных фрагментов — по два, три и т. д. фрагмента.

Пусть MFk U Mi— множество магистралей, в кото-

i∖fi∈Fk

рые могут быть назначены фрагменты множество конфликтно связанных фрагментов Fk. Поставим в соответствие магистрали mj∙ ∈MFk множество фрагментов NFkj C Fk, которые могут назначаться в mj∙ .В наборе разрешенных магистралей этих фраг­ментов содержится mj∙.

Тогда рассматриваемая задача сводится к стандартной задаче о назначениях. В основу правил положен учет ограничения, заключающегося в том, что каждый фрагмент fi∈Fk может быть назначен только в одну магистраль mj∙ ∈Mi, MiC MFk. С другой стороны, в каждую магистраль mj∙ ∈MFk может быть назначен только один фрагмент fi∈NFkj.

Первое правило отсечки формулируется следующим образом:

ПО1.

ЕСЛИ (существует fi∈Fk, для которого набор разрешенных магистралей включает только одну магистраль mj∙) И (в mj

не назначен ни один из /ι, находящийся в горизонтальном конфликте с /i),

ТО (/iназначается в mj∙, а для всех фрагментов, находящихся в горизонтальном конфликте с /i, из набора разрешенных магистралей удаляется mj∙).

Если фрагмент /i, не принадлежащий Fk, находится в гори­зонтальном конфликте с каждым фрагментом, принадлежащим Fk, то будем говорить, что /iнаходится в конфликте с Fk.

Второе правило является обобщением первого. Суть его в том, что если число Fkфрагментов множества конфликтно связанных фрагментов равно числу магистралей, в которые они могут быть назначены, то эти магистрали резервируются за Fk .

ПО2.

ЕСЛИ (Fk — это множество конфликтно связанных фрагментов) И (|Fk| = |MFk|),

ТО (магистрали набора MFkрезервируются за участками Fk, а для всех фрагментов, находящихся в конфликте с Fk, из набора разрешенных магистралей удаляются магистрали, содержащиеся в MFk).

Третье правило основано на учете того обстоятельства, что существуют два множества кон­фликтно связанных фрагментов Fk и Fr,отличающихся только одним элементом, т. е. Fk∖fi= = Fr∖fj, fi = fj. При этом MFk = = MFr. На рис. 1o.7 показанорасположение фрагментов Fk = {/1, /2, /4}, Fr= {/1, /2, /3}.

Несовпадающая пара /3 и /4. Это означает, что /3 и /4 должны располагаться в одной магистрали.

ПОЗ.

ЕСЛИ (Fk и Fr— это два множества конфликтно связанных фрагментов, составы которых отличаются одним элементом, т. е. Fk∖(Fk ∩ Fr) = /i, Fk∖(Fk ∩ Fk) = /, /i = /) И (MFk = = MFr) И (|MFk| = |MFr| = |Fk| = |Fr|),

ТО (магистрали MFk= MFrрезервируются для фрагментов множества MFk ∪MFr. Причем /iи /j должны распола­гаться в одной магистрали, а для всех фрагментов, находя­щихся в горизонтальном конфликте с Fk или с Fr, из набора разрешенных магистралей удаляются магистрали, содержа­щиеся соответственно в MFk или в MFr.).

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

ПО4.

ЕСЛИ (Fk — это множество конфликтно связанных фрагментов) И (|Fk| = ∖MFk|) И (существует магистраль mi∈MFk, такая что в нее может быть назначен только один fj ∈Fk, т. е. MFki = f),

ТО (fjназначается в mi, a miудаляется из набора разрешенных магистралей всех фрагментов, находящихся в горизонталь­ном конфликте с fj).

Пятое правило распространяется на несколько магистралей.

ПО5.

ЕСЛИ (Fk — это множество конфликтно связанных фрагмен­тов) И (|Fk| = |MFk|) И (среди магистралей MFk, пред­назначенных для размещения в них фрагментов Fk, су­ществует некоторое подмножество MG C MFk, в которое могут быть помещены фрагменты подмножества FR C Fk, FR U NFi,и при этом |MG| = |FR|),

i∣m⅛∈MG

ТО (FR назначается в MG, а для всех fi∈Fk\FR, а также для всех fi, находящихся в конфликте с Fk, из набора разрешенных магистралей исключаются MG).

Отметим, что если в результате применения правил произо­шло изменение набора разрешенных магистралей некоторого fi, то необходим пересмотр набора разрешенных магистралей для всех fj, связанных с fiв граф вертикальных ограничений.

Обозначим через miniи maxiминимальный и максимальный номера магистралей в наборе разрешенных магистралей для fi. Соответственно для fj — minj∙ и maxj∙. Магистрали пронумерова­ны сверху вниз. Пусть pij — максимальный путь между xi и xj в граф вертикальных ограничений. Это значит, что fj должен быть размещен выше fi, не менее чем на pijмагистралей. Описание условий отражают следующие ограничения:

Если увеличить mini, то для выполнения ограничений необ­ходимоувеличение minj∙. Если уменьшится maxj∙, то необходимо уменьшение maxi.

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

В результате может оказаться, что трассировка при таком пробном размещении нереализуема. Следствием этого является удаление из набора разрешенных магистралей фрагмента fiпроб­ного номера магистрали.

Рассмотренные выше правила на основе анализа соотноше­ний между фрагментами и магистралями позволяют производить либо назначение отдельных фрагментов, либо сужение их набо­ра разрешенных магистралей. Эти же соотношения позволяют сделать вывод о реализуемости трассировки в заданном числе магистралей. Ниже приводится сформулированное для этих це­лей правило проверки ПП1.

ПП1.

ЕСЛИ (Fk — это множество конфликтно связанных фрагментов) И (|Fk| >|MFk |),

ТО (трассировка в заданном числе магистралей не реализуется).

Если трассировка невозможна, то необходимо увеличить ши­рину канала.

После сокращения ряда набора разрешенных магистралей ситуация изменяется и могут возникать новые множества кон­фликтно связанных фрагментов, для которых выполняются усло­вия вышеприведенных правил отсечек. Циклическая структура сужения состава набора разрешенных магистралей и отсечек решений приведена в алгоритме A2.

Алгоритм А2

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

2. В пределах каждого Fk формируются различной мощности подмножества FkiC Fk, |Fki|

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

Еще по теме Процедуры уменьшения пространства решений:

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