📄Работа №120004
Тема: Алгоритмизация труднорешаемой задачи размещения графа
Тип работы
Магистерская диссертация
Предмет
Информатика и вычислительная техника
Объем:
91 листов
Год:
2018
Просмотров:
212
4980
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
СОДЕРЖАНИЕ 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
ВВЕДЕНИЕ 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 ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ
В этой главе анализируется эффективность реализованных алгоритмов в сравнении с реализованным эвристическим алгоритмом.
ЗАКЛЮЧЕНИЕ
В заключении приводятся основные результаты работы, а также результаты проведенных вычислительных экспериментов.
Эта задача может помочь уменьшить время проектирования и достижения желаемых электрических параметров микросхемы.
Кроме того, алгоритмизация задачи размещения графа может помочь в решении других труднорешаемых задач, таких как задача коммивояжера, задача поиска гамильтонова цикла и т. д., так как они имеют много общего.
Проблема
На текущий момент для задачи размещения графа не существует эффективных алгоритмов ее решения. Это, прежде всего, связано с тем, что задача является труднорешаемой. Для решения задачи размещения графа применяют мультиэвристические алгоритмы такие, как генетические алгоритмы и другие. Применение этого класса алгоритмов вызывает трудности в эффективном исследовании этих алгоритмов, так как они в основном являются стохастическими и рассматривают задачу без ее конкретной структуры.
Кроме того, на данный момент неизвестно является ли задача размещения графа 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 ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ
В этой главе анализируется эффективность реализованных алгоритмов в сравнении с реализованным эвристическим алгоритмом.
ЗАКЛЮЧЕНИЕ
В заключении приводятся основные результаты работы, а также результаты проведенных вычислительных экспериментов.
✅ Заключение
В результате проведенного исследования была построена математическая модель задачи размещения графа, и, на ее основе, доказана теорема об NP- полноте задачи.
Была доказана теорема о том, что решение оптимизационной задачи размещения графа влечет за собой решение задачи размещения графа как задачи распознавания свойств для одной целевой функции.
Были разработаны два алгоритма, решающие задачу размещения графа. Алгоритм Hebene и стохастический алгоритм Hebene. Во время проведения вычислительных экспериментов, разработанные алгоритмы оказались сравнимы (или лучше) других алгоритмов решения задачи. В частности, при проведении вычислительных экспериментов на малых размерностях графов стохастический алгоритм Hebene показал 99% попадания в оптимум. В это же время алгоритм Hebene показал 72% попадания в оптимум, что оказалось сравнимо с результатами алгоритма локального поиска и генетического алгоритма, но оказался хуже, чем алгоритм имитации отжига - 94%. С увеличением размерности графов ситуация стабилизировалась и алгоритм Hebene оказался сравним с другими алгоритмами или оказался лучше них.
Для проведения вычислительных экспериментов были собраны попарно неизоморфные графы порядка 6, 7, 8 и 9, и разработан алгоритм генерации случайных графов. Кроме того, был разработан специальный формат хранения графов graph7, который позволяет хранить большое количество графов с минимальной избыточностью данных. Формат graph7 оказался более успешным, чем формат graph6: есть возможность хранить разные типы графов, место, занимаемое одним графов, не зависит от порядка этого графа.
Была получена оценка, позволяющая оценивать решения на их отклонение от оптимального решения для одной целевой функции.
Была доказана теорема о том, что решение оптимизационной задачи размещения графа влечет за собой решение задачи размещения графа как задачи распознавания свойств для одной целевой функции.
Были разработаны два алгоритма, решающие задачу размещения графа. Алгоритм Hebene и стохастический алгоритм Hebene. Во время проведения вычислительных экспериментов, разработанные алгоритмы оказались сравнимы (или лучше) других алгоритмов решения задачи. В частности, при проведении вычислительных экспериментов на малых размерностях графов стохастический алгоритм Hebene показал 99% попадания в оптимум. В это же время алгоритм Hebene показал 72% попадания в оптимум, что оказалось сравнимо с результатами алгоритма локального поиска и генетического алгоритма, но оказался хуже, чем алгоритм имитации отжига - 94%. С увеличением размерности графов ситуация стабилизировалась и алгоритм Hebene оказался сравним с другими алгоритмами или оказался лучше них.
Для проведения вычислительных экспериментов были собраны попарно неизоморфные графы порядка 6, 7, 8 и 9, и разработан алгоритм генерации случайных графов. Кроме того, был разработан специальный формат хранения графов graph7, который позволяет хранить большое количество графов с минимальной избыточностью данных. Формат graph7 оказался более успешным, чем формат graph6: есть возможность хранить разные типы графов, место, занимаемое одним графов, не зависит от порядка этого графа.
Была получена оценка, позволяющая оценивать решения на их отклонение от оптимального решения для одной целевой функции.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.