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

В жизни очень часто надо решить такую задачу: требуется посетить несколько мест и оказаться в конечном пункте. Например, обойти несколько магазинов и вернуться домой. Разумеется, путь должен быть максимально коротким. Эта задача называется задачей Коммивояжера. Казалось бы, ничего сложного нет; если пунктов не много, то оптимальный путь обычно очевиден. А если пунктов 20 или 50? Если пути между ними не прямые линии, а учитывают дороги, рельеф местности, цены на транспорт? Тогда на помощь приходит компьютер. Сам по себе он никак не поможет. Да, современные процессоры выполняют миллиарды действий в секунду, но думать они еще не умеют. Им нужна программа, алгоритм действий. Даже самые умные и, на первый взгляд, «самообучаемые» программы работают по строго написанному алгоритму. Для решения задачи коммивояжера есть много различных алгоритмов. Здесь мы рассмотрим наиболее известные:

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

Полный перебор

Первый, самый очевидный способ найти оптимальный маршрут, — построить все маршруты и потом выбрать самый короткий (дешёвый, удобный). Сколько же придётся построить маршрутов? Число возможных маршрутов выражается как (N-1)!/2, где N - число вершин графа. Если для 10 вершин существует всего 181440 маршрутов, то для 20 вершин уже 60822550204416000 маршрутов. По времени выполнения: если существует машина, способная обработать 15 вершин за час, то для обработки 20 вершин ей потребуется 160 лет!. Как видим, время выполнения растет очень резко. Но этот алгоритм остается самым точным, хотя и подходит только для графов с небольшим количеством вершин.

Жадный алгоритм

Самое очевидное, как можно ускорить поиск, сначала брать самые короткие ребра.

Жадный алгоритм

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

Полюсный перебор

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

Полярный перебор

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

Полярный перебор

Для включения новой вершины в маршрут, ее надо “встроить” в ближайшее ребро так, чтобы длина маршрута увеличилась минимально.

Полярный перебор

Наибольшее влияние на общую длину маршрута оказывают вершины, наиболее отдаленные от остальных вершин графа. Назовем ихполюсами. Значит, для уменьшения количества обрабатываемых маршрутов можно сначала обработать полным перебором полюсы, а потом “встроить” остальные вершины графа. Для получения более точного результата полюсы можно делить на уровни. На первом уровне находятся наиболее приоритетные полюсы, которые оказывают наибольшее влияние на длину маршрута. На последующих уровнях приоритет полюсов уменьшается. В итоге все вершины графа становятся полюсами разного уровня. На первом уровне должно быть столько полюсов, сколько машина может обработать полным перебором за приемлемое время.
Для получения маршрута надо сначала построить полным перебором маршрут между полюсами первого уровня, а затем последовательно “встроить” вершины с остальных уровней. Чем выше уровень полюса, тем меньше он влияет на длину маршрута, поэтому добавлять его нужно позже. Таким образом получается, что наиболее важные вершины будут соединены наиболее оптимально.
На мой взгляд, это самый лучший из всех способов: он работает с достаточной точностью, а главное, дает легко балансировать точность и скорость увеличивая или уменьшая количество полюсов первого уровня. При этом расходуется минимальное количество памяти, в отличие от следующего метода.

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

Довольно сложный алгоритм, использующий много оперативной памяти, но с огромным потенциалом для модернизации.

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

  1. найти в исходном графе ребро деления, создать корень дерева
  2. найти наименьшую оценку среди листьев дерева
  3. найти ребро деления
  4. вычислить оценки для новых листьев
  5. прикрепить новые листья дерева к родительскому
  6. вернуться к п. 2, если маршрут еще не построен