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

Наверное только ленивый не слышал о задаче коммивояжера. Но в чем ее суть и почему об этой задаче так часто говорят в теории алгоритмов? А суть в том, что нужно обойти все пункты по кратчайшему маршруту, при этом, не заходя ни в один из пунктов дважды.  Казалось бы, что особенного в этой задаче? Давайте предположим, что у нас всего три точки 1,2 и 3. Какие у нас есть маршруты? Очевидно, шесть маршрутов:

1. Сначала 1, потом 2, потом 3.
2. Сначала 1, потом 3, потом 2.
3. Сначала 2, потом 1, потом 3.
4. Сначала 2, потом 3, потом 1.
5. Сначала 3, потом 1, потом 2.
6. Сначала 3, потом 2, потом 1.

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

Если у нас немного точек, то мы сможем перебрать все варианты. Но в реальной жизни объектом может быть гораздо больше. А с увеличением количества пунктов количество вариантов резко возрастает. Например, факториал от 10 это 3 628 800. А 20!=2 432 902 008 176 640 000. Это порядка десяти в восемнадцатой степени. Тактовая частота современных процессоров порядка нескольких гигагерц (десять в степени девять). Даже если мы будем на каждый вариант тратить один такт процессорного времени (что уже невозможно, на самом деле на одну итерацию придется потратить очень много тактов), то это уже займет порядка миллиарда секунд. Это примерно тридцать лет. А если точек будет еще больше, например 30, или даже 40, то на перебор всех вариантов не хватит времени существования Вселенной.

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

Уже при 11 элементах алгоритм полного перебора падает в исключение «переполнение стека». Ясно, что это не метод решения. Как же тогда быть? Как вариант, можно использовать жадный алгоритм. В чем его суть? Сначала берем первую попавшуюся точку. Затем ищем ближайшую к ней. Проводим в нее ребро, и ищем следующую ближайшую точку. И так пока не обойдем все точки. Разумеется, никто не гарантирует, что это будет самый короткий путь. Но он будет достаточно коротким. Вот например, как сработает алгоритм для 11 случайных точек:

А как программа справиться с большим количеством точек? Например, 30?

А если 100?

Согласитесь, вполне даже неплохо справляется, несмотря на то, что жадные алгоритмы – наиболее простая идя решения задачи коммивояжера.  Какие есть еще способы? В частности, другие наиболее простые методы это:

• Случайный перебор.
• Метод минимального остовного дерева.
• Метод имитации отжига.

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

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

Еще для решения задачи коммивояжера можно применить разные эвристические алгоритмы, например, муравьиный алгоритм, генетический алгоритм, методы динамического программирования.