Содержание к диссертации
Введение
1. Определение объекта исследования и постановка задачи 12
1.1. Анализ задачи разрезания и выбор математических моделей 12
1.2. Формальная постановка задачи разрезания 16
1.3. Задача выбора структур данных для реализации алгоритмов декомпозиции схем 17
1.4. Анализ методов решения задачи разрезания 19
Выводы 23
2. Проблема выбора структур данных 25
2.1. Анализ структур данных и операций над ними 25
2.2. Исследование операций над линейными структурами данных 35
2.3. Исследование операций над древовидными и сетевыми структурами .45
2.4. Классификация базовых структур данных и матрица сложностей базовых операций 60
2.5. Формальная постановка и методика решения задачи выбора структур данных 64
2.6. Локально-оптимальный алгоритм выбора структур данных 73
2.7. Выбор структур данных для последовательного алгоритма разрезания гиперграфа 77
Выводы 86
3. Алгоритмы декомпозиции схем по методу двоичной свертки 88
3.1. Математическая модель процесса композиции и особенности алгоритмов свертки 88
3.2. Алгоритмы свертки без учета связности 92
3.3. Алгоритмы свертки с учетом связности 97
3.4. Сравнительный анализ полученных результатов 101
3.5. Выбор структур данных 103
Выводы 112
4. Алгоритм дихотомического разрезания гиперграфа по методу ветвей и границ 114
4.1. Математическая модель процесса дихотомического разрезания гиперграфа по методу ветвей и границ 114
4.2. Доказательство применимости метода ветвей и границ для декомпозиции схем 117
4.3. Схемы реализации метода ветвей и границ 121
4.4. Способы формирования дерева решений 125
4.5. Способы кодирования вершин дерева решений и оценка сверху их емкостной сложности 128
4.6. Кодирование огибающей цепи 132
4.7. Алгоритм дихотомического разрезания гиперграфа по методу ветвей и границ 137
4.8. Выбор структур данных и определение вычислительной сложности
алгоритма 141
Выводы 151
5. Экспериментальная часть 153
5.1. Система автоматизированной декомпозиции схем 153
5.2. Экспериментальное исследование вычислительной сложности алгоритмов двоичной свертки... 154
5.3. Исследование возможности применения алгоритма дихотомического разрезания гиперграфа по методу ветвей и границ и двоичной свертки для декомпозиции схем 157
5.4. Экспериментальные исследования качественных характеристик алгоритмов 160
Выводы 163
Заключение 165
Список литературы
- Задача выбора структур данных для реализации алгоритмов декомпозиции схем
- Исследование операций над древовидными и сетевыми структурами
- Алгоритмы свертки без учета связности
- Схемы реализации метода ветвей и границ
Введение к работе
Актуальность. Автоматизированное проектирование (АП) широко применяется при создании ЭВМ. Качество результатов конструкторского проектирования ЭВМ, т.е. технический уровень готового изделия в большой степени зависит от степени использования и возможностей систем АП. На всех этапах, начиная с эскизного проектирования и кончая выпуском конструкторской документации, решаются задачи структурного синтеза комбинаторно-оптимизационного характера. Многие из этих задач относятся к классу NP-полных [3,10,16,17,19,20,22,24,39]. В связи с этим, актуальным является разработка высокопроизводительных алгоритмов их решения, сравнение эффективности которых возможно на основании оценок вычислительных и емкостных сложностей, а также качества результатов проектирования.
Задача декомпозиции схем возникает при схемно-топологическом проектировании в процессе определения метрических параметров размещения элементов схем на типовых конструкциях и топологии линий связи, определяемых в ходе компоновки, размещения и трассировки. В большинстве случаев компоновка сводится к декомпозиции (разрезанию) схем на подсхемы с заранее заданным или неизвестным количеством элементов в них.
Актуальность задачи декомпозиции схем неизменно возростает при росте степени интерграции элементной базы. Разрезание, в частности, успешно применяется при проектировании полузаказных СБИС на базовых матричных кристаллах (БМК), для которых определяется состав макроэлементов. Это позволяет достигнуть лучших результатов и перейти к решению задач меньшей размерности: глобальному размещению макроэлементов в макрообластях, локальному размещению, глобальной и локальной трассировке.
Компоновка также применяется при создании высокопроизводительных ЭВМ, требующих применения большого числа процессорных элементов. Примером может служить самый мощный в настоящий момент суперкомпьютер "Симулятор Земли" производительностью 40 триллионов операций в секунду, скомпонованный в 470 шкафах. При этом выигрыш в производительности по сравнению с другими суперЭВМ достигнут благодаря более эффективной конструкции (количество микропроцессоров - 5120, что значительно меньше, чем у конкурирующих суперЭВМ).
Декомпозиция схем находит также широкое применение при размещении элементов ЭВМ на печатных платах. Например, дихотомическое разрезание схем по критерию минимальной связности позволяет получить вариант размещения, обеспечивающий прокладку минимального количества трасс через критическое сечение платы.
Приведенные примеры говорят о высокой актуальности темы данной диссертации.
Вместе с этим можно отметить, что многие методы комбинаторной оптимизации не исследованы применительно к проблеме компоновки схем или исследованы недостаточно подробно. В частности, существующие алгоритмы декомпозиции схем реализуют лишь приближенные методы комбинаторной оптимизации и, как правило, не обеспечивают высокое качество решения для разрезания широкого круга схем или же обладают большой вычислительной сложностью. Таким образом, существует потребность в разработке алгоритмов, реализующих точные методы, а также в модификации и сравнении существующих приближенных методов с целью снижения их вычислительной сложности и повышения качества результатов декомпозиции.
Очевидно, что разработка эффективных алгоритмов невозможна без исследования вариантов его конечной реализации, т.е. выбора структур данных. Вычислительная сложность вариантов алгоритма при использовании различных структур может различаться на несколько порядков. Данная задача, т.е. оптимизация выбора структур данных, является самостоятельной научной проблемой, актуальной для многих научно-технических направлений. Пути ее формализации частично рассматривается в многочисленных работах [1,2,5,8,9,10,37,42], однако ее четкой формальной постановки до сих пор не получено. Это во многом связано с разнообразием стоящих перед исследователями задач. В данной работе предпринята попытка формальной постановки задачи выбора структур данных для указанного класса комбинаторно-оптимизационных задач структурного синтеза, предложены методы ее решения, которые успешно воплощены для разработанных и исследованных алгоритмов декомпозиции схем соединения элементов ЭВМ.
Таким образом, актуальными являются разработка высокопроизводительных реализаций как эвристических так и точных методов, применимых для декомпозиции схем, а также формальная постановка и исследование методов решения задачи выбора структур данных для указанного класса комбинаторно-оптимизационных задач структурного синтеза.
Цель работы. Целью данной диссертационной работы являются разработка новых моделей автоматизированной декомпозиции схем ЭВМ и создание высокопроизводительных алгоритмов их реализации, обеспечивающих высокое качество решения, а также расширение области применения существующих алгоритмов.
Задачи исследований. Для достижения поставленных целей потребовалось:
1.Выявить перспективные методы решения задачи разрезания схем.
2.Разработать математические модели процессов разрезания схем выбранными методами.
3.Исследовать способы снижения вычислительной и емкостной сложности реализаций выбранных методов.
4.Разработать аналитические средства оценки алгоритмов декомпозиции схем различной степени интеграции.
5.Создать алгоритмы декомпозиции и экспериментально исследовать области их применения.
Методы исследований. При решении задач данной диссертационной работы были использованы: методы теории графов, методы решения задач комбинаторной оптимизации (метод ветвей и границ, поиска в глубину, двоичной свертки); методы комбинаторного анализа, математического анализа.
Научная новизна работы.
Разработаны математические модели процесса декомпозиции по методам двоичной свертки и ветвей и границ, позволившие создать высокопроизводительные алгоритмы их реализации.
В результате анализа алгоритмов решения широкого класса комбинаторно-оптимизационных задач была выявлена совокупность операций преобразования исходной модели в модель результата и получена матрица сложности их реализаций для различных структур данных.
Получена в матричной форме формальная постановка задачи выбора структур данных для оптимизации комбинаторных алгоритмов по критерию минимума их вычислительной сложности, что дало возможность создать методику выбора структур данных.
Методика выбора структур данных применена для последовательного алгоритма разрезания гиперграфа. Выбранные структуры позволили получить реализацию алгоритма, обладающую линейной вычислительной сложностью.
Исследование вариантов реализации метода двоичной свертки для решения задачи разрезания гиперграфа и проведенный выбор структур данных позволили существенно сократить вычислительную сложность алгоритма.
Разработана модификация метода ветвей и границ для решения задачи разрезания гиперграфа, выбраны структуры данных, обеспечивающие минимальную вычислительную сложность построения одной вершины дерева решений. Определены точные размеры дерева решений.
Практическая ценность работы. По результатам проведенных исследований создана исследовательская система, которая включает рабочие модули, реализующие алгоритм двоичной свертки, последовательный алгоритм разрезания и алгоритм разрезания гиперграфа по методу ветвей и границ. Получены оценки сверху времени их работы. Данная система позволила исследовать характеристики качества результатов декомпозиции для реализованных алгоритмов.
Апробация работы. Основные положения диссертационной работы обсуждены на Межвузовской юбилейной научно-технической конференции "Современные информационные технологии" (г. Москва 2001), Межвузовской научно-технической конференции "Современные информационные технологии" (г. Москва 2002).
Реализация и внедрения. Теоретические и практические результаты работы, полученные автором, нашли применение при разработке архитектуры и организации цифровой вычислительной системы для обработки сигналов и управления бортовым фурье-спектромётром высокого разрешения, выполняемой в рамках проекта ОКР «Метеор-М-ИКФС-2-МГТУ» и при анализе предприятия ОАО "АВТОТОР ХОЛДИНГ". Документы, подтверждающие внедрение, приведены в приложении.
Публикации. По результатам диссертационной работы автором опубликовано 4 работы.
Объем и структура диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложения, занимающих 176 страниц текста, в том числе 51 рисунок и 20 таблиц, список литературы из 63 наименований на 7 страницах, приложение на 2-х листах.
Содержание работы.
Во введении обоснована актуальность темы диссертации, сформулированы основные задачи и научные результаты, дано краткое содержание глав.
В первой главе описана проблемная область и определены объекты исследования: проанализированы задачи разрезания и выбраны математические модели исходного опг' а . ч схемы, получена формальная постановка задачи разрезания, показана важность решения задачи выбора структур данных для реализации комбинаторно-оптимизационных алгоритмов, проанализированы методы решения задачи разрезания.
Во второй главе рассматривается проблема выбора структур данных. Проанализированы различные структуры данных, обобщены методы их использования, оценены вычислительные сложности базовых операций для каждой из структур, получена матрица сложностей операций. Создана многокритериальная классификация базовых структур данных. Разработана математическая модель задачи выбора структур данных, создана методика выбора структур данных. На примере последовательного алгоритма разрезания гиперграфа показана эффективность ее применения - получена реализация метода, обладающая линейной вычислительной сложностью.
В третьей главе исследованы алгоритмы декомпозиции схем по методу двоичной свертки. Рассмотрены различные варианты алгоритмов свертки -уравновешенная и неуравновешенная свертка с предварительным учетом связности и без него. Исследованы и сравнены их вычислительных сложности для простейших реализаций без предварительного выбора структур данных. Выбраны структуры данных, обеспечивающие вычислительную сложность алгоритмов 0(nR+1) для худшего случая с учетом изменения характеристик модели в соответствиис законом Рента (где R - показатель Рента).
В четвертой главе исследована реализация метода ветвей и границ для дихотомического разрезания. Разработана математическая модель процесса дихотомического разрезания гиперграфа для метода ветвей и границ, доказана применимость метода ветвей и границ для декомпозиции схем. Рассмотрены различные схемы реализации метода ветвей и границ - аспекты отсечения ветвей и выбор вершин ветвления, способы формирования дерева решений. Получены оценки сверху объема памяти, требуемой для хранения дерева решений при различных способах кодирования его вершин. Выбраны структуры данных, создана конечная реализация метода ветвей и границ для дихотомического разрезания гиперграфа. Определены точные размеры дерева решений и получена оценка сверху вычислительной сложности алгоритма.
В пятой главе проведены экспериментальные исследования вычислительной сложности алгоритмов двоичной свертки, исследованы возможности применения алгоритма дихотомического разрезания гиперграфа по методу ветвей и границ для декомпозиции схем, проведено экспериментальное сравнение различных стратегий формирования дерева решений для данного метода. Экспериментально исследованы качественные характеристики последовательного алгоритма, алгоритма по методу двоичной свертки и проведено сравнение их с оптимальным решение, полученным алгоритмом по методу ветвей и границ.
Задача выбора структур данных для реализации алгоритмов декомпозиции схем
Комбинаторно-оптимизационные алгоритмы структурного синтеза заключаются в преобразовании исходной модели в модель результата. В [8] отмечается, что над разными структурами данных одни и те же операции выполняются с различными вычислительными сложностями. Поэтому, важной задачей при оптимизации комбинаторных алгоритмов является выбор структур данных, обеспечивающих минимизацию вычислительной сложности при допустимом значении емкостной сложности. Более того, именно оптимизация выбора структур представления исходных данных, промежуточных данных и результатов позволяет оптимизировать вычисления самих комбинаторных алгоритмов (ярким примером может служить алгоритм Прима) [10,24].
В настоящий момент данной проблеме уделяется большое внимание исследователей, направленное на исследование новых структур данных. Подробно такие структуры описаны в [10,8,9,1,2,5,37,42]. Однако, можно выявить следующие недостатки данных трудов в исследовании различных структур данных: а Не определена и не классифицирована совокупность структур, на основании которой производится выбор. Не определено множество операций над структурами данных, а Правила выбора структур данных для конкретных алгоритмов не формализованы. ? Сравнение структур данных носит неполный, нечеткий характер. ? Все указанные недостатки приводят к тому, что задача выбора структур данных формально не поставлена и четко не сформулирована, что ограничивает возможность ее целенаправленного решения.
Для практических задач часто требуется производить такую совокупность операций над данными, которую можно эффективно реализовать лишь с помощью нескольких связанных структур. Как показано в [10,24,8,9], применение сложных иерархических структур данных позволяет сократить.вычислительную сложность алгоритмов. В [10] описана реализация алгоритма Прима и Крускала поиска минимального покрывающего дерева с помощью двоичной кучи, что позволяет значительно уменьшить его вычислительную сложность. Однако выбор данных иерархических структур недоказателен из-за отсутствия как самой сформулированной задачи, так и исходных данных для ее решения.
В отличие от других предметных областей, для комбинаторно-оптимизационных алгоритмов структурного синтеза характерно четкое представление о составе и последовательности выполняемых действий. Это позволяет представить сложность алгоритма в виде совокупности сложностей выполняемых операций. Например: для алгоритма Прима определения минимального покрывающего дерева на графе схемы из п элементов и m цепей, применяемого для решения задачи коммутации, требуется п раз выполнить операцию удаления элемента структуры с минимальным ключом, m раз выполнить поиск и m раз изменить значение ключа [10]. Такая детализация должна позволить сконструировать наиболее "подходящую" структуру.
Данная задача относится к классу комбинаторно-оптимизационных и заключается в построении последовательности шагов из конечного множества вариантов, ведущих к получению оптимального решения. Необходимо определить совокупность из известных методов решения задач комбинаторной оптимизации, которые могли бы быть применены для ее решения.
На каждом шаге решения комбинаторно-оптимизационной задачи делается выбор из некоторой совокупности возможных дальнейших действий. Такую работу можно представить в виде дерева элементарных шагов (дерева поиска решения) [8,9,10]. Как показано в [11] различные методы строят данное дерево и делают выбор по-разному. Построение дерева обычно заключается в декомпозиции пространства решений [8,9,10]: задача разбивается на подзадачи меньшей размерности, а выбор заключается в определении перспективного направления для дальнейшей декомпозиции.
Исследование операций над древовидными и сетевыми структурами
Свойства деревьев достаточно подробно рассмотрены в [1,2,8,9,10,37,42], но сложности многих из предложенных в данной работе операций над структурами данных в них не определены. Поэтому кратко опишем правила применения основных видов деревьев и определим сложности выполнения базовых операций.
В общем случае деревом можно считать структуру Т вида: T:{V0,..., Vn.!}, V0=Root[T] (Parent[Vo]=0), VV; 3! Vk (Parent[Vi]=Vk), i,k=0,...,n-l, (2.4) где Vi - вершины дерева, Vo - корень дерева, определяемый функцией Root[T], Parent[Vi] - функция, определяющая единственную родительскую вершину для любой из вершин дерева (у корня дерева нет родительской вершины).
Для хранения такой структуры применяется дополнительная функция: Child[Vi]=Q, VVj, VjeQ Parent[Vj]=Vi. (2.5) Child[Vi] - функция, определяющая дочерние для Vj вершины (Рис 2.6). Для некоторых вершин множество СІ может быть пустым. Такие вершины называются висячими (или конечными).
Как отмечно в [8], сама природа представления данных в компьютере устанавливает точный порядок для всякого дерева, и поэтому в большинстве случаев наибольший интерес для нас представляют упорядоченные деревья. Это значит, что между родительскими и дочерними вершинами существует отношение порядка на ключах (как и ранее, будем считать что, либо каждый элемент структуры содержит специальное поле ключа, либо сама информация является ключом). Для деревьев поиска ключ левого потомка любой вершины дерева должен быть меньше или равен ее собственному ключу, а ключ правого потомка - больше. Для куч (разновидности деревовидных структур данных) ключ родительской вершины должен быть меньше или равен любому из ключей ее листьев.
На физическом уровне абстракции деревья могут быть отображены в память как последовательным, так и связным распределением. Связное распределение наиболее естественно отображает дерево в памяти и, поэтому, большинство древовидных структур использует именно его. Для того,.чтобы представить дерево линейной структурой необходимо задать последовательность обхода. При обходе дерева в прямом порядке сначала просматривается левый потомок и его поддеревья, а потом переходят к правому потомку. Далее представление дерева заключается в расстановке скобок в последовательной записи вершин. Возможны также и другие способы обхода деревьев: в фамильном и обратном порядках. Подробно данные варианты описаны в [8].
Важным свойством деревьев является возможность выполнения операции поиска, удаления и добавления за 0(log п), что _ достигается благодаря поддержанию условий сбалансированности.
AVL-деревья являются бинарными сбалансированными деревьями поиска. Бинарное дерево называется сбалансированным, если высота левого поддерева любого узла отличается не более чем на +1 от высоты правого поддерева. Если не вводить условий балансировки, то дерево может выродиться в простой линейный список. Однако, для сбалансированного дерева этого не происходит, т.к. его высота всегда ограничена. В [8,9,10] также показано, что высота h сбалансированного дерева с п внутренними (не конечными) узлами определяется неравенством: log (n+1) h 1,4405 log (n+2) - 0,3277. (2.6)
Примером AVL-деревьев может служить дерево поиска Фибоначчи [9] (Рис. 2.7): при прохождении от корня к листьям ключи просмотренных вершин отличаются на значение Fn, где Fn - число Фибоначчи порядка п:
Т.к. сложности операций поиска, добавления, удаления зависят от высоты дерева, то их оценка составляет 0(log п). При добавлении или удалении вершины в сбалансированном дереве балансировка может нарушиться. Для ее восстановления может потребоваться 0(log п) специальных балансирующих операций - левых и правых вращений, сложность которых составляет 0(1) [8,10], т.е. добавление и удаление требует 0(log и) операций. Операции поиск MTN, поиск МАХ, следующий и предыдущий требует в худшем прохождения 0(log п) вершин, т.е. всей высоты дерева. Вместе с тем, операция поиска порядковой статистики требует 0(k+log п) операций, т.к. за к шагов при поиске следующей за данной вершины будет просмотрено дополнительно не более 0(log п) вершин дерева, не являющихся таковыми и на просмотр каждой вершины требуется 0(1) операций. Можно также заключить, что операция мощность требует 0(п) операций, т.к. при k=n все вершины дерева будут рассмотрены за 0(п) шагов. Исходя из этого очевидно, что из сбалансированного дерева поиска можно за 0(п) шагов получить отсортированную последовательность ключей.
Алгоритмы свертки без учета связности
Содержательное описание алгоритма неуравновешенной двоичной свертки (Рис. 3.2) включает следующие пункты: 1. Определить показатели связности для всех пар вершин по ГХ и ТО. 2. Найти пару вершин с максимальной связностью. 3. Связать выбранные вершины в новую. 4. Изменить множества ГХ и ТО. 5. Исключить одну из связанных вершин и пересчитать показатели связности объединенной вершины. 6. Если осталось две вершины то переход к п.7, иначе - к п.2. 7. Конец. определяем матрицу СВЯЗНОСТИ S длявсехэлементовГХ и Ги Находим пару XI и X;) с MAX(S13) СвязываемXI и хз Исключаем изГХ и Ги элементыXI и Xj и заносимобъединеннуювершину Исключаем из SX;}, а новыепоказатели записываем на местоXI В X две s , Нет вершины Рис. 3.2. Алгоритм неуравновешенной двоичной свертки без предварительного учета связности
Рассмотрим первый уровень с количеством вершин равным п. Для определения связываемых вершин необходимо найти показатели связности всех вершин данного уровня попарно. Т.е. для данных вариантов алгоритма свертки (без предварительного учета связности) необходимо хранить все показатели связности для всех пар вершин. Очевидно, что вычислительная и емкостная сложности реализации алгоритма зависят от размеров исходной информации, и, в данном случае, могут быть велики. Это связано с тем, что необходимо перебрать все возможные пары элементов (их количество равно п(п-1)/2), и для них определить показатели связности Sy.
Вычислительная сложность определения одного показателя будет заключаться в просмотре и сравнении одного множества ГХ для вершины Xj с каждым ребром из множества ГХ для вершины Xj (длина обоих множеств равна ро). Таким образом: Sij=Po . Сложность выполнения рассматриваемой операции: S, = n(n-l)/702/2.
Определение пары вершин, обладающих максимальным показателем связности, осуществляется сравнением и выбором максимального из найденных ранее t(t-l)/2 показателей: S2 = t(t-l)/2 - 1. Пересчет показателей связности факторизованной вершины требует S3=(t-2)/} операций сравнения и вместе с поиском максимальных связанных вершин выполняется для всех последующих уровней свертки t=(n-l),..,2. Для более трудоемкого первого случая на некотором уровня свертки t схема садержит t элементов и один из них является результатом факторизации (п+l) элементов исходной схемы. Этот случай возможен, если для всех шагов факторизация происходит в один и тот же макроэлемент. Таким образом: /?,=/?o(n+l)R. В связи с этим, общая вычислительная сложность данного метода: «-і 8сл10бщ = n(n-lW/2 + n(n-l)/2 -1 + I (t(t-l)/2 -1 + (t-2)p02(n+\)2R). t= Далее будем оценивать вычислительную сложность алгоритма для схем средней степени связности, для которых показатель Рента принимает значение R-0.5. Упрощая полученную формулу, получаем: 8СЛ1О6Щ=АДІ3/6+П3/6 -1р02п16-5п1в+2ро+\. (3.3) Таким образом, оценка сверху вычислительной сложности алгоритма в худшем будет: OMVi) = O(nW+l),np02). (3.4)
Для оценки сложности свертки для схем второго типа математическое ожидание количества элементов исходной схемы для уровня t, на котором рассматривается t вершина, будет равно: M(nt) = n/t. (3.5) В связи с этим для оценки вычислительной сложности свертки во втором случае значение pt будет изменяться соответственно: p,=po(n/t) . Общая сложность в среднем составит: SCJ1-206n, = п(п-\)р2/2 + п(п-1)/2 -1 + Z (t(t-l)/2 -1 + (t-2)p0\n/t)2R). 1=2
Упрощая полученную формулу при R-0.5, получаем: SCJ1-2O6m=n3/6+2nV//3-2p0nxln(n)+n( /2-5/6)+l. (3.6) Таким образом, оценка сверху вычислительной сложности данного алгоритма в среднем будет: Осл2(А0 = 0(п3, п2ро, про2). (3.7) Емкостная сложность данного алгоритма зависит от величины матрицы связности. SeMK = Vin, где V] - объем, необходимый для хранения одного показателя связности (в байтах), Vi = ]log2p/8[.
Алгоритм уравновешенной свертки без учета связности (Рис. 3.3) содержит следующие действия: 1. Найти показатели связности для всех элементов по ГХ и Ги. 2. Определить пару элементов с максимальной связностью. 3. Связать выбранные вершины X; и Xj 4. Исключить из рассмотрения на данном уровне вершины xj и Xj. 5. Определить максимально связанные элементы без учета уже связанных на этом уровне. 6. Если на данном уровне все вершины связаны, то переход к п.7 иначе к п.З. 7. Если осталось две вершины то к п.8, иначе к п. 1. 8. Конец. [ Качала ) Определяем матрицу свячности 8 для всех элементов ГХ и ГЦ
Т.к. в алгоритмах уравновешенной свертки происходит связь всех пар вершин на каждом уровне, то их количество уменьшается вдвое при переходе с уровня на уровень. При этом не требуется пересчитывать показатели связности после объединения двух вершин. Это необходимо делать только один раз на каждом уровне, что может дать некоторый выигрыш в вычислительной сложности по сравнению с алгоритмами неуравновешенной сверки.
Схемы реализации метода ветвей и границ
Рассмотрим проблему выбора очередной вершины ветвления. На основании изучения литературы [12,17,7,11,15,20,38,32,40,41,43,44] определены два возможных способа ветвления:
1. Ветвление по минимуму нижней границы (при отыскании минимума целевой функции). Определяется вершина дерева решений, для которой (p(t) f(to) минимальна (Рис. 4.5, а), в ней осуществляется ветвление, подсчитывается Si,2 для обеих вершин потомков, процесс повторяется для всех висячих вершин, т.е. еще не ставших концевыми в смысле окончания формирования Hi и Нг по соответствующим маршрутам.
2. Последовательное построение ветвей (Рис. 4.5, б). Находится один вариант решения задачи и строится полностью одна ветвь (назовем ее опорной). Полученое для опорного решения значение целевой функции f(t0) используется для отсечения подмножеств вариантов при поиске оптимального. Ветвление выполняется от построенной ветви последовательно, начиная с вершины, предшествовавшей конечной (обозначим ее V;). При этом новый маршрут достраивается до конца, если не происходит отсечение ветви, по минимуму нижней границы. Процедура повторяется по отношению к вершинам новой ветви, после построения всех возможных ветвей, проходящих через Vi, отыскивается следующая вершина Vj и процесс повторяется (см. Рис. 4.5). На этом рисунке индексы вершин показывают последовательность их появления по мере построения дерева решений (таким образом, УІУІУЗУАУЗ - опорная ветвь). В [12] отмечается, что при таком способе ветвления исследуется больше вершин, чем при ветвлении по минимуму нижней границы, но требуется хранить меньше данных о количестве построенных вершин.
Остановимся теперь на фундаментальной проблеме метода ветвей и границ - его эффективности. Известно [7,12,17,38], что она зависит от близости оценки к точной границе и от наличия f(t0) и степени близости ее к оптимальному значению целевой функции f(t ). Нижняя граница Si 1 в нашей задаче является точной оценкой связанности для каждого варианта текущего состава вершин кусков гиперграфа Н/ и Н2Т. Можно ожидать, что эффективность применения метода ветвей и границ будет тем выше, чем больше разность между нижними границами подмножеств вариантов решения, по крайней мере при достаточно равномерном возрастании оценки по ходу построения дерева пространства решений, т.е. по мере включения вершин гиперграфа в сформированные куски. Степень различия значений оценочной функции зависит от конкретных данных задачи, в нашем случае от распределения связей между элементами схемы, стратегии и схемы формирования подмножеств вариантов решения. Конкретные данные задачи(структура схемы) влияет также на изменение значения оценочной функции Sii2 по мере включения вершин гиперграфа в формируемые куски.
В задаче дихотомического разрезания гиперграфа при выбранном способе ветвления схема формирования вариантов решения определяется порядком включения вершин гиперграфа в подмножество Х/ и Х2Т, от которого зависит также величина разности нижних границ целевой функции в соседних вершинах дерева решений. Действительно, при очередном ветвлении рассматривается событие включения некоторой вершины гиперграфа, например х3, в состав подмножеств Х\ и Х2 (вершины V3 и V4 на Рис. 4.5, а).
Если вершина х2 имеет примерно одинаковую связность с кусками Hi и Н2 , то (Si,2( -Si 3)) - разность нижних границ для вершин 3 и 3 дерева решений незначительна, так как S,,2(3)=Si,2( 2)+ASu2(3) Su2( 3)=S,,2( 2)+AS,,2( 3),где Su( 2) T X показатель связности кусков Hi и H2 соответствующих вершине Vi дерева решений, AS(3) и AS( 3) - количество ребер типа Цз и U4 соответственно (см. Рис. 4.4.).
Исходя из выполненного анализа следует признать целесообразным нахождение опорного решения Hi0(Xi,Ui) последовательным алгоритмом по связности для получения значения f(t0) для целей отсечения. Полученные при этом множества вершин Xi и Х2 куска гиперграфа могут рассматриваться как X ={Xi,X2} и определять порядок их включения в формируемые т т подмножества Xi и Х2 , если используется показанная на Рис. 4.5, з схема формирования пространства решений. Заметим, что для получения Xу последовательный алгоритм придется применять дважды, так как Х2, определенное как Х2=Х\Хі, не является упорядоченным множеством (в смысле максимальной связности вершин). Поскольку ранжирование выполняется по критерию максимальной связанности, можно ожидать, что оно приведет к увеличению разности нижних границ подмножеств вариантов по всему дереву пространства решений и более равномерному возрастанию у "Т" нижних границ по ходу формирования Х\ и Х2 . Таким образом ранжирование в некоторой степени сгладит влияние структуры схемы на изменение значения Si . После построения ветви опорного решения ветвление будет выполняться от корня по минимуму нижних границ, так как этот способ прост в реализации и приводит обычно к получению точного решения при меньшем количестве исследованных вариантов.
