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

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

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

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

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

 

 

 

Предположим, что бродячий торговец должен, покинув город, которому присвоим номер 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 копеек.