📄Работа №107656
Тема: Параллельные алгоритмы решения задачи коммивояжера методом ветвей и границ
Тип работы
Бакалаврская работа
Предмет
информатика
Объем:
49 листов
Год:
2019
Просмотров:
215
4335
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
1 ОПИСАНИЕ АЛГОРИТМОВ 4
1.1 Общая характеристика задачи о коммивояжере 4
1.1.1 Основные понятия теории графов 4
1.1.2 Постановка задачи коммивояжера 7
1.1.3 Математическая модель задачи коммивояжера 8
1.2 Параллельные алгоритмы 11
1.2.1 Параллелизм 11
1.2.2 Потоки и процессы 12
1.2.3 Синхронизация в многопоточных приложениях 15
1.3 Метод ветвей и границ и его улучшения для решения задачи
коммивояжера 16
1.3.1 Общая схема метода ветвей и границ для оптимизационных задач .... 16
1.3.2 Метод ветвей и границ, применительно к решению задачи
коммивояжера 18
1.3.3 Параллельные алгоритмы 22
2 РЕАЛИЗАЦИЯ АЛГОРИТМОВ 27
2.1 Разработка приложения 27
2.1.1 Постановка требований 27
2.1.2 Выбор технических средств 27
2.2 Реализация последовательного алгоритма ветвей и границ 29
2.3 Реализация параллельного алгоритма с централизованным управлением 31
2.4 Реализация параллельного алгоритма с распределённым управлением . ... 31
3 СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕАЛИЗАЦИЙ 34
3.1 Средства и методы тестирования 34
3.2 Сравнительный анализ алгоритмов 36
ЗАКЛЮЧЕНИЕ 44
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 45
1 ОПИСАНИЕ АЛГОРИТМОВ 4
1.1 Общая характеристика задачи о коммивояжере 4
1.1.1 Основные понятия теории графов 4
1.1.2 Постановка задачи коммивояжера 7
1.1.3 Математическая модель задачи коммивояжера 8
1.2 Параллельные алгоритмы 11
1.2.1 Параллелизм 11
1.2.2 Потоки и процессы 12
1.2.3 Синхронизация в многопоточных приложениях 15
1.3 Метод ветвей и границ и его улучшения для решения задачи
коммивояжера 16
1.3.1 Общая схема метода ветвей и границ для оптимизационных задач .... 16
1.3.2 Метод ветвей и границ, применительно к решению задачи
коммивояжера 18
1.3.3 Параллельные алгоритмы 22
2 РЕАЛИЗАЦИЯ АЛГОРИТМОВ 27
2.1 Разработка приложения 27
2.1.1 Постановка требований 27
2.1.2 Выбор технических средств 27
2.2 Реализация последовательного алгоритма ветвей и границ 29
2.3 Реализация параллельного алгоритма с централизованным управлением 31
2.4 Реализация параллельного алгоритма с распределённым управлением . ... 31
3 СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕАЛИЗАЦИЙ 34
3.1 Средства и методы тестирования 34
3.2 Сравнительный анализ алгоритмов 36
ЗАКЛЮЧЕНИЕ 44
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 45
📖 Введение
Задача коммивояжера имеет множество применений в различных областях и сферах деятельности человека. Примерами могут служить доставка посылок, сбор детей школьным автобусом, сбор заказов на складе.
Одним из основных подходов к решению этой задачи является метод ветвей и границ. Его отличают следующие особенности, существенные с точки зрения распараллеливания: неизвестный заранее информационный граф и необходимость обмена информацией между вычислительными потоками. В работе предлагается подход к распараллеливанию метода ветвей и границ. Мы сравниваем этот подход с последовательными реализациями, а также исследуем влияние различных способов организации вычислительного процесса на производительность приложения.
Актуальность темы бакалаврской работы обусловлена тем, что в последнее время основным способом повышения производительности вычислительных устройств стало увеличение числа вычислительных ядер в процессорах. Поэтому особое значение приобретает разработка и улучшение параллельных реализаций для ресурсоёмких задач, к которым относится задача коммивояжера.
Объект работы: алгоритмы решения задачи коммивояжера.
Предмет исследования: сравнительный анализ реализаций алгоритма ветвей и границ и различных его вариаций на языке программирования Python.
Цель работы: реализовать параллельные алгоритмы решения задачи коммивояжера методом ветвей и границ, сравнить их эффективность с другими реализациями метода ветвей и границ.
Для достижения цели работы необходимо решить следующие задачи:
1) Рассмотреть вариации алгоритма ветвей и границ.
2) Реализовать параллельные алгоритмы ветвей и границ на языке Python.
3) Выявить достоинства и недостатки параллельных реализации алгоритма ветвей и границ, провести сравнительный анализ.
Одним из основных подходов к решению этой задачи является метод ветвей и границ. Его отличают следующие особенности, существенные с точки зрения распараллеливания: неизвестный заранее информационный граф и необходимость обмена информацией между вычислительными потоками. В работе предлагается подход к распараллеливанию метода ветвей и границ. Мы сравниваем этот подход с последовательными реализациями, а также исследуем влияние различных способов организации вычислительного процесса на производительность приложения.
Актуальность темы бакалаврской работы обусловлена тем, что в последнее время основным способом повышения производительности вычислительных устройств стало увеличение числа вычислительных ядер в процессорах. Поэтому особое значение приобретает разработка и улучшение параллельных реализаций для ресурсоёмких задач, к которым относится задача коммивояжера.
Объект работы: алгоритмы решения задачи коммивояжера.
Предмет исследования: сравнительный анализ реализаций алгоритма ветвей и границ и различных его вариаций на языке программирования Python.
Цель работы: реализовать параллельные алгоритмы решения задачи коммивояжера методом ветвей и границ, сравнить их эффективность с другими реализациями метода ветвей и границ.
Для достижения цели работы необходимо решить следующие задачи:
1) Рассмотреть вариации алгоритма ветвей и границ.
2) Реализовать параллельные алгоритмы ветвей и границ на языке Python.
3) Выявить достоинства и недостатки параллельных реализации алгоритма ветвей и границ, провести сравнительный анализ.
✅ Заключение
В ходе выполнения бакалаврской работы рассмотрены теоретические аспекты теории графов, алгоритмы решения классической задачи коммивояжера, достоинства и недостатки алгоритмов, а также реализации параллельных и последовательных алгоритмов решения задачи коммивояжера методом ветвей и границ.
В работе приводится описание алгоритмов и их программных реализаций. Проведено экспериментальное исследование производительности разработанных параллельных и последовательных алгоритмов на представительном наборе тестовых примеров. Исследование показало, что параллельная реализация приводит к значительному ускорению вычислений по сравнению с любыми последовательными вариантами на больших объёмах данных.
Реализованы параллельные и последовательные алгоритмы решения задачи о коммивояжере на основе метода типа ветвей и границ. Исходя из полученных результатов, можно сделать следующие выводы. Выяснилось, что время решения задачи довольно быстро увеличивается с ростом размерности задачи. Параллельные реализации на небольших объёмах данных уступают последовательным реализациям. Но с увеличением количества входных данных растёт и эффективность параллельных реализаций.
В работе приводится описание алгоритмов и их программных реализаций. Проведено экспериментальное исследование производительности разработанных параллельных и последовательных алгоритмов на представительном наборе тестовых примеров. Исследование показало, что параллельная реализация приводит к значительному ускорению вычислений по сравнению с любыми последовательными вариантами на больших объёмах данных.
Реализованы параллельные и последовательные алгоритмы решения задачи о коммивояжере на основе метода типа ветвей и границ. Исходя из полученных результатов, можно сделать следующие выводы. Выяснилось, что время решения задачи довольно быстро увеличивается с ростом размерности задачи. Параллельные реализации на небольших объёмах данных уступают последовательным реализациям. Но с увеличением количества входных данных растёт и эффективность параллельных реализаций.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.