Задача коммивояжера

СОДЕРЖАНИЕ:

ВВЕДЕНИЕ………………………………………………………………..2

1. ОСОБЕННОСТИ РЕШЕНИЯ ЗАДАЧ КОМИВОЯЖЕРА………….3

1. Задача коммивояжера: сущность и применение на практике…3
2. Методы решения задачи коммивояжера………………………...6

2. ЭВРИСТИЧЕСКИЕ МЕТОДЫ………………………………………..9
1. Алгоритм Борувки………………………………………………..11
2. Алгоритм Крускала………………………………………………11
3. Алгоритм Прима………………………………………………….12
4. Вывод………………………………………………………………12

3. МЕТОД ВЕТВЕЙ И ГРАНИЦ……………………………………….13

4. Заключение……………………………………………………………19

5. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………….20

ВВЕДЕНИЕ

Комбинаторика раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбина-торных конфигураций. Это изучение включает в себя вопросы существования комбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задач перечисления, в частности определение числа конфигураций данного класса. Простейшим примером комбинаторных конфигураций являются перестановки, сочетания и размещения. Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем диссертация Комбинаторное искусство , Я. Бернулли работа Искусство предположений , Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейбница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций методу производящих функций.

Возвращение интереса к комбинаторному анализу относится к 50-м годам  ХХ в. в связи с бурным развитием  кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался  интерес к классическим комбинаторным  задачам. Классические комбинаторные  задачи это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую  формулировку развлекательного содержания типа головоломок.

В 1859 г. У. Гамильтон придумал игру Кругосветное путешествие , состоящую  в отыскании такого пути, проходящего  через все вершины города, пункты назначения графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами. Задача  о гамильтоновых циклах в графе  получила различные обобщения.

Одно из этих обобщений  – задача коммивояжера, имеющая  ряд применений в исследовании операций, в частности при решении некоторых  транспортных проблем. Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере. Коммивояжер – не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами как угодно.

Задача коммивояжера (ЗК), известная также как задача о сверлильном станке или алгоритм коммивояжера была поставлена в 1934 году. Эта задача является одной из знаменитых задач теории комбинаторики и широко применяется при разработке программного обеспечения.

1. ОСОБЕННОСТИ РЕШЕНИЯ  ЗАДАЧИ КОММИВОЯЖЕРА

1. Задача коммивояжера: сущность и применение на практике

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

      Задача  коммивояжера является типичной  задачей оптимизации, которая  широко применяется при разработке  программного обеспечения. Задача  о коммивояжере является упрощенной  моделью для многих других  задач дискретной оптимизации,  а также часто является подзадачей. В своей области (оптимизации  дискретных задач) она служит  своеобразным катализатором, стимулирующим  разработку наиболее эффективных  методов, алгоритмов и способов  их машинной реализации.

      Задача  коммивояжера формулируется очень  просто: на плоскости (в пространстве) расположены N городов, заданы  расстояния между каждой парой  городов. Требуется найти маршрут  минимальной длины с посещением  каждого города ровно один  раз и с возвращением в исходную точку.

     В задаче  коммивояжера целевой функцией, которую надо минимизировать, является  стоимость обхода.

      Особенностью  задачи о коммивояжере является  необходимость  дополнительно  учитывать расстояния от города  до города, которые предполагаются  известными. Эти «расстояния» можно  заменить на количество затраченного  времени, стоимость проезда или  предполагать другие произвольные  значения. В общем случае мы  даже не предполагаем, что стоимость  проезда из I в J обязательно совпадает  со стоимостью обратного проезда  из I в J. Данная задача соединяет  в себе простоту условия и  сложность решения, обусловленную  большими размерами поискового пространства.

      На  графах  задача формулируется следующим   образом: требуется найти гамильтонов   цикл наименьшей стоимости во  взвешенном полном графе. Т.е.  выйдя из стартовой вершины,  посетить каждую вершину графа  ровно один раз и вернуться  в начальную по кратчайшему  пути.

      Гамильтонов  путь (или гамильтонова цепь) –  путь (цепь), содержащий каждую вершину  графа ровно один раз. Гамильтонов  путь, начальная и конечная вершины  которого совпадают, называется гамильтоновым циклом.

      Гамильтоновы  путь, цикл и граф названы в  честь  ирландского математика  У. Гамильтона, который впервые  определил эти  классы, исследовав  задачу «кругосветного путешествия»  по додекаэдру, узловые вершины  которого символизировали крупнейшие  города Земли, а ребра – соединяющие их дороги.

       Существует  несколько частных случаев общей постановки задачи, в частности:

• геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости);
• треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника);
• симметричная и асимметричная задачи коммивояжёра.

      Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.

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

       При постановке задачи коммивояжера для  k коммивояжеров на множестве из n+1 городов строится k замкнутых маршрутов по следующим правилам:

один из городов, называемый базой входит во все маршруты;

каждый из городов, исключая базу входит в ровно один из маршрутов;

суммарная длина всех маршрутов минимальна.

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

Разбивается ли задача достаточно хорошо на совокупность более мелких подзадач?

Существует ли точная, непротиворечивая информация о задаче?

Ожидается ли, что в процессе решения задачи человек будет  взаимодействовать с вычислительной машиной?

       Задача  коммивояжера имеет ряд практических применений.

       Как правило, речь идет либо о простом перемещением по заданным точкам, либо с развозом груза небольшого формата или веса на транспортном средстве, вмещающем большое количество единиц, что создает предпосылки для применения задачи коммивояжера. Примером реализации задачи на практике является составление оптимального маршрута человека для доставки продуктов в магазины с оптового склада; доставки бутилированной воды; обновления программных продуктов автоматизированного учета на предприятии; пополнения банкоматов наличными деньгами; сбора сотрудников для доставки вахтовым методом; расклейки афиш; сбора наличных денежных средств их терминалов и др. В этом случае вершинами являются места установки терминалов (банкоматов и т.д.) и «базовый пункт». Стоимостью каждого ребра (отрезка маршрута) является время в пути между двумя точками (вершинами) на маршруте.

      Еще одно применение задачи коммивояжера – это задача о сверлильном станке. Данное применение задачи является сугубо специализированным приложением, которое заключается в оптимизации движений сверлильного станка ЧПУ для создания большого количества нерегулярно расположенных отверстий или сварочного робота. Сверлильный станок изготавливает металлические листы с некоторым количеством отверстий. Координаты отверстий известны. Необходимо найти кратчайший путь через все отверстия, а значит, и наименьшее время, затрачиваемое на изготовление одной детали. В данном случае, если такой станок делает миллион деталей в год, то даже миллиметровая выгода может сэкономить приличные средства. Этим объясняется стремление развитых стран затрачивать огромные финансовые ресурсы на инвестиции в информационные технологии.

       Внимание  исследователей к этой задаче привлекает благодаря: большому количеству практических задач, которые к ней сводятся; сосредоточению характерных математических, алгоритмических вычислительных сложностей; простоте и прозрачности формулирования. 

1.2 Методы решения задачи  коммивояжера.

       Задачи  коммивояжера решаются посредством различных методов, выведенных в результате теоретических исследований. Все эффективные методы (сокращающие полный перебор) — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение.

 Выделяют  следующие  группы методов решения задач  коммивояжера, которые относят к  простейшим:

      Полный  перебор (или метод «грубой силы») — метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

Случайный перебор;

      Обычно  выбор решения можно представить  последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать «рекорд», т. е. наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.

Жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешевого включения);

      Жадный  алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. При решении задачи коммивояжера жадный алгоритм превратится в стратегию «иди в ближайший (в который еще не входил) город».

К эвристическим методам  решения задачи коммивояжёра следует  отнести «жадный» алгоритм, на каждом шаге выбирающий ребро наименьшей стоимости  из множества рёбер, не нарушающих корректности решения. Эти методы имеют большую  погрешность. Хорошо исследована область  генетических алгоритмов, показавших свою эффективность для данной задачи, но они довольно громоздки. Метод  перебора прост, но только лишь при  небольшом количестве итераций.

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

Предположим, что бродячий торговец должен, покинув город, которому присвоим номер 1, объехать еще N – 1 городов  и вернутся снова в город номер 1. В его распоряжении есть дороги, соединяющие эти города. Он должен выбрать свой маршрут – порядок  посещения городов так, чтобы  путь, который ему придется пройти, был как можно короче. Основное условие этой задачи состоит в  том, что коммивояжер не имеет  права возвращаться снова в этот город, в котором он однажды уже  побывал. Это условие будем называть условием (α). Мы считаем, что расстояние между двумя городами – функция f(xi, xj) – определено. Разумеется, функция f(xi, xj) может означать не только расстояние, но, например, время или издержки в пути и т.д. поэтому в общем  случае

f(xi, xj) ≠ f(xj, xi),

а функции f(xi, xi) естественно  приписать значение ∞. Длина l пути S определяется формулой:

Сумма в выражении (1) распространена по всем индексам i и j, удовлетворяющим  условию (α), т.е. условию, что каждый из индексов i и j входит в выражение (1) один и только один раз. Функция l = l(x1, …, xN) является, таким образом, аддитивной – она представима в виде суммы  слагаемых, однако сама задача – задача отыскания минимума l – в силу ограничения (α) не является аддитивной и не удовлетворяет принципу оптимальности.

Рассмотрим снова плоскость t, x, где t – дискретный аргумент, принимающий  значения 0,1, 2, …, N, соответствующие  этапам путешествия торговца. Значит t = 0 соответствует его начальному положению в городе номер 1, t = 1 –  переходу из города номер 1 в город, который он выбрал первым для посещения, и т.д., t = N означает последний этап его путешествия – возвращение  в город номер 1. Аргумент x теперь также принимает дискретные значения 1,2, …, N (Рисунок 1.1). Соединим точку (0, 1) с точками (1,1), (1, 2), …(1, N) и длинам отрезков, соединяющих эти точки, припишем значения f(x1,xj). Далее точки (1, s) – узлы, лежащие на первой вертикали, мы соединим со всеми уздами второй вертикали, длинам отрезков мы припишем значения f(xs, xk) и т.д. точки (N-1, s) соединим с точкой (N,1).

(1.1)

В результате мы построили  некоторый граф, каждая ломанная которого, соединяющая точку (0,1) сточкой (N,1), описывает  путь коммивояжера. Нашу задачу мы можем  теперь сформулировать следующим образом. Среди всех ломанных, принадлежащих  этому графу и соединяющих  точки (0,1) и (N,1) и удовлетворяющих условию (α), найти ломанную кратчайшей длины. Условие (α) состоит теперь в том, что искомая ломанная пересекает (в узле) каждую из прямых x = i один и только один раз. Таким образом, задача о коммивояжере формулируется более привычным для нас языком.

Рассмотрим узел P, лежащий  на третьей вертикали (Рисунок 1.2). Если бы условие (α) отсутствовало, то выбор  траектории, которая соединяет точку P с точкой (N, 1), не зависел бы от того пути, который привел нас в точку P. В данном случае ситуация иная, и  если два коммивояжера находятся  в точке P, но один из них пришел в  это состояние, двигаясь вдоль траектории, проходящей через точку Q, а второй через точку R, то их состояния существенно  отличаются друг от друга.

Коммивояжер, который двигался по второй траектории , уже побывал  в городах номер 2 и номер 5 и  в будущем он уже не имеет права  снова заезжать в эти города. Что  касается коммивояжера, который двигался вдоль первой траектории, то он побывал  в городах номер 3 и номер 6; он не имеет права возвращаться в  эти города, но зато он еще обязан посетить города номер 2 и номер 5 и т. д.

Поскольку функция f(xi, xj) определена на конечном множестве точек, то и  функция l(х1,…,xN) также определена на конечном множестве точек.

Следовательно, задача определения  минимума функции l сводится к перебору некоторого конечного множества  значений этой функции, и проблема носит  чисто вычислительный характер. Однако именно вычислительные трудности здесь  огромны.

Легко подсчитать, что число  возможных вариантов (число значений функции l) равно (N — 1)!. Таким образом, непосредственно перебрать и  сравнить между собой все возможные  пути, по которым может следовать  бродячий торговец, для достаточно большого количества городов практически  невозможно.

Возникает проблема построения такого метода последовательного анализа  вариантов, который выделял бы по возможности большое количество неперспективных вариантов и  сводил задачу к перебору относительно небольшого количества «подозрительных» вариантов.

2. ЭВРИСТИЧЕСКИЕ МЕТОДЫ

Решить задачу коммивояжера можно с помощью алгоритма  Крускала. Также нам могут помочь алгоритмы Борувки и Прима, так  называемые «жадные алгоритмы» Эти  методы ускоряют разработку алгоритма  по сравнению с методом полного перебора, однако не всегда дают оптимальное решение. Но немного расскажем о них.

Итак, имеется n городов, которые  нужно обойти. Для этого достаточно проложить (n-1) путей между городами. Как соединить города так, чтобы  суммарная стоимость путешествия  была минимальна?

В общем случае, задачу можно  сформулировать так. Пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V — множество  вершин (городов), а E — множество  их возможных попарных соединений (дороги). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или  стоимость пути). W(u,v) называется весовой  функцией. Задача состоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.

Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом. Остовное дерево T, у которого суммарный  вес его ребер w(T) = ∑_(u,v)∈T^w(u,v) минимален, называется минимальным остовным или минимальным покрывающим деревом.

Так как рассматриваются  только деревья, можно считать все  ребра положительными (достаточно добавить к весу всех ребер некоторую относительно большую положительную константу). В противном случае, если стоимость  соединения между двумя вершинами  равна отрицательному числу, можно  несколько раз параллельно соединить  их для уменьшения суммарного веса остовного подграфа.

Также считаем, что для  любой пары ребер их весовые характеристики будут различны. Это гарантирует  уникальность построенного минимального остовного дерева. Для примера, если все ребра имеют единичный  вес, то любое остовное дерево будет  минимальным (с суммарным весом v-1, где v – количество вершин в графе).

Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G, который  называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое  ребро e=(u,v) выбирается так, чтобы не нарушить этого свойства: A ∪ {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.

По определению A, он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит  в том, как искать безопасное ребро. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A – одна компонента). Таким образом анализ графа выполняется (n-1) раз.

Далее приводится общее правило  отыскания безопасных ребер. Для  этого есть теорема, которая поможет  находить безопасные ребра.

Теорема: Пусть G(V;E) – связный  неориентированный граф и на множестве  Е определена весовая функция w. Пусть  А – некоторый подграф G, являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E(K) ребер графа G, только один конец которых лежит в К. Тогда  ребро минимального веса из E(K) будет  безопасным.

В связи с приведенной  теоремой введем следующее: безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро  с минимальным весом, ровно один конец которого лежит в К.

2.1. Алгоритм Борувки

На первом шаге A состоит  из всех вершин G и пустого множества  ребер. В начале очередной фазы алгоритма  Борувки, для каждой компоненты связности  промежуточного остовного леса выбирается лидер или корень – вершина, сопоставляемая каждой компоненте. Сделать это можно  в простейшем случае с помощью  обхода A в глубину: вершина, с которой  начинается обход очередной компоненты, и будет ее лидером.

После того, как лидеры выбраны, для каждой компоненты связности  находится безопасное для нее  ребро, по существу методом грубой силы. Как только все такие ребра  отобраны, они добавляются к A. Процесс  продолжается до тех пор, пока в A присутствует больше одной компоненты связности.

2.2. Алгоритм Крускала

Алгоритм Крускала объединяет вершины графа в несколько  связных компонент, каждая из которых  является деревом. На каждом шаге из всех ребер, соединяющих вершины из различных  компонент связности, выбирается ребро  с наименьшим весом. Необходимо проверить, что оно является безопасным. Безопасность ребра гарантируется ранее показанной теоремой о безопасных ребрах. Так  как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным.

Остается понять, как реализовать  выбор безопасного ребра на каждом шаге. Для этого в алгоритме  Крускала все ребра графа G перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы  ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются.

Удобно использовать для  хранения компонент структуры данных для непересекающихся множеств, как, например, списки или, что лучше, лес  непересекающихся множеств со сжатием  путей и объединением по рангу (один из самых быстрых известных методов). Элементами множеств являются вершины  графа, каждое множество содержит вершины  одной связной компоненты.

2.3. Алгоритм Прима.

Как и алгоритм Крускала, алгоритм Прима следует общей  схеме алгоритма построения минимального остовного дерева: на каждом шаге мы добавляем к строящемуся остову безопасное ребро. Алгоритм Прима относится  к группе алгоритмов наращивания  минимального остова: на каждом шаге существует не более одной нетривиальной (не состоящей из одной вершины) компоненты связности, и каждый к ней добавляется  ребро наименьшего веса, соединяющее  вершины компоненты с остальными вершинами. По теореме такое ребро  является безопасным.

При реализации надо уметь  на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться  очередью с приоритетами (кучей). Алгоритм получает на вход граф G и его корень r – вершина, на которой будет  наращиваться минимальный остов. Все  вершины G, еще не попавшие в дерево, хранятся в очереди с приоритетом  Ω. Приоритет вершины v определяется значением key[v], которое равно минимальному весу ребер, соединяющих v с вершинами  минимального остова. Поле p[v] для вершин дерева указывает на родителя, а  для вершин из очереди, указывает  на остов дерева, в которою ведет  ребро с весом key[v] (одно из таких  ребер, если их несколько).

2.4. Вывод

Рассмотрим небольшую  «детскую» задачу. Допустим, что  у нас есть монеты достоинством 25, 10, 5 копеек и 1 копейка и нужно  вернуть сдачу 63 копейки. Почти не раздумывая, мы преобразуем эту величину в две монеты по 25 копеек, одну монету в 10 копеек и три монеты по одной  копейке. Нам не только удалось быстро определить перечень монет неясного достоинства, но и, по сути, мы составили самый короткий список монет требуемого достоинства.

Алгоритм, которым мы в  этом случае воспользовались, заключался в выборе монеты самого большого достоинства (25 копеек), но не больще 63 копеек, добавлению ее в список сдачи и вычитанию  ее стоимости из 63 (получается 38 копеек). Затем снова выбираем монету самого больщого достоинства, но не больще остатка (38 копеек): этой монетой опять оказывается  монета в 25 копеек. Эту монету мы опять  добавляем в список сдачи, вычитаем ее стоимость из остатка и т.д.

Этот метод внесения изменений  называется «жадным» алгоритмом. На каждой отдельной стадии «жадный» алгоритм выбирает тот вариант, который является локально оптимальным в том или  ином смысле. Обратите внимание, что  алгоритм для определения сдачи  обеспечивает в целом оптимальное  рещение лищь вследствие особых свойств  монет. Если бы у нас были монеты достоинством 1 копейка, 5 и 11 копеек и  нужно было бы дать сдачу 15 копеек, то «жадный» алгоритм выбрал бы сначала  монету достоинством 11 копеек, а затем  четыре монеты по одной копейке, т.е. всего пять монет. Однако в данном случае можно было бы обойтись тремя  монетами по 5 копеек.