Алгоритмы и структуры данных вариант №7 Задача коммивояжёра.

В 1859 г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил детскую головоломку, в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара. Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере. Коммивояжер – не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами, как угодно. Задача о коммивояжере относится к классу NP-трудных задач. Методы решения задачи о коммивояжере различны. В данной курсовой кратко рассказывается только о некоторых наиболее известных. К эвристическим методам решения задачи коммивояжёра следует отнести «жадный» алгоритм, на каждом шаге выбирающий ребро наименьшей стоимости из множества рёбер, не нарушающих корректности решения. Эти методы имеют большую погрешность. Хорошо исследована область генетических алгоритмов, показавших свою эффективность для данной задачи, но они довольно громоздки. Метод перебора прост, но только лишь при небольшом количестве итераций. И наиболее удобным является метод ветвей и границ. Его можно применять и при большом количестве городов. Задача состоит в том, чтобы коммивояжер (торговец) обошел все намеченные города единожды и в таком порядке, чтобы его путь был наименьшим. Эта задача заинтересовала меня потому, что её решение интересно с точки зрения программирования и составления алгоритма. Важно нахождение такого алгоритма, который позволит наиболее оптимально решить задачу, что является актуальной задачей. Сейчас решение данной задачи необходимо во многих областях, связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий. Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место. Объектом курсовой работы является задача поиска оптимального пути. Предметом является методы оптимизации. Целью работы является практическое применение задачи коммивояжера. Для решения поставленной цели в работе решается ряд задач:  теоретическая информация, предназначенная для самостоятельного изучения;  практическая часть: индивидуальные задания на выбранную тему. Методы разработки: анализ, сравнение, наблюдение, синтез. Структурно работа состоит из введения, заключения, двух частей и списка использованных источников.

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:  маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;  в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды [6]. Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице диагональ заполнена нулями). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат. Для начала следует сказать, что в основе любого метода решения данной задачи лежит полный перебор всевозможных вариантов путей. Мы проходимся по каждому маршруту: одни отбрасываем, другие сравниваем с минимальным путем. В конце перебора получаем кратчайший путь. Особенностью этой задачи является то, что с увеличением количества городов растет общее число различных комбинаций прохождения пути. А вместе с тем растет и время расчета результата. Поэтому главным решением оптимизации алгоритма можно свести к тому, чтобы во время вычислений отбрасывать заведомо не минимальные пути. Необходимо задать такой критерий, который отсекал бы лишние ветви в дереве поиска кратчайшего пути [7]. Для пояснения моего варианта решения задачи следует ввести несколько понятий. Промежуточную длину пути можно определить следующим образом: представим, что торговец выбрал какой-либо путь; он вышел из первого города и сейчас находится в каком-то городе i . Тогда все пройденное расстояние из начала в город i будем называть промежуточная длина пути. Если исходить из того, что торговец в каждый момент времени будет находиться в каком-то i -ом городе, то всегда можно подсчитать какое расстояние он прошел из начала до этого города, то есть промежуточную длину пути [4]. Минимальным путем будем называть маршрут, проходящий по всем городам и имеющий минимальную длину.

Коммивояжер - это разъездной торговый агент какой-либо фирмы, предлагающий покупателям товары по образцам и каталогам. Его задача объездить все пункты назначения, не побывав ни в одном дважды и вернуться в точку старта [9]. Метод Литтла Целью данного метода является поиск гамильтонового цикла с минимальной стоимостью в графе. Что бы найти его, нужно придерживаться следующим действиям: 1. В каждой строке матрицы стоимости найдем минимальный элемент и вычтем его из всех элементов строки. Сделаем это и для столбцов, не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент. 2. Для каждого нулевого элемента матрицы, рассчитываем коэффициент k, который равен сумме минимальных элементов столбца и строки этого нуля. Выбираем нуль с максимальным коэффициентом (если таковых несколько выбираем любой из них). Вносим в гамильтонов контур соответствующую дугу. 3. Удаляем строку и столбец, на пересечении которого выбранный нами нуль. 4. Проверяем граф на наличие точек возврата, если есть таковые, то меняем их значение на максимальное. Повторяем предыдущие действия пока не останется матрица порядка 2. 5. Вносим в гамильтонов контур недостающие дуги. Получаем искомый цикл [11].

Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике. Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики (расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал. Существуют несколько методов решения задачи коммивояжера: метод полного перебора, «жадные» методы (Крускала, Прима, и т.п.), генетические алгоритмы и еще множество их обобщений. Однако только метод ветвей и границ дает нам в итоге самое оптимальное решение. В основе метода ветвей и границ лежит следующая идея если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Задача о коммивояжере имеет множество обобщений и методы её решения в различных проявлениях используются на практике. Задача коммивояжера является одной из самых важнейших задач в теории графов. Возможность представления (записи) различных производственных процессов на языке теории графов и умение решить сформулированную математическую задачу позволяют найти оптимальную стратегию ведения хозяйства, сэкономить ресурсы, выполнить поставленную задачу в более короткие сроки. Для решения оптимизационных и других задач строительства нередко прибегают к формулировке поставленной задачи в виде каких-то хорошо известных математических задач: транспортная задача, задача поиска оптимального пути (задача коммивояжера) и другие. Сформулированную таким образом задачу решают, используя такие математические методы, как метод ветвей и границ, симплексный метод, метод Литтла (приближенного решения), метод дефектов и другие методы. Подведем итог, после всех перечисленных шагов, получилась программа, позволяющая высчитать ответ, согласно решению задач «коммивояжера», все пункты были детально рассмотрены и выполнены, благодаря этому цель курсового проекта была достигнута.

1. Андрейчиков, А. В. Системный анализ и синтез стратегических решений в инноватике. Концептуальное проектирование инновационных систем / А.В. Андрейчиков, О.Н. Андрейчикова. - Москва: СИНТЕГ, 2019. - 432 c. 2. Анфилатов, В. С. Системный анализ в управлении / В.С. Анфилатов, А.А. Емельянов, А. А. Кукушкин. - М.: Финансы и статистика, 2017. - 368 c. 3. Байокки, К. Вариационные и квазивариционные неравенства. Приложения к задачам со свободной границей / К. Байокки, А. Капело. - М.: [не указано], 2019. - 195 c. 4. Бойко, В.В., Савинков, В.М. Проектирование баз данных информационных систем. – М.: Финансы и статистика, 2018. – 256с. 5. Бугорский, В. Н. Сетевая экономика / В.Н. Бугорский. - М.: Финансы и статистика, 2019. - 256 c. 6. Буч, Г. Введение в UML от создателей языка [Текст] / Г. Буч, Д. Рамбо, А. Джекобсон – М.: ДМК Пресс, 2015. – 496 c. 7. Гагарина, Л.Г. Разработка и эксплуатация автоматизированных информационных систем. Учебное пособие [Текст] / Л. Г. Гагарина – М.: Инфра–М, 2015. – 384 с. 8. Диментберг, Ф.М. Винтовое исчисление и его приложения в механике / Ф.М. Диментберг. - М.: [не указано], 2011. - 390 c. 9. Диязитдинова, А.Р. Управление разработкой информационных систем: Учебник [Текст] / А. Р. Диязитдинова, Н. В. Коныжева – Самара: ФГОБУ ПГУТИ, 2013. – 194 с. 10. Дылян, Г.Д. Модели управления процессами комплексной информатизации общего среднего образования / Г.Д. Дылян, Э.С. Ратобыльская, М.С. Цветкова. - М.: Бином. Лаборатория знаний, 2015. - 112 c. 11. Ерусалимский, Я.М. Дискретная математики: теория, задачи, приложения / Я.М. Ерусалимский. - М.: [не указано], 2018. - 622 c. 12. Заботина, Н. Н. Методы и средства проектирования информационных систем. Учебное пособие [Текст] / Н. Н. Заботина – М.: Инфра–М, 2020. – 331 с. 13. Заложнев, А. Ю. Информационные технологии маркетинга. Управление взаимоотношениями с клиентами / А.Ю. Заложнев, Е.Л. Шуремов. - М.: Бухгалтерия и Банки, 2018. - 152 c. 14. Зельдович, Я.Б. Высшая математика для начинающих и её приложения к физике / Я.Б. Зельдович. - М.: [не указано], 2013. - 941 c. 15. Иванова, В. В. Основы бизнес-информатики. Учебник / В.В. Иванова, Т.А. Лезина, А.А. Салтан. - М.: Издательство СПбГУ, 2018. - 244 c. 16. Кайнова, Е. Г. Информационные Технологии В Науке И Технике / Кайнова Елена Геннадиевна. - Москва: Наука, 2015. - 674 c. 17. Кайнова, Е. Г. Основы Научно-Технической Информации / Кайнова Елена Геннадиевна. - Москва: РГГУ, 2015. - 865 c. 18. Макаров, Н. С. UML: поддержка проектирования и инструментальные среды [Текст] / Н. С. Макаров – М.: Синергия, 2015. – 368 с. 19. Пантелеев, В.Н. Основы автоматизации производства: учеб. пособие для нач. проф. образования / В.Н. Пантелеев, В.М. Прошин. – М.: Академия, 2018. – 192 с. 20. Шишмарев, В.Ю. : учеб. пособие для студ. сред. проф. образования / В.Ю. Шишмарев. – М.: Академия, 2017. – 304 с.

-