Разработка программного обеспечения среды исследования алгоритмов решения задачи коммивояжера

Пояснительная записка: 87 с., 45 рис., 22 табл., 15 источник, 4 прил.

Целью создания программного обеспечения является исследование результатов различных алгоритмов решения задачи коммивояжера.

Главным назначение программы является упрощение процесса исследования задач коммивояжера.

Объектом исследования является процесс решения задач коммивояжера.

Предметом исследования – алгоритмы задач коммивояжера.

Программа была разработана как программ­ное средство, предназначенное для исследования задач коммивояжера.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ. 8

1 ПОСТАНОВКА ЗАДАЧИ.. 10

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.1 Актуальность задачи. 15

3.2 Метод полного перебора. 16

3.3 Метод ближайшего соседа. 18

3.4 Улучшенный метод ближайшего соседа. 22

3.5 Метод ветвей и границ. 24

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.4 Гражданская оборона. 65

6.5 Безопасность жизнедеятельности. 68

ЗАКЛЮЧЕНИЕ. 73

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ.. 74

Приложение А ТЕХНИЧЕСКОЕ ЗАДАНИЕ. 76

Приложение Б РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ. 78

Приложение В ЛИСТИНГ. 79

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.