Разработка и реализация многоуровневых алгоритмов декомпозиции гиперграфовых моделей

• Автор: Филимонов, Андрей Викторович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Нижний Новгород
• Количество страниц: 123 с. : ил.

Оглавление
Оглавление.
Введение.

Актуальность темы исследований.

,ель работы

Научная новизна

Теоретическая и практическая ценность работы.

Апробация результатов

Глава 1. Методы решения декомпозиционных задач на гиперграфах

1.1. Постановка задачи разбиения.

1.2 Методы решения экстремальных декомпозиционных задач на гиперграфах.

1.2.1 Конструктивные алгоритмы
1.2.2 Улучшающие алгоритмы
1.2.3 Использование элементов рандомизации
Глава 2. Теоретические аспекты гииерграфовых структур.
2.1 Основные определения и понятия
2.1.1 Гиперграф, вершина, гиперребро
2.1.2 Визуализация гиперграфа.
2.1.4 Части, подграфы, суграфы и куски
2.1.5 Связность, компоненты, независимые множества
2.2. Базовые операции над гиперграфом.
2.2.1 Введение, удаление и стягивание гиперребра
2.2.2 Введение и удаление вершины из гиперребра
2.2.3 Введение и удаление вершины.
2.2.4 Удаление частей гиперграфа
2.2.5 Стягивание множества вершин и отождествление множества гипсррсбср
2.2.6 Расщепление вершин и гиперребер.
2.2.7 Бинарные операции над гиперграфами
2.3. Операции фильтрации и фильтры
2.3.1 Помеченные гиперграфы.
2.3.2 Операции с атрибутивной информацией.
2.3.3 Фильтр и процесс фильтрации.
2.3.4 Категории типы фильтров.
2.4. Виды гиисрграфа
3. Многоуровневый алгоритм декомпозиции гиперграфа
3.1 Общая схема работы многоуровневого алгоритма декомпозиции.
3.2 Фаза загрубления
3.2.1 Алгоритм реберного загрубления
3.2.2 Схема гиперреберного загрубления
3.2.3 Модифицированная схема гиперреберного загрубления.
3.2.4 Алгоритм построения затрубленного гиперграфа
3.3 Фаза поиска начального разбиения ч
3.4 Фаза восстановления решения.
3.5 Использование концепции фильтрвид для построения многоуровневого алгоритма декомпозиции
3.5.1 Фага загрубления
2.5.2 Фаза поиска начального разбиения
3.5.3 Фаза восстановления решения.
3.6 Многоуровневый алгоритм с элементами эволюционногенетического поиска
4. Программная реализация.
4.1. Объектноориентированная реализация гиперграфовой системы
4.1.1. Модель работы с гинерграфом
4.1.2. Объектноориентированное представление гиперграфовой структуры
4.1.3. Фильтры и виды гиперграфа
4.1.4. Повышение производительности работы системы
4.2 Реализация многоуровневого алгоритма декомпозиции.
4.2.1 Общая структура классов многоуровневого алгоритма декомпозиции.
4.2.2 Конфигурирование многоуровневог о алгоритма.
4.2.3 Трудности реализации многоуровневого подхода
4.2.4 Реализация улучшающег о генетического алгоритма
4.3 Вычислительный эксперимент.
5. Задача компоновки при проектировании полузаказных БИС на
основе базовых матричных крист аллов.
5.1. Процессы проектирования ВИС.
5.2 Задача компоновки при проектировании БМК
5.3 Формализация задачи компоновки.
5.4 Вычислительный эксперимент.
Заключение.
Литература


Новгород, ), Всероссийской научно-технической конференции «Информационные системы и технологии» ИСТ- (Н. Новгород, г. ВМК МИГУ. Глава 1. Проблема к-разбиения гиперграфа состоит в распределении множества вершин V по к подмножествам Уь. Ук, таким образом, чтобы удовлетворялся набор о1раничений, называемых декомпозиционными ограничениями, а оптимизируемая функция (функция цели, критерий оптимальности, функционал), определенная над разбиением, принимала экстремальное значение. Распределение предполагает, что множества У,,. Подмножества разбиения определяют подграфы разбиения [1]. Значение к фиксировано и задается как параметр задачи. В ограничениях (2) константы Ъ{ и Ц определяют пределы, в которых могут варьироваться веса подграфов разбиения. Критерии оптимальности, как и декомпозиционные ограничения, определяются спецификой конкретной задачи. В исследовании [1 приведено обширное описание функций цели, встречающихся при проектировании РЭЛ. Один из наиболее часто используемых критериев - минимизация веса сечения. Задачу (1)-(3) будем называть задачей к-разбиения гиперграфа. Возможны различные расширения проблемы (1)-(3). Например, задача может иметь несколько функций цели (многокритериальный случай), тогда решение состоит в нахождении Парето-области решений. Ес= : ? Эу,,у; е е. Теория гиперграфов - сравнительно молодой раздел дискретной математики, характеризующийся, однако, широким многообразием методов и теоретических результатов. Это связано с тем, что теория гиперграфов - наследник классической теории графов, и на объект исследования, гиперграф, было перенесено множество результатов, полученных ранее для частного случая гиперграфа - классического графа. Сказанное справедливо и для методов решения задач декомпозиции. Исследуемая задача к-разбисния гиперграфа №-грудна [1,2, , , , , 1, поэтому применение точных алгоритмов получения решения имеет не очень большое практическое значение. Действительно, гиперфаф - гораздо более сложный объект для исследования и программной реализации. Следствие этого -даже простые алгоритмы, перенесенные с графов, нередко усложняются настолько, что их применение становится нецелесообразным. С другой стороны, гиперграф -удобный объект моделирования, а к задачам его декомпозиции сводится множество прикладных задач проектирования радиоэлскронной аппаратуры, вычислительных сетей, баз данных, систем управления, задач дискретной оптимизации и линейной алгебры. На практике такие задачи, как правило, имеют большие размерности, что является еще одним фактором, обуславливающим неприменимость точных переборных методов. Однако, применение переборных методов все же возможно, например, как составную часть более сложных алгоритмов. В точных методах делается попытка максимизировать сокращение объема перебора, хотя при этом и предполагается неизбежность экспоненциального времени работы. Так, самый простой, но самый трудоемкий алгоритм “полного перебора” целесообразно применять только на гиперірафах е самой малой размерностью. К наиболее широко используемым приемам сокращенного перебора относятся приемы, основанные на методе “ветвей и границ” или методе “неявного перебора” [0, 6, 2]. Они состоят в построении “частичных решений”, представленных в виде дерева поиска, и применении мощных методов построения оценок, позволяющих опознать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге отсекается целая ветвь. Известны и другие подходы, когда процесс поиска организован иначе. К ним относятся методы отсечений [3] и метод Лагранжа [5]. Алгоритмы сокращенного перебора применимы для гиперграфов с малой и со средней размерностью. Методы динамического программирования также нашли свое применение в качестве основы для посіроения точных алгоритмов для решения задач на графах. Однако, как и методы “ветвей и границ”, для нахождения сірого оптимальні,їх решений на практике они используются редко из-за своей большой вычислительной сложности. Применение их в основе некоторого эвристического подхода [] позволяет применять их и для графов с большим числом вершин.