Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем

Информатика в техническом университете

Информатика в техническом университете




Серия основана в 2000 году




    РЕДАКЦИОННАЯ КОЛЛЕГИЯ:


                   д-р техн, наук И.Б. Федоров — главный редактор
                   д-р техн, наук А. А. Марков — зам. главного редактора
                   д-р техн, наук Ю.М. Смирнов — зам. главного редактора
                   д-р техн, наук В. Ф. Горнее
                   д-р техн, наук В. В. Девятков
                   канд. техн, наук И.П. Иванов
                   д-р техн, наук В. А. Матвеев
                   д-р техн, наук И.П. Норенков
                   д-р техн, наук В.В. Сюзев
                   д-р техн, наук Б.Г. Трусов
                   д-р техн, наук В.М. Черненький
                   д-р техн, наук В.А. Шахнов

                В.А. Овчинников





Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем

Допущено Министерством образования Российской Федерации в качестве учебника для студентов высших учебных заведений, обучающихся по направлению «Информатика и вычислительная техника», специальностям: «Вычислительные машины, комплексы, системы и сети», «Автоматизированные системы обработки информации и управления», «Программное обеспечение вычислительной техники и информационных систем»





Москва Издательство МГТУ имени Н.Э. Баумана 2001

         УДК 681.31(075.8)
         ББК 32.973-02
              035


Рецензенты:
кафедра «Информационные технологии» Московского государственного университета печати
(зав. кафедрой профессор В.М. Гасов); заслуженный деятель науки и техники РФ профессор А.Я. Савельев






              Овчинников В.А.
          035 Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: Учеб, для вузов. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 288 с., ил. (Сер. Информатика в техническом университете).

                 ISBN 5-7038-1872-9

                  Рассмотрены воцросы алгоритмизации комбинаторно-оптимизационных задач структурного синтеза на графах. Большое внимание уделено формализации таких задач и методам их решения, основанным на идее отсечения, ветвей и границ, поиска в глубину, в ширину, двоичной свертки. Описаны основные этапы построения алгоритмов и подходы к оценке их точности и сложности; точные и приближенные алгоритмы решения таких задач, как построение минимального остовного дерева, замкнутого цикла минимальной длины, кратчайшего маршрута, разрезания гиперграфа схемы и др. Выполнена оценка вычислительной и емкостной сложности большинства алгоритмов.
                  Содержание учебника соответствует курсу лекций, который автор читает в МГТУ им. Н.Э. Баумана.
                  Для студентов вузов, обучающихся по специальностям, связанным с информатикой. Будет полезна инженерам, работающим в данной области.





УДК 681.31(075.8)
ББК 32.973-02




ISBN 5-7038-1872-9

                                                      © В.А. Овчинников, 2001
                                                      © Московский государственный технический университет им. Н.Э. Баумана, 2001
                    © Издательство МГТУ им. Н.Э. Баумана, 2001

ОГЛАВЛЕНИЕ


         Введение...................................................... 8

         1. Постановка и формализация комбинаторно-оптимизационных задач....................................................... 10
           1.1. Комбинаторно-оптимизационные задачи структурного синтеза и их постановка.............................................. 10
          1.2. Этапы полного решения прикладной задачи структурного синтеза 16
          1.3. Элементы теории графов................................. 23
              Контрольные вопросы и задания .......................... 35
         2. Математические модели объектов проектирования и структуры их представления............................................. 37
          2.1. Требования к математическим моделям объектов проектирования. 37
           2.2. Представление объектов проектирования неориентированным графом и гиперграфом....................................... 40
          2.3. Представление схем ориентированным графом.............. 44
          2.4. Математические модели монтажного пространства.......... 49
          2.5. Базовые структуры данных............................. 52
          2.6. Анализ структур данных, используемых для представления графов 62
              Контрольные вопросы и задания........................... 68
         3. Методы решения комбинаторно-оптимизационных задач.......        70
          3.1. Стратегии декомпозиции множества решений и дерево поиска.... 70
          3.2. Методы поиска решения, использующие идею отсечения...        72
          3.3. Метод ветвей и границ.................................. 78
          3   .4. Метод итерационного улучшения....................... 87
          3.5. Метод параллельно-последовательной свертки............. 89
              Контрольные вопросы и задания........................... 93
         4. Построение и анализ алгоритмов............................ 94
          4.1. Точность и сложность алгоритма......................... 94
          4.2. Основные этапы построения алгоритма................... 105

5

Оглавление

         . 4.3. Описание алгоритмов операциями теории множеств, графов и математической логики................................. 117
          4.4. Методика анализа вычислительной сложности алгоритмов.. 125
          4.5. Особенности реализации операций над множествами и отношений между ними............................................... 136
             Контрольные вопросы и задания......................... 141
        5. Алгоритмы декомпозиции схем ЭВМ......................... 143
          5.1. Постановка задачи схемной компоновки................ 143
          5.2. Последовательный алгоритм разрезания гиперграфа схемы. 147
          5.3. Алгоритм параллельного разрезания гиперграфа схемы.... 157
          5.4. Итерационный алгоритм улучшения компоновки при задании схемы гиперграфом........................................ 162
          5.5. Алгоритм дихотомического разрезания гиперграфа схемы по методу ветвей и границ................................... 169
             Контрольные вопросы и задания......................... 185
        6. Задачи идентификации объектов и поиска идентичных частей.... 186
          6.1. Математическая модель задачи идентификации схем..... 186
          6.2. Исследование алгоритмических моделей решения задачи идентификации............................................ 189
          6.3. Алгоритм решеция задачи идентификации............... 195
          6.4. Математическая модель задачи покрытия схемы заданным набором модулей.......................................... 196
          6.5. Исследование алгоритмических моделей задачи изоморфного наложения................................................ 198
          6.6. Алгоритм решения задачи покрытия.................... 202
             Контрольные вопросы и задания.......................   205
        7. Алгоритмы свертки....................................... 206
          7.1. Задача свертки и ее формальная постановка........... 206
          7.2. Неуравновешенная двоичная свертка................... 208
          7.3. Уравновешенная двоичная свертка..................... 216
          7.4. Выделение минимальных массивов гиперграфа........... 223
             Контрольные вопросы и задания......................... 228
        8. Алгоритмы размещения.................................... 230
          8.1. Постановка задачи размещения........................ 230
          8.2. Последовательный алгоритм размещения................ 232
          8.3. Итерационный алгоритм размещения.................... 242
             Контрольные вопросы и задания......................... 246

6

Оглавление

        9. Алгоритмы решения задачи коммутации.................... 248
          9.1. Алгоритм Прима..................................... 248
          9.2. Алгоритм Дейкстры.................................. 251
              Контрольные вопросы и задания....................... 258
        10. Дополнительные приемы снижения вычислительной сложности алгоритмов................................................ 260
          10.1. Упорядочивание множеств........................... 260
          10.2. Представление множеств характеристическими векторами. 267
          10.3. Использование отображения множества вершин гиперграфа в само себя.............................................. 273
               Контрольные вопросы и задания...................... 274
        Приложения................................................ 275

        Список литературы.......................................   284

        Предметный указатель...................................... 286

    ВВЕДЕНИЕ


           Роль автоматизированного проектирования (АП) в решении задач науки и техники общеизвестна. Особенно велико значение АП в создании ЭВМ. Это предъявляет соответствующие требования к подготовке специалистов в области проектирования и конструирования ЭВМ.
           При проектировании ЭВМ комбинаторно-оптимизационные задачи структурного синтеза - наиболее широкого и сложного класса задач АП, решают, как правило, на всех этапах, начиная с эскизного проектирования и заканчивая разработкой конструкторской документации. В конструкторском проектировании к таким задачам относятся, например, схемная компоновка, размещение компонентов в монтажном пространстве, коммутация соединений и т.д.
           Непосредственное решение задач, т.е. формальное преобразование исходного описания объекта в результат проектирования, выполняет программа, которая реализует алгоритм. Студенты соответствующих специальностей достаточно глубоко изучают средства, системы и технологию программирования, в то время как вопросам алгоритмизации, т.е. разработки и анализа алгоритмов, не уделяется достаточного внимания.
           Для разработки алгоритма специалист должен четко и с требуемой полнотой определить содержательную постановку задачи и сформулировать ограничения и критерий оптимальности вариантов ее решения, выбрать аппарат формализации, разработать математические модели объекта и результата, получить формальную постановку задачи, выбрать метод ее решения и определить операции преобразования модели объекта в модель результата и последовательность их выполнения.
           Разработка алгоритма подразумевает также выбор структур данных, обеспечивающих эффективное преобразование модели объекта, анализ емкостной и вычислительной сложности, использование способов снижения последней. Это приобретает особенное значение в связи с тем, что многие комбинаторнооптимизационные задачи структурного синтеза относятся к классу АР-полных, время точного решения которых экспоненциально зависит от размера входа задачи.
           Поскольку математическими моделями объекта структурного синтеза являются различного рода графы (неориентированные, ориентированные,

8

Введение

         гиперграфы), в учебнике рассматриваются вопросы разработки алгоритмов преобразования графов.
           Основная цель книги - систематизировать комбинаторно-оптимизационные задачи структурного синтеза, возникающие при конструировании ЭВМ, изложить методики подготовки таких задач к решению, а также разработки и анализа алгоритмов, показать способы перехода от объекта к его модели в виде соответствующих графов, привести математические основы, методы и алгоритмы решения задач.
           В учебнике описана разработка алгоритмов решения задач декомпозиции схем ЭВМ, их идентификации и поиска идентичных частей, двоичной свертки и поиска минимальных массивов гиперграфа, размещения и коммутации, выполнен выбор структур данных и получены оценки вычислительной сложности.
           В книге использованы оригинальные результаты работ по созданию компонент САПР и курса лекций, прочитанных автором в МГТУ им. Н.Э. Баумана.
           Учебник предназначен для студентов высших учебных заведений, обучающихся по специальности «Вычислительные машины, системы, комплексы и сети» и может быть полезен студентам специальностей «Автоматизированные системы обработки информации и управления», «Программное обеспечение вычислительной техники и автоматизированных систем».
           Автор выражает глубокую благодарность к.т.н., доценту Г.С. Ивановой за помощь и советы при подготовке рукописи, а также рецензентам д.т.н., профессору А.Я. Савельеву и сотрудникам кафедры «Информационные технологии» Московского государственного университета печати за ценные замечания, позволившие улучшить содержание книги.


В.А. Овчинников

        1. ПОСТАНОВКА И ФОРМАЛИЗАЦИЯ
         КОМБИНАТОРНО-ОПТИМИЗАЦИОННЫХ ЗАДАЧ

    1.1. Комбинаторно-оптимизационные задачи структурного синтеза и их постановка

          Задачи структурного синтеза возникают при разработке практически любых объектов или систем на всех этапах, начиная с эскизного проектирования и заканчивая выпуском конструкторской документации. Особенно много таких задач при проектировании средств электронно-вычислительной техники (ЭВТ).
         Это объясняется следующими факторами:
          -  природа функционирования средств ЭВТ такова, что задачи формообразования (геометрйческого синтеза) за исключением проектирования топологии являются второстепенными;
          -  велико число элементов средств ЭВТ и допустимых принципов и способов их соединения в различные структуры, выполняющие одинаковые функции.
          Структура объекта или системы - это совокупность составляющих его элементов и связей между ними. В общем виде задача структурного синтеза заключается в-определении некоторого варианта структуры объекта. Под комбинаторной понимается такая задача, решение которой сводится к выбору варианта из конечного множества решений. Для выбора варианта необходимо иметь правило, служащее для сравнительной оценки качества вариантов -критерий оптимальности. Полученный вариант структуры характеризуется некоторым выходным параметром или их совокупностью, соответственно различают частный и обобщенный критерии оптимальности. Критерий оптимальности, представленный в виде функциональной зависимости от варьируемых параметров, называется целевой функцией.
          При использовании частного критерия оптимальности целевая функция -отдельный (определяющий) выходной параметр структуры, который является функцией ее варьируемых (внутренних) параметров. Под оптимизацией понимается процесс поиска такого варианта решения, целевая функция которого принимает экстремальное значение.

10

1.1. Комбинаторно-оптимизационные задачи структурного синтеза

            В комбинаторно-оптимизационных задачах в конечном множестве допустимых решений отыскивается такое, для которого целевая функция достигает оптимального (максимального или минимального) значения.
            Нередко вариант структуры полностью можно охарактеризовать только совокупностью выходных параметров. Таким образом, возникает задача многокритериальной оптимизации. Наилучшему качеству объекта могут соответствовать как максимальные, так и минимальные значения параметров из этой совокупности. Улучшение значения одного или нескольких параметров может привести к ухудшению значения других. Получить целевую функцию для обобщенного критерия оптимальности, т.е. интегральную функцию всех выходных параметров, удается лишь в редких случаях, так как установление взаимозависимости выходных параметров требует глубокого анализа физической сути функционирования еще не разработанной сложной системы.
            Обычно многокритериальные задачи сводят к однокритериальным, принимая в качестве целевой функции параметр, наиболее полно характеризующий проектируемый объект. Остальные параметры или их часть могут выступать в качестве ограничений (условий). Параметры, которые не были включены в ограничения, будут принимать значения, полученные при оптимизации целевой функции. Мы пришли к задаче на условный экстремум (максимум или минимум).
            Алгоритмизация решения задачи требует ее формальной постановки. В общем виде формальная постановка (математическая модель) комбинаторнооптимизационной задачи имеет вид:

           Найти          х*е X: /(x*)=opt{/’fx> / х&Х}                   (1.1)

         при ©Д, ...,ут)< 0, z=U7, а<у<Ъ., j=\ym, flx)=F(Y,Z),

         где X— вектор выходных переменных, задающий конечное множество допустимых решений - вариантов структуры;
           х - допустимое решение - один из вариантов структуры;
           х*- оптимальное решение;
           f - целевая функция задачи оптимизации;
           f(x*) - оптимальное значение целевой функции;
            Y = {у. / j = вектор управляемых переменных, конкретные значения которых определяют один из вариантов структуры объекта, значение целевой функции и показателей, включенных в ограничения;
           Z~ {zₖl ,К } - вектор неуправляемых переменных.
            Конкретизация общей формулировки для различных проектных задач структурного синтеза требует выбора целевой функции и определения состава векторов управляемых, неуправляемых и выходных переменных.
            В качестве управляемых переменных могут выступать количество элементов определенного типа в структуре объекта и их характеристики, координаты элементов, наличие или отсутствие связей, характеристики связей и т.д.


11

1. Постановка и формализация комбинаторно-оптимизационных задач

            К неуправляемым параметрам относятся такие конструкторские характеристики комплектующих элементов структуры, как размеры, масса, выделяемая мощность, интенсивность отказов (или среднее время безотказной работы и его дисперсия) и т.д.
            В приведенной постановке подразумевается, что множество допустимых решений Аладано или может быть получено. При формализации конкретных прикладных задач структурного синтеза в первую очередь необходимо решить проблему определения множествах. Отсюда ясно, что мы можем ставить в виде задач структурного синтеза и формализовано решать только те задачи проектирования, для которых возможно создание вариантов структуры по существующему описанию объекта проектирования.
            Очевидно, что в задачах структурного синтезах- это математическая модель проектируемого объекта, представляющая собой формальное описание множества вариантов структуры объекта на рассматриваемом уровне детализации. Отметим, что это множество не обязательно должно быть задано перечислением его элементов (см. § 1.2).
            Теперь можно сформулировать две основные проблемы, которые необходимо решать при формализации прикладных задач структурного синтеза:
            • получение математической модели объекта проектирования;
            •конструирование целевой функции и формирование ограничений.
            В рамках одной книги невозможно дать исчерпывающую характеристику даже комбинаторно-оптимизационным задачам проектирования средств ЭВТ. Однако очертить круг задач и указать их характерные особенности автор считает необходимым. В соответствии с преследуемыми целями многие комбинаторнооптимизационные задачи структурного синтеза можно отнести к тому или иному из следующих четырех классов:
            • позиционирования;
            • коммутации;
            • декомпозиции /композиции;
            • установления идентичности.
            Задачи позиционирования. Позиционирование или размещение в общем виде заключается в определении оптимального в смысле некоторого критерия положения элементов структуры объекта и связей между ними в монтажном пространстве некоторого другого объекта. В такой постановке задача размещения может быть сформулирована как задача целочисленного программирования, однако из-за большой размерности ее практическая реализация нецелесообразна, точнее невозможна за приемлемое для разработчиков время. В связи с этим задача условно разбивается на две: размещение элементов структуры и трассировка связей между ними. В дальнейшем под позиционированием будем понимать размещение элементов структуры.
            Для задач позиционирования общими признаками являются:
            •   задана структура размещаемого объекта, метрические параметры и топологические свойства его элементов и связей, а также монтажного пространства;

12

1.1. Комбинаторно-оптимизационные задачи структурного синтеза

            • функциональное назначение элементов, как правило, не имеет значения;
            •    метрические параметры и топологические свойства как размещаемого объекта, так и монтажного пространства оказывают существенное влияние на решение задачи;
            • разработка целевой функции является сложной проблемой.
            Цель размещения - создание наилучших условий для трассировки связей. Однако установить исчерпывающую совокупность этих условий и представить их в виде некоторой интегральной функции, имеющей численную меру, весьма сложная и пока не решенная задача. В качестве целевой функции выбирают обычно некоторый показатель, связанный с метрическими характеристиками результата, например, минимум суммарной длины связей. Другие условия переводятся в ограничения. Оценка значения целевой функции и проверка выполнения условий осложняются тем, что геометрию связей еще предстоит определить. Априорные оценки характеризуются невысокой точностью, а иногда и мало достоверны.
            Типичным примером задачи этого класса является задача размещения микросхем в монтажном пространстве одно- и многоплатного субблока.
            Отметим, что для формальной постановки задач этого класса необходима разработка математической модели как структуры размещаемого объекта - схемы соединения элементов, так и монтажного пространства.
            При проектировании средств ЭВТ схема соединения элементов представляется гиперграфом, а монтажное пространство - графом решетки (элементы схемы сопоставляются вершинам гиперграфа, установочные позиции монтажного пространства - вершинам графа решетки). Тогда задача размещения формулируется следующим образом: установить такое взаимно-однозначное соответствие вершин гиперграфа вершинам графа решетки, при котором целевая функция достигает экстремального значения. Таким образом, результатом решения задачи является граф соответствия вершин гиперграфа вершинам графа решетки.
            Коммутационные задачи. Независимо от физической природы элементов и их связей для этих задач характерно следующее:
            •    определены элементы структуры, их количество, характеристики и топологические свойства; функциональное назначение элементов, как правило, одинаково или не имеет значения для решения задачи (возможны случаи, когда заданы допустимые варианты элементов структуры);
            •   зафиксированы координаты элементов структуры на плоскости или в пространстве;
            •    заданы способы и/или правила соединения элементов, характеристики и топологические свойства линий коммутации (в ряде задач линии связи уже существуют, например сеть дорог);
            •    известен либо может быть определен из содержательной постановки задачи вид траектории;
            •    конструирование целевой функции не ставит серьезных теоретических проблем, так как задачи, как правило, однокритериальные.

13