СОДЕРЖАНИЕ 2
ВВЕДЕНИЕ 4
Глава 1 АНАЛИЗ ЛИТЕРАТУРЫ 9
1.1 Современная математическая модель 11
1.3 Алгоритмы решения задачи размещения графа 15
1.4 Выводы проведенного анализа литературы 16
Глава 2 АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 17
2.1 Разработка математической модели 17
2.1.1 Термины и определения 17
2.1.2 Об NP-полноте задачи размещения графа 21
2.1.3 Вспомогательные результаты 23
2.2 Алгоритмы решения задачи размещения графа 26
2.2.1 Алгоритм локального поиска 26
2.2.2 Алгоритм имитации отжига 27
2.2.3 Генетический алгоритм 31
2.3 Вспомогательный метод оптимизации 36
2.4 Выводы проведенного анализа предметной области 39
Глава 3 РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ГРАФА 41
3.1 Реализация алгоритмов решения задачи размещения графа 41
3.1.1 Реализация алгоритма имитации отжига и алгоритма
локального поиска 41
3.1.2 Реализация генетического алгоритма 42
3.1.3 Эвристический алгоритм Hebene 44
3.1.4 Стохастический алгоритм Hebene 46
3.2 Разработка программного обеспечения 47
3.3 Демонстрация программного обеспечения 52
3.4 Сбор данных для вычислительных экспериментов 55
3.4.1 Генерация случайных графов 56
3.4.2 Получение попарно неизоморфных графов 59
3.4.3 Способы хранения большого количества графов 61
3.5 Выводы 69
Глава 4 ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ 71
4.1 Сравнение скорости работы алгоритмов 71
4.2 Сравнение поисковых способностей алгоритмов 74
4.2.1 Сравнение поисковых способностей алгоритмов на графах
малых порядков 74
4.2.2 Сравнения поисковых способностей алгоритмов для графов
больших порядков 76
4.3. Некоторые вспомогательные вычислительные эксперименты 84
4.3.1 Оценка решений графов на отклонение от оптимальных решений 84
4.3.2 Пример размещения графа в сетке 85
4.4 Выводы проведенных вычислительных экспериментов 86
ЗАКЛЮЧЕНИЕ 88
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 89
Купить

Работа посвящена алгоритмизации задачи размещения графа. Приложением задачи размещения графа является задача размещения элементов СБИС.
Эта задача может помочь уменьшить время проектирования и достижения желаемых электрических параметров микросхемы.
Кроме того, алгоритмизация задачи размещения графа может помочь в решении других труднорешаемых задач, таких как задача коммивояжера, задача поиска гамильтонова цикла и т. д., так как они имеют много общего.
Проблема
На текущий момент для задачи размещения графа не существует эффективных алгоритмов ее решения. Это, прежде всего, связано с тем, что задача является труднорешаемой. Для решения задачи размещения графа применяют мультиэвристические алгоритмы такие, как генетические алгоритмы и другие. Применение этого класса алгоритмов вызывает трудности в эффективном исследовании этих алгоритмов, так как они в основном являются стохастическими и рассматривают задачу без ее конкретной структуры.
Кроме того, на данный момент неизвестно является ли задача размещения графа NP-полной, а лишь известно, что нет алгоритмов решающих ее эффективно.
Также не существует оценок, которые могли бы дать возможность оценивать решения для задачи размещения графа.
Объект и предмет исследования
Объектом исследования является задача размещения графа.
Предметом исследования является доказательство NP-полноты задачи размещения графа, разработка детерминированного эвристического алгоритма, нахождение оценки ее решений.
Цель исследования
Доказать NP-полноту задачи размещения.
Разработать эвристический алгоритм решения задачи размещения графа.
Выявить возможную оценку для решений задачи размещения графа.
Гипотеза исследования
Для доказательства NP-полноты нужна математическая модель на основании аппарата теории NP-полноты.
Существует эвристический алгоритм решения задачи размещения графа, который может быть сравним с существующими методами, но не являться стохастическим.
Существует оценка для решений задачи размещения графа на отклонение от оптимальный решений.
Задачи исследования
Рассмотрим этапы и задачи исследования, возникающие в процессе:
• анализ необходимости эвристического подхода;
о построение математической модели с использованием аппарата теории NP-полноты;
о доказательство NP-полноты задачи;
• построение эвристического алгоритма;
о анализ существующих алгоритмов решения;
о построение алгоритма решения;
• построение существующих алгоритмов для сравнения их результата с разработанным алгоритмом;
о построение существующих алгоритмов решения для сравнительного анализа с разработанным алгоритмом;
• сбор данных для вычислительных экспериментов;
о сбор всех попарно неизоморфных графов малых порядков для проведения сравнительного анализа алгоритма;
о разработка алгоритма генерации случайных графов с для анализа алгоритма на больших размерностях графов;
о разработка способа хранения большого количества графов;
Теоретическая основа
В связи с тем, что задача размещения графа является труднорешаемой, исследования в данной области направлены на нахождения эффективных эвристических и стохастических алгоритмов решения задачи.
Текущее состояние проблемы таково, что силы исследователей направлены на подбор параметров для существующих мультиэвристических алгоритмов.
Например, авторы [9], [1], [12] в своих работах используют различные мультиэвристические алгоритмы для решения задачи размещения графа.
Некоторые авторы [24], не заостряя свое внимание на конкретной задаче размещения графа, выделяют общие свойства графов, которые могут помочь в построении эффективных алгоритмов решения.
Методологическая основа
В качестве методологической основы использовались такие разделы, как теория формальных языков, теория NP-полноты, теория графов и теория алгоритмов.
Основные этапы исследования и апробация результатов
Этапы исследования:
• анализ необходимости эвристического подхода;
• построение эвристического алгоритма;
• построение существующих алгоритмов для сравнения их результата с разработанным алгоритмом;
• сбор данных для вычислительных экспериментов;
Для апробации результатов проводились сравнительные вычислительные эксперименты разработанного алгоритма с другими известными алгоритмами.
В работе [8] автором были опубликованы результаты построения математической модели и доказательство NP-полноты задачи.
В работах [13, 22] был представлен разработанный детерминированный эвристический алгоритм Hebene.
Научная новизна, теоретическая и практическая значимость
Во время исследования впервые была доказана NP-полнота задачи размещения графа.
Был построен эвристический алгоритм. Это, в первую очередь, означает, что требуются дальнейшие исследования этого алгоритма с целью выявления механизма его работы, которые могут помочь решению задач подобного рода.
Была получена оценка решений для задачи размещения графа. Такая оценка является полезной при исследовании алгоритмов для задачи, так как позволяет оценить приближенное отклонение найденного решения от оптимального.
Разработанный алгоритм может применяться для решения задачи размещения элементов СБИС.
Основные положения
Доказано, что задача размещения графа является NP-полно.
Разработан эвристический алгоритм решения задачи размещения графа.
Получена оценка оптимальных решений задачи.
Разработан специальный формат хранения большого количества графов graph7.
Объем и структура
Работа изложена на 91 страницах, содержит 41 рисунок и 6 таблиц.
Диссертационное исследование состоит из следующих глав.
Глава 1 АНАЛИЗ ЛИТЕРАТУРЫ
В этой главе делается анализ существующих публикаций по теме исследования, приводятся методы и алгоритмы, которые используют другие авторы.
Глава 2 АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ
В этой главе приводится разработанная математическая модель для задачи размещения графа. Вводятся термины и определения. Доказывается теорема об NP-полноте задачи размещения графа. Проводится анализ существующих алгоритмов решения, их параметров и особенностей.
Глава 3 РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ГРАФА
В этой главе приводится реализации существующих алгоритмов, а также описываются разработанный алгоритм.
Приводятся методы сбора данных для вычислительных экспериментов.
Описывается разработанный формат хранения графов graph7.
Глава 4 ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ
В этой главе анализируется эффективность реализованных алгоритмов в сравнении с реализованным эвристическим алгоритмом.
ЗАКЛЮЧЕНИЕ
В заключении приводятся основные результаты работы, а также результаты проведенных вычислительных экспериментов.
Купить