
Тип работы:	Предмет:	Язык работы:

Параллельные алгоритмы решения задачи коммивояжера методом ветвей и границ

Работа №	107656
Тип работы	Бакалаврская работа
Предмет	информатика
Объем работы	49
Год сдачи	2019
Стоимость	4335 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	72

Не подходит работа?

Узнай цену на написание

Содержание

ВВЕДЕНИЕ 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

Введение

Задача коммивояжера имеет множество применений в различных областях и сферах деятельности человека. Примерами могут служить доставка посылок, сбор детей школьным автобусом, сбор заказов на складе.
Одним из основных подходов к решению этой задачи является метод ветвей и границ. Его отличают следующие особенности, существенные с точки зрения распараллеливания: неизвестный заранее информационный граф и необходимость обмена информацией между вычислительными потоками. В работе предлагается подход к распараллеливанию метода ветвей и границ. Мы сравниваем этот подход с последовательными реализациями, а также исследуем влияние различных способов организации вычислительного процесса на производительность приложения.
Актуальность темы бакалаврской работы обусловлена тем, что в последнее время основным способом повышения производительности вычислительных устройств стало увеличение числа вычислительных ядер в процессорах. Поэтому особое значение приобретает разработка и улучшение параллельных реализаций для ресурсоёмких задач, к которым относится задача коммивояжера.
Объект работы: алгоритмы решения задачи коммивояжера.
Предмет исследования: сравнительный анализ реализаций алгоритма ветвей и границ и различных его вариаций на языке программирования Python.
Цель работы: реализовать параллельные алгоритмы решения задачи коммивояжера методом ветвей и границ, сравнить их эффективность с другими реализациями метода ветвей и границ.
Для достижения цели работы необходимо решить следующие задачи:
1) Рассмотреть вариации алгоритма ветвей и границ.
2) Реализовать параллельные алгоритмы ветвей и границ на языке Python.
3) Выявить достоинства и недостатки параллельных реализации алгоритма ветвей и границ, провести сравнительный анализ.

Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!

ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ

Курсовые Статьи Диплом Рязань

Заключение

В ходе выполнения бакалаврской работы рассмотрены теоретические аспекты теории графов, алгоритмы решения классической задачи коммивояжера, достоинства и недостатки алгоритмов, а также реализации параллельных и последовательных алгоритмов решения задачи коммивояжера методом ветвей и границ.
В работе приводится описание алгоритмов и их программных реализаций. Проведено экспериментальное исследование производительности разработанных параллельных и последовательных алгоритмов на представительном наборе тестовых примеров. Исследование показало, что параллельная реализация приводит к значительному ускорению вычислений по сравнению с любыми последовательными вариантами на больших объёмах данных.
Реализованы параллельные и последовательные алгоритмы решения задачи о коммивояжере на основе метода типа ветвей и границ. Исходя из полученных результатов, можно сделать следующие выводы. Выяснилось, что время решения задачи довольно быстро увеличивается с ростом размерности задачи. Параллельные реализации на небольших объёмах данных уступают последовательным реализациям. Но с увеличением количества входных данных растёт и эффективность параллельных реализаций.

Литература

1. Акимов О. Е. «Дискретная математика. Логика, группы, графы» / О.Е. Акимов. - Москва: Изд. «Лаборатория базовых знаний», 2003. - 376 с.
2. Бенгфорт Б. Прикладной анализ текстовых данных на Python. Машинное обучение и создание приложений обработки естественного языка / Б. Бенгфорт, Р Билбро, Т. Охеда. - СПб.: Питер, 2019. - 368 с.
3. Громкович Ю. Алгоритмизация труднорешаемых задач. Часть II. Более сложные эвристики. / Ю. Громкович, Б.Ф.Мельников // Перевод с английского Б.Ф. Мельников. Философские проблемы информационных технологий и киберпространства. - Пятигорск: 2014. - 612 с.
4. Емеличев В. А. Лекции по теории графов / В.А. Емиличев, О. И. Мельников, В. И. Сарванов, Р И. Тышкевич - Москва: Либроком, 2012. - 392 с.
5. Карепова Е.Д. Средства разработки параллельных программ: учебное пособие / Е.Д. Карепова, Д.А. Кузьмин, А.И. Легалов, А.В. Редькин, Ю.В. Удалова, Г. А. Федоров - Красноярск, 2007.
6. Кормен Т. Клиффорд. Алгоритмы: построение и анализ. 2 издание: Пер. С англ. / Т. Кормен, Ч. И. Лейзерсон, Р Л. Ривест, К. Штайн - М.: Издательский дом «Вильямс», 2015. - 1296 с.
7. Липский В. Комбинаторика для программистов: Пер. с польск. /В. Лимский - М:. Мир, 2014. - 213с.
8. Наоми С., Python. Экспресс-курс. 3-е изд./С. Наоми - СПб.: Питер, 2019. - 480 с.: ил. - (Серия «Библиотека программиста»)
9. Роганов Е.А. Основы информатики и программирования: Учебное пособие / Е.А. Роганов - М.: МГИУ, 2001. - 315 с.
10. Applegate D. On the solution of traveling salesman problem / D. Applegate, R.E. Bixby, V. Chvatal, and W Cook // Doc. Math., ICM(III). - 1998. - P 645¬656.
11. Sleator Daniel D. A data structure for dynamic trees / Daniel D. Sleator and E. Tarjan Robert // Journal of Computer and System Sciences. - 26 (3). 2013. P. 362-391. DOI:10.1016/0022-0000(83)90006-5.
12. Sleator Daniel D. Self-adjusting binary search trees / Daniel D. Sleator and E. Tarjan Robert // Journal of the ACM (ACM Press). 2015. - 32 (3). - P. 652-686. DOI:10.1145/3828.3835.
Электронные ресурсы
13. Востокин С.В. Обзор области параллельных вычислений [Электронный
ресурс]: учебное пособие. - Режим
доступа: http://www.williamspublishing.com/PDF/5-8459-0388-2/part.pdf
14. Гергель В.П. Высокопроизводительные вычисления для
многопроцессорных многоядерных систем [Электронный ресурс] : курс лекций. - Нижегородский государственный университет им. Ломоносова.
- Режим доступа: http://www.unn.ru/pages/e-library/methodmaterial/
15. Методы взаимодействия процессов [Электронный ресурс]: курс «Основы современных операционных систем. - НОУ «ИНТУИТ» - Режим доступа: http://www.intuit.ru/studies/courses/641/497/lecture/11282
16. Парадигмы параллельного программирования [Электронный ресурс]:
лекционный материал. - Режим доступа:
http://staff.mmcs.sfedu.ru/~dubrov/files/sl_parallel_05_paradigm.pdf
17. Проблема спящего парикмахера [Электронный ресурс]: Википедия -
свободная энциклопедия - Режим доступа:
https: //ru.wikipedia. огд/'№1к1/Проблема_спящего_парикмахера.й1ш1
18. GeeksforGeeks [Электронный ресурс:] Traveling Salesman Problem using
Branch And Bound - Режим доступа:
https://www.geeksforgeeks.org/traveling-salesman-problem-using-branch-and- bound-2/
19. Metanit [Электронный ресурс:] Руководство по языку программирования Python. - Режим доступа: https://metanit.com/python/tutorial/
20. Wikipedia [Электронный ресурс:] Travelling salesman problem. - Режим
доступа: https://en.wikipedia.org/wiki/Travelling_salesman_problem/