Содержание к диссертации
Введение
1. Выбор и обоснование методов решения оптимизационных здач конструкторского проектирования в адаптируемых САПР II
1.1. Создание адаптируемых САПР на базе формальных комбинаторных процедур II
1.2 Анализ точных методов комбинаторной оптимизации, применяемых для решения задач конструкторского проектирования 15
1.3. Общая схема решения оптимизационных задач конструкторского проектирования 31
1.4. Эвристические методы снижения вычислительной сложности комбинаторных методов 37
1.5. Выводы и рекомендации 45
2. Сокращение комбинаторного перебора при решений задач компоновки и покрытия 47
2.1. Применение метода динамического программирования для решения задач компоновки и покрытия 47
2.2. Исследование эвристик, применяемых для сокра щения области определения переменной управления 57
2.3» Реализация комбинаторного алгоритма компоновки на базе схемы последовательного анализа вариантов 70
2.4« Экспериментальное исследование комбинаторных алгоритмов компоновки и покрытия 75
2.5. Выводы и рекомендации 8І
3. Применение метода динамического программирования дли решения задачи размещения элементов эва в ортогональной решетке 84
3.1. Формальная постановка задачи и метод ее решения 84
3.2. Сокращение комбинаторного перебора в алгоритме размещения за счет изменения стратегии ветвления З?
3.3. Применение эвристического алгоритма компоновки для сокращения комбинаторного перебора в алгоритмах размещения 106
3.4. Выводы и рекомендации из
4. Применение метода ветвей и границ в комбинаторных алгоритмах трассировки проводного монтажа блоков эва 116
4.1. Формальная постановка и алгоритм решения задачи выбора оптимальной конфигурации соединений при жгутовом монтаже блоков ЭВА 116
4.2. Оптимизация конфигурации проводных соединений при монтаже методом накрутки 130
4.3. Применение эвристик для снижения трудоемкости комбинаторных алгоритмов трассировки проводных соединений 137
4.4. Выводы и рекомендации 145
Заключение 147
Список литературы
- Создание адаптируемых САПР на базе формальных комбинаторных процедур
- Эвристические методы снижения вычислительной сложности комбинаторных методов
- Применение метода динамического программирования для решения задач компоновки и покрытия
- Формальная постановка задачи и метод ее решения
Введение к работе
В материалах ХХУІ съезда КПСС "Основные направления экономического развития СССР на 1981«1985 годы и на период до 1990 года" в качестве одного из основных направлений развития науки и ускорения технического прогресса определено "расширение автоматизации проектно-конструкторских и научно-исследовательских работ с применением средств вычислительной техники". Упор на внедрение электронно-вычислительной техники обусловлен неуклонным повышением требований к качеству, возросшими объемом и сложностью выпускаемой аппаратуры, а также совершенствованием и изменением ее элементно-конструктивной базы и технологии изготовления. В соответствии с этим на первый план выдвигается проблема комплексной автоматизации процесса проектирования и изготовления электронно-вычислительной аппаратуры и, в частности, проблема автоматизации этапа конструкторского проектирования, как одного из наиболее сложных, а также связанная с ней задача разработки и совершенствования алгоритмической базы современных систем автоматизации проектирования (САПР). Большой вклад в развитие теории и практическую реализацию САПР внесли основополагающие работы: Л.Б.Абрайтиса, Р.П.Базилевича, Д.И. Батищева, В.М.Глушкова, М.А.Гаврилова, Ю.П.Зимана, А.М.Карапетяна, В.М.Курейчика, Н.Я.Матюхина, А.Н.Мелихова, С.А.Майорова, Б.Н.День-добренко, А.И.Петренко, Г.Г.Рябова, В.А.Селютина, А.Я.Тетельбаума, М.Е.Штейна, О.Н.Юрина и других, а также многих зарубежных специалистов.
При создании САПР ведущую роль играет разработка комплекса алгоритмов и программ, реализующих процесс проектирования и предназначенных для решения отдельных задач конструкторского проектирова-
ния. В связи с этим важной с математической точки зрения особенностью большинства задач конструкторского проектирования является то, что все они сводятся к моделям целочисленного программирования, имеющим чрезвычайно сложные и громоздкие решения из-за большой размерности, существенно нелинейных оптимизируемых функций и функционалов, большого числа нелинейных ограничений. Это обуславливает широкое применение в реально существующих САПР эвристических алгоритмов, которые, не являясь формально обоснованными Г1,2] , нередко приводят к неудовлетворительным результатам.
U другой стороны, большие успехи, достигнутые в последние годы в развитии теории комбинаторных вычислений, дали в руки исследователей и специалистов достаточно общие точные и приближенные методы, с успехом используемые для решения сложных экономических, научно-технических, управленческих и ряда других задач. Эти же методы при соответствующей формализации применимы и для решения задач конструкторского проектирования.
U практической точки зрения реализация комбинаторных методов заключается в выборе соответствующих моделей объектов и разработке комбинаторных алгоритмов. Для решения задач конструкторского проектирования наиболее известными и хорошо разработанными комбинаторными моделями являются графы. Они позволяют сохранить содержательное представление о реальной схеме устройства, обладают наглядностью и простотой восприятия, однако графы применимы лишь в тех случаях, когда на множестве элементов схемы задается бинарное отношение. Это приводит к тому, что для ряда задач конструкторского проектирования (например, для задач компоновки, размещения, покрытия, распределения инвариантных контактов при трассировке и других) графовые модели недостаточно полно отражают все свойства схем.
Более предпочтительны для представления электронных схем гиперграфы. Они являются адекватной моделью объектов, элементы которых связаны совокупностями различных многоарных отношений. Это позволяет точно определять все основные конструктивные параметры устройства, взаимно-однозначно и достаточно компактно описывать объекты проектирования, а также получать формальные комбинаторные алгоритмы, легко поддающиеся программированию.
Теория гиперграфов развита в работах К.Бержа и А.А.Зыкова, а наиболее существенные результаты по применению гиперграфов в автоматизации конструкторского проектирования содержатся в работах: А.М.Бершадского, Л.С.Берштейна, В.М.Курейчика, А.Н.Мелихова, А.И. Петренко, А.Я.Тетельбаума.
Комбинаторные алгоритмы на графах и гиперграфах обладают рядом достоинств, основным из которых является простота вычислительных процедур, сводящихся, как правило, к логическим операциям и получению оценок. В то же время недостаток алгоритмов - огромный комбинаторный перебор, возникающий при решении задач, приводит к чрезвычайно высокой сложности их реализации. Поэтому важным направлением исследований следует считать разработку методов снижения перебора, опирающихся на особенности вычислительных схем самих комбинаторных методов, а также на специфику решаемых задач. Существенные результаты в этом направлении получены: В,А.Емеличевым, А.А. Корбутом, В.С.Михалевичем, Ю.Ю.Финкельштейном, А.Ахо, Р.Беллманом, Г.Вагнером, Х.Мюллер-Мербахом, Э.Рейнгольдом, Дж.Хопкрофтом, Дж. Ульманом. Применительно к задачам конструкторского проектирования идеи снижения трудоемкости комбинаторных алгоритмов содержатся в работах: Г.А.Акрамовского, Л.С.Берштейна, В.М.Курейчика, Б.К.Лебедева, К.К.Морозова, А,В.Петросяна, В.А.Селютина, М.Е-Штейна, П, Джилмора, Т.Оцуки и других ученых.
Целью настоящей работы является исследование формальных постановок и комбинаторных методов решения задач конструкторского проектирования (динамического программирования, последовательного анализа вариантов, метода ветвей и границ), разработка на базе этих методов комбинаторных алгоритмов сокращенного перебора, а также реализация разработанных алгоритмов в системах автоматизации проектирования.
В соответствии с этой целью в диссертации отражены следующие вопросы:
исследована общая схема, включающая известные комбинаторные методы, применяемые для решения оптимизационных задач дискретного программирования, на базе которой разработаны формальные приемы снижения трудоемкости комбинаторных алгоритмов путем включения в . вычислительные схемы точных методов эвристических алгоритмов}
разработаны точные и приближенные комбинаторные алгоритмы для решения задач компоновки, покрытия, размещения и трассировки проводных соединений, основанные на известных вычислительных схемах методов динамического программирования, ветвей и границ и последовательного анализа вариантов и использующие в качестве эвристик известные и оригинальные эвристические алгоритмы, а также формальные приемы сокращения перебора;
разработан комплекс программ для приближенного решения конструкторских задач реальной размерности в условиях ограниченного объема памяти и времени, используемый в системах автоматизации конструкторского проектирования на ЕС ЭВМ; проведено исследование и сопоставление разработанных программ с известными.
Настоящая работа выполнялась в рамках госбюджетной и хоздоговорной тематики в соответствии с планами работы секций радиоэлектрони-
ки и приборостроения Программ САПР Минвуза РСФСР и Минвуза СССР, а также планами работы Рязанского радиотехнического института и специальными постановлениями.
Практическая ценность работы заключается в том, что разработанные на базе вычислительных схем точных методов приближенные комбинаторные алгоритмы позволяют получать решения, точность которых определяется только имеющимися ресурсами ЭВМ (временем и оперативной памятью) и не зависит от конкретных особенностей проектируемого устройства. Это приводит к существенному повышению качества проектирования.
Разработанные алгоритмы реализованы в виде программ для ЕС ЭВМ и включены в системы автоматизации конструкторского проектирования, эксплуатируемые на предприятиях п/я М-5783, п/я А-3756 и КБМ г.Коломна. На базе предложенных методов решения задач конструкторского проектирования ЭВА поставлен цикл лабораторных работ по курсу "Автоматизация конструирования", а теоретические достижения используются при чтении лекций по тому же курсу на кафедре Конструирования электронно-вычислительной аппаратуры Рязанского радиотехнического института.
Основные результаты работы докладывались и обсуждались на 15 конференциях и семинарах в г.г. Пензе, Каунасе, Ереване, Запорожье, Славском, Владимире, а также на профессорско-преподавательских конференциях РРТИ.
Результаты исследований изложены в четырех разделах, заключении и приложениях.
Первый раздел посвящен разработке эвристических методов сокращения комбинаторного перебора в алгоритмах решения задач конструкторского проектирования. С этой целью дан обзор известных методов
комбинаторной оптимизации, применяемых для решения исследуемых задач, а также разработана общая схема, на базе которой определены формальные приемы снижения комбинаторного перебора путем включения в схемы точных методов эвристических алгоритмов. Рассмотрены принципы организации адаптируемой САПР, использующей формальные комбинаторные процедуры для динамического синтеза компонентов программного обеспечения»
Во втором разделе разработаны приближенные комбинаторные алгоритмы решения известных задач компоновки и покрытия, основанные на идеях метода динамического программирования и использующие предлагаемые эвристические приемы сокращения комбинаторного перебора. Для задачи компоновки разработаны точный алгоритм, основанный на схеме метода последовательного анализа вариантов, а также приближенный, используемый в качестве эвристики для снижения перебора. Аналитически решена задача определения минимального набора модулей, требуемого для покрытия функционально-логической схемы ЭВА. Приведены результаты экспериментального исследования и оценки трудоемкости разработанных алгоритмов.
В третьем разделе дана формальная постановка и алгоритм решения задачи размещения элементов схемы ЭВА в ортогональной решетке, основанный на идеях метода динамического программирования. Для этой же задачи показана возможность снижения комбинаторного перебора за счет изменения стратегии ветвления, а также за счет сокращения области допустимых решений с помощью алгоритма компоновки цепей. Приведены алгоритмы, оценки их трудоемкости и результаты экспериментальных исследований.
Четвертый раздел посвящен решению задач трассировки проводных
соединений, в нем приведены разработанные формальные постановки и методы решения, основанные на схеме метода ветвей и границ, задачи определения оптимальной конфигурации жгутовых соединений однорядных блоков ЭБА и задачи укладки проводов при монтаже методом накрутки. Указаны способы сокращения комбинаторного перебора путем включения в схему решения эвристического алгоритма последовательной укладки проводов, а также за счет применения предложенных в первом разделе приемов, опирающихся на специфику задач,
В приложении приведены копии актов внедрения, вывод рекуррентной формулы для определения минимального набора не связанных интегральных модулей, требуемого для покрытия электронной схемы, а также листинги программ разработанных алгоритмов.
-li-
Создание адаптируемых САПР на базе формальных комбинаторных процедур
В настоящее время большинство существующих САПР ориентируется на конструкторскую и технологическую базу проектируемого изделия. Жесткая привязка к заложенным в них алгоритмическим решениям, связанная, как правило, с широким применением эвристических алгоритмов, требует существенных затрат на перестройку САПР при переходе к проектированию другого класса устройств и смене технологии. При этом обычно приходится создавать новые комплексы алгоритмов и программ, хотя сроки их разработки, как правило, оказываются значительно больше времени изготовления новых образцов изделий.
Одним из возможных способов адаптации находящихся в эксплуатации САПР является наращивание их функциональной мощности путем создания пакетов прикладных программ, ориентированных на те или иные конструктивы. Этим путем пошли, например, разработчики отраслевых САПР, таких, как РАПИРА и ЕСАП. Пакеты прикладных программ этих систем имеют свои мониторы, которые настроены на общую информационную базу и подчинены главному монитору САПР. Включение новых программ и подсистем заключается в определенной перестройке организационного обеспечения САПР и согласовании информационного обеспечения. Такие системы обладают достаточно высокой живучестью, хотя подобные изменения приводят зачастую к необоснованному расширению программного обеспечения и дублированию программ и методов проектирования.
Другой подход, интенсивно развивающийся в последние годы, заключается в разработке адаптируемых САПР, использующих нисходящую технологию проектирования на базе типовых алгоритмических решений [4,5] . Подобные САПР включают набор универсальных математических процедур, каждая из которых выполняет одну, вполне определенную и, как правило, оптимизационную функцию, а также имеет один вход и один выход. Вызывая эти процедуры в определенном порядке, в принципе, можно реализовать произвольные, достаточно сложные алгоритмы, ориентируя их на требуемые конструктивы и технологию. Однако этот подход наталкивается на существенные трудности, связанные как с проблемой полноты подобных наборов, так и с вопросом внутренней адаптации САПР, т.е. решением задач синтеза алгоритмов и динамического выбора алгоритмических решений в процессе проектирования.
Эти трудности можно преодолеть, представляя процесс проектирования в виде последовательного решения ряда задач, каждая из которых имеет однотипный алгоритм решения. Подобное представление оказывается возможным для оптимизационных задач конструкторского проектирования (компоновка, покрытие, размещение, трассировка). Действительно, все эти задачи - комбинаторные с конечным множеством допустимых решений} процесс поиска решения для них можно представить в виде упорядоченного перебора вариантов, а в качестве математической модели для всех задач использовать гиперграфы. Кроме того, схемы комбинаторных решений имеют достаточно общий вид, а количество их - ограничено [1,2,3,6,7 и др,] Это означает, что имея вполне определенный набор базовых комбинаторных процедур, реализующих различные стратегии перебора вариантов по принципу разделения и сравнения подмножеств решений, можно, во обще говоря, осуществить синтез необходимых алгоритмов путем включения в соответствующие процедуры отдельных модулей, реализующих требуемые критерии оптимизации и ограничения.
Структура подобной САПР изображена на рис»1.1. Отличие ее от системы автоматизации проектирования, реализованной "традиционными" способами, заключается в том, что соответствующие компоненты программного обеспечения при изменении конструктива заменяются новыми, сформированными подсистемой синтеза алгоритмов, причем, организация процесса синтеза основана на таких же принципах, что и в адаптируемых САПР [5 ]
Подсистема синтеза алгоритмов состоит из транслятора входного задания, который формирует на базе задаваемых критериев оптимизации и ограничений задачи стандартные модули, и библиотек базовых комбинаторных процедур и эвристик, также оформленных в виде отдельных подпрограмм. Библиотека эвристик содержит набор базовых эвристических процедур, которые при необходимости включаются в комбинаторные схемы решений для уменьшения перебора вариантов Управление процессом синтеза алгоритмов осуществляется управляющей программой - монитором, в функции которой входит также поддержка библиотек подсистемы и коррекция библиотеки компонентов программного обеспечения САПР.
Эвристические методы снижения вычислительной сложности комбинаторных методов
В настоящее время общепринятым приемом снижения сложности общей задачи конструкторского проектирования является декомпозиция ее на более простые задачи, такие, как компоновка, покрытие, размещение и трассировка. В рамках каждой из перечисленных задач можно указать аналогичные примеры более мелкого деления. Однако, снижая такш»! образом трудоемкость общей задачи, естественным образом оказывается утерянной органическая взаимосвязь между отдельными задачами. Это обусловлено как оптимизацией различных, порой противоречивых критериев, так и невозможностью учета ограничений последующих задач в рамках решаемой. Поэтому вполне очевидным выступает факт невозможности строгой формализации отдельных задач конструкторского проектирования и, естественно, получение для них оптимальные в смысле критерия общей задачи решений.
Учитывая приведенное замечание, необходимо, по-видимому, с целью снижения трудоемкости вычислений в каждом конкретном случае стремиться к компромиссу между точностью получаемого решения оптимизационной задачи, с одной стороны, и затрачиваемыми ресурсами ЭВМ (временем и памятью) - с другой, получая тем самым приближенные результаты, которые "в большинстве случаев достаточны, т.е. достаточно хорошо удовлетворяют запросы практики" [87] .
Анализ известных приемов снижения вычислительной сложности комбинаторных методов показывает, что наиболее простым и эффективным приемом, идущим от классической вычислительной математики, является - оптимизация [1,34,37 и др.] . При использовании этого приема обычно задают верхнюю (нижнюю) границу относительного отклонения от оптимума (f) р 0 i(-f) , и процесс поиска решения прекращают, когда для задач максимизации целевой функции,
К сожалению, такой прием далеко не всегда применим для практического решения задач конструкторского проектирования. Это обусловлено, во-первых, тем, что трудоемкость - оптимизации все не оказывается значительной. Во-вторых, возможность применения -оптимизации существенно ограничена особенностями реализации отдельных комбинаторных методов и среди рассматриваемых применима только к методам типа ветвей и границ.
С другой стороны, в настоящее время в дискретном программировании мощное направление получило развитие приближенных подходов "внутри" самих точных методов. Наиболее "приспособленной" для этого оказалась схема метода ветвей и границ [2,18,88,89,90,91,92 и др.J . Она легко позволяет оценить (приблизительно) качество любого полученного допустимого решения} процесс улучшения решения легко согласовать с имеющимися ресурсами ЭВМ} в реализацию схемы метода не сложно включить эффективные эвристические правила выбора переменной для ветвления, получения рекордов и т.д. [93] Включение в вычислительную схему точного метода различных правил и алгоритмов (так называемых эвристик) преследует, цель, с одной стороны, усилить сами эвристические решения, а с другой - сократить до допустимых пределов возникающий при решении задач комбинаторный перебор. При этом проблема конструирования эвристик и способ их включения в большой степени зависят от специфики самих задач и искусства программиста. Некоторые аспекты этой проблемы, заключающиеся в выборе подходящей окрестности для поиска допустимых решений отдельных задач, рассмотрены в работах f87,943 Особо следует отметить статью Мюллер-Мербаха Г95] , в которой глубоко исследован инженерный подход к проблеме создания приближенных алгоритмов, приведена классификация оптимизационных задач и дана методология синтеза эвристик для различных классов задач. Фундаментальный обзор и классификация эвристик приведены в работе того же автора Г96] , а применительно к задачам автоматизации проектирования - в работе [97]
Исходя из общей схемы комбинаторных методов, рассмотрим возможные пути создания приближенных алгоритмов решения оптимизационных задач конструкторского проектирования, направленные на дальнейшее сокращение комбинаторного перебора.
Применение метода динамического программирования для решения задач компоновки и покрытия
Большинство известных комбинаторных алгоритмов, используемых в системах автоматизации проектирования для решения задач компоновки и покрытия, используют вычислительную схему метода ветвей и границ [8,18,22,24,45,47,49,51,69,74,100 и др. ] . Однако их эффективность, как правило, оказывается невысокой из-за того, что в силу специфики этих задач достаточно сложно найти подходящую оценку для учета нелинейности контактных ограничений. Указанный недостаток можно устранить, применяя вычислительную схему, основанную на идеях метода динамического программирования.
Воспользуемся приведенной выше математической постановкой задачи компоновки, учитывающей модульные и контактные ограничения формируемых блоков (I.2I) - (1.25), и применим для практической реализации комбинаторного алгоритма [12] предлагаемые методы снижения трудоемкости. Для этого обозначим через Еs{&f,P2- " , yi множество всех элементов схемы, а через fe /я,/я-/,, . f) -подмножество элементов, отвечающих состоянию , и рассмотрим рекуррентное соотношение (1.26), соответствующее вычислительной схеме метода.
Учитывая аддитивность оптимизируемого критерия (І.2І), мощность множества (/ на очередном t -м шаге алгоритма можно оценить следующим выражением [12] :
Выше было отмечено, что множество (/ содержит все возможные допустимые комбинации элементов схемы из множества \ Є В то же время разбиение схемы на малосвязанные блоки приводит, как правило, к формированию только сильносвязанных подсхем ГЮІ] Это означает, что на этапе выбора очередного управления X можно рассматривать лишь некоторые наборы связанных элементов, со-ставляющих множество V I/ , т.е. ограничивая тем самым число образуемых подзадач (число дочерних вершин дерева ветвления). Практически, учитывая аддитивность критерия оптимизации (I.2I), достаточно выделить с помощью одного из эвристических алгоритмов компоновки множество связанных элементов и на его базе сформировать множество допустимых блоков V (управлений Х }% каждое из которых содержит "ядро" # S (fiiwffl? J $), сильносвязанных элементов и некоторые элементы из множества S \Q, либо слабо связанные с "ядром", либо имеющие связи с элементами, не включенными в множество S Рекуррентное соотношение (1.2б) при таком подходе примет вид: а количество образуемых подзадач определится выражением; что значительно ниже оценки (2.1).
Отметим, что трудоемкость вычислений при таком подходе будет существенно зависеть от объема выделяемой подсхемы «S и величины "ядра" Q . С другой стороны, при ограниченных ресурсах ЭВМ необходимо стремиться к уменьшению разностей CasfffS )- & и
СвРС/fS ) - fastf (Q J В этом случае результат решения задачи в значительной степени будет зависеть от качества алгоритма, применяемого для формирования области определения переменной управления V 9 т.е. от качества выделения подсхемы S
Вычислительная сложность алгоритма, использующего выделение таким способом подсхем S , содержащих "хорошее" решение, все же остается высокой (1.35). Поэтому с целью дальнейшего снижения комбинаторного перебора предлагается ограничивать множество задач допустимой для конкретной ЭВМ величиной списка Р , оставляя в списке лишь задачи с лучшими оценками.
Недостатком рассмотренного алгоритма является то, что отсутствие допустимого решения при заданном числе блоков разбиения приводит к необходимости повторного разбиения схемы на /п+f, л?+2,,., и т.д. блоков, что связано с введением Sf 2&t,., и т.д. дополнительных переменных. Этот недостаток можно устранить, применяя предлагаемый в разд.2.3 комбинаторный алгоритм, основанный на схеме последовательного анализа вариантов.
Для решения задачи покрытия схем ЭВА набором не связанных интегральных модулей также может быть применена похожая схема вычислений. Однако при ее реализации необходимо учитывать ограничения на состав логических элементов (ЛЭ), включаемых в формируемую микросхему. Дадим возможную математическую постановку задачи.
Воспользуемся в качестве формальной модели функционально-логической схемы (ФЛС) моделью гиперграфа &Щі/) , в котором множество вершин l/-{l/f9/t, .,.,} соответствует множеству логических элементов схемы, а множество ребер 1/= {z?t, ,..., 2J -множеству электрических цепей. Обозначим через О- It?,... М) множество индексов ЛЭ, составляющих ФЛС.
Формальная постановка задачи и метод ее решения
В последнее время широкое применение в САПР при решении задач размещения находят топологические критерии оптимизации [9,22,64, 71 и др.] , позволяющие учитывать взаимное расположение не только элементов, но и соединений между ними. Такой подход весьма перспективен при переходе от метрических преобразований схемы, обусловленных отображением множества элементов в множество позиций коммутационного поля, к топологическим, связанным с определением топологии каждого конкретного соединения различными алгоритмами трассировки, С точки зрения уменьшения вычислительной сложности реализующих алгоритмов наиболее приемлемой топологической характеристикой для оценки полученного размещения является суммарное количество линейных интервалов цепей, которое, по мнению авторов [24,71,107] , приводит к более равномерной загрузке магистралей коммутационного поля.
Представим модель коммутационного поля в виде прямоугольной решетки размером л т , где /7 - число посадочных мест в вертикальном ряду, а т - количество таких рядов (рисЗ.і), и, учитывая последнее замечание, рассмотрим следующий функционал: Р« I ,-frfaJ -Ai-ftfibJ -/Tg fbfaj] . (3.1)
Здесь P/fZ/,) - суммарное число цепей, выходящих из / -го вертикального ряда (пересекающих / -е вертикальное сечение); fife ) и f3fz») - соответственно число вертикальных и горизонтальных линейных интервалов цепей} /f? ( / 1,2,3) - весовые коэффициенты, учитывающие важность функций в зависимости от метрико-топологических требований трассировки и соотношения числа горизонтальных и вертикальных магистралей.
Отметим, что минимизация функционала (ЗЛ) при решении задачи размещения приводит, с одной стороны, к увеличению количества линейных интервалов цепей, что в свою очередь, влечет упрощение их конфигурации, а с другой - ослабляет загрузку горизонтальных каналов коммутационного поля, создающих наибольшие трудности при трассировке некоторых типов печатных плат. В то же время минимизация (З.і) косвенно влияет на уменьшение суммарной длины связывающих соединений (в ортогональной метрике), что немаловажно для реализации высокочастотных узлов.
Для определения выражений, позволяющих вычислить значения функций, составляющих функционал (3.1), представим модель электрической схемы в виде гиперграфа, заданного матрицей инциденций С - /І С#І II fxfl , где - число цепей, а N (Л/ л /п) - число элементов схемы. Введем нулевой столбец матрицы О , который будет определять цепи схемыу выходящие на разъем, и нулевой ряд коммутационного поля, определяющий его разъем с числом контактов /f , равным числу внешних выводов схемы:
Обозначим через Є и V пропускную способность сечений между рядами посадочных мест коммутационного поля, равную соответственно числу магистралей 6 для горизонтальных и V - для вертикальных сечений. Обозначим через Z,,., множество элементов, размещенных в / -I /j рядах коммутационного поля; Z„ - Лґ -Й набор элементов, помещав мый в -" й ряд и характеризующийся матрицами состава /„ и матрицами перестановок Y? 5 / Ъ»№), W - соответственно функции, характеризующие число цепей в / -м сечении и число вертикальных и горизонтальных интервалов цепей, добавляемых к общему числу интервалов при условии, что в / -й ряд назначается набор элементов Z„ , а в /« -I рядах помещены элементы из множества ./ . Оценку качества при размещении /ґ-го набора в -й ряд обозначим через
