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

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

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




Серия основана в 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