Разработка программного обеспечения среды исследования алгоритмов решения задачи коммивояжера
Пояснительная записка: 87 с., 45 рис., 22 табл., 15 источник, 4 прил.
Целью создания программного обеспечения является исследование результатов различных алгоритмов решения задачи коммивояжера.
Главным назначение программы является упрощение процесса исследования задач коммивояжера.
Объектом исследования является процесс решения задач коммивояжера.
Предметом исследования – алгоритмы задач коммивояжера.
Программа была разработана как программное средство, предназначенное для исследования задач коммивояжера.
СОДЕРЖАНИЕ
2 ОБОСНОВАНИЕ ВЫБОРА СРЕДСТВ РАЗРАБОТКИ ПО.. 11
2.1 Обоснование выбора языка программирования. 11
2.2 Анализ и обоснование выбора среды разработки. 12
2.3 Обоснование выбора совокупности модулей. 13
2.3.1 Обоснование выбора модуля tkinter 13
2.3.2 Обоснование выбора модуля Matplotlib. 13
2.3.3 Обоснование выбора модуля numpy. 14
3 АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА.. 15
3.2 Метод полного перебора. 16
3.3 Метод ближайшего соседа. 18
3.4 Улучшенный метод ближайшего соседа. 22
4 РАЗРАБОТКА И РЕАЛИЗАЦИЯ ПРИЛОЖЕНИЯ.. 31
4.1 Реализация метода полного перебора. 38
4.2 Реализация метода ближайших соседей. 39
4.3 Реализация улучшенного метода ближайших соседей. 40
4.4 Реализация метода ветвей и границ. 41
5 ТЕСТИРОВАНИЕ СИСТЕМЫ И АНАЛИЗ РЕЗУЛЬТАТОВ. 43
6 ОХРАНА ТРУДА, ВОПРОСЫ БЕЗОПАСНОСТИ ЖИЗНЕДЕЯТЕЛЬНОСТИ И ГРАЖДАНСКОЙ ОБОРОНЫ.. 59
6.1 Анализ условий труда в помещении с ПК.. 59
6.2 Мероприятия по улучшению условий труда. 60
6.2.1 Расчет заземления общего контура здания, который должен быть выведен к каждой розетке с ПК.. 62
6.3 Мероприятия по обеспечению пожарной безопасности. 64
6.5 Безопасность жизнедеятельности. 68
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ.. 74
Приложение А ТЕХНИЧЕСКОЕ ЗАДАНИЕ. 76
1. Большакова Е. И., Мальковский М. Г., Пильщиков В. Н. Искусственный интеллект. Алгоритмы эвристического поиска [Электронный ресурс] // Учебная литература факультета ВМК МГУ. URL: http://recyclebin.ru/BMK/II/ii.html (дата обращения: 08.10.2015).
2. Бронштейн Е. М., Заико Т. А. Детерменированные оптимизационные задачи транспортной логистики // Автоматика и телемеханика, 2010. №10. С. 133-147.
3. Вишняков П.О. Планирование маршрутов с использованием модифицированного метода «ближайшего соседа» //Математические методы в технике и технологиях - ММТТ. 2014. № 6 (65). С. 63-67.
4. Гладков Л.А., Баринов С.В., Разработка новых подходов к решению транспортной задачи с использованием геоинформационных технологий // Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР», 2009. №2. С. 141-144
5. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Р., Штайн К. Алгоритмы. Построение и анализ. 2 изд. М.: Вильямс, 2012. 1296 с.
6. Курейчик В.М., Кажаров А.А. Муравьиные алгоритмы для решения транспортных задач. // Известия РАН. Теория и системы управления. – 2010. № 1. С. 32-45.
7. Левитин А. В. Алгоритмы: введение в разработку и анализ. М.: Вильямс, 2006. 576 с.
8. Маций О.Б. Повышение точности симметричной задачи класса коммивояжера большой размерности // Вестник Харьковского национального автомобильно-дорожного университета. 2011. № 55. С. 100-102.
9. Седжвик Р. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++, СПб: ДиаСофт, 2002. 688 с.
10. Ураков А.Р., Михтанюк А.А. Оценка количества вариантов обхода в задаче коммивояжера с дополнительными условиями //Глобальный 42 научный потенциал, 2012. № 21. С. 82-86.
11. Bang-Jensen J., Gutin G., Yeo A. When the greedy algorithm fails // Discrete Optimization. 2004 Vol. 1, No 2. P. 121-127.
12. Berbeglia G., Cordeau J.F., Gribkovskaia I., Laporte G. Static pickup and delivery problems: A classification scheme and survey // TOP. 2007. V. 15. No 1. P. 1-31.
13. Kellerer H., Pferschy U., Pisinger D. Knapsack problems. // Springer-Verlag, 2003. 548 с
14. Paar C., Pelzl J. Understanding cryptography: a textbook for students and practitioners. Berlin: Springer, 2010. 372 c.
15. Parragh S., Doerner K., Hartl R. A survey on pickup and delivery problems. Part II: Transportations between customers and depot // J. Betriebswirtschaft. 2008. V. 58. No 2. P. 81-117.
