X Международная студенческая научная конференция Студенческий научный форум - 2018

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

Приведем классическую постановку задачи.Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3, ... ,n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к математическому виду, введём некоторые термины. Итак, города перенумерованы числами jТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j₁,j₂,..,jn,j₁), причём все j₁..jn – разные номера; повторяющийся в начале и в конце j₁,показывает, что перестановка зациклена. Расстояния между парами вершин С_ijобразуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

(1)

Относительно математизированной формулировки ЗК необходимо сделать два замечания.

Во-первых, в постановке С_ijозначали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jТ:

С_ij0; C_jj=∞ (2)

(последнее равенство означает запрет на петли в туре),

симметричными, т.е. для всех i,j:

С_ij= С_ji , (3)

и удовлетворять неравенству треугольника, т.е. для всех:

С_ij+ С_jkC_ik . (4)

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С_ij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому различают два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную – в противном случае.

Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j1,j2,..,jn,j1) и t’=(j1,jn,..,j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если Сij=0 и не проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную ЗК можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо “цикл” надо говорить “контур”, а вместо “ребра” ‒ “дуги” или “стрелки”.

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

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

Рис. 1. ‒ Сеть, представляющую узкий ромб, и найденный “жадным” алгоритмом тур

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию “иди в ближайший (в который еще не входил) город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 1, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

В пользу процедуры “иди в ближайший” можно сказать лишь то, что при старте из одного города она не уступит стратегии “иди в дальнейший”.

К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода.

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

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

Нахождение кратчайшего пути методом перебора. Классическим примером переборной задачи и служит задача коммивояжера. Пусть дано множество из N городов, расстояния между которыми известны. В каком порядке должен посетить их коммивояжер, заезжая в каждый город лишь один раз, чтобы общий пройденный путь был кратчайшим?

Опишем решение задачи методом перебора или “brute-force enumeration” ‒ “перебор животной силой”, как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что ЗК с N городами требует при полном переборе рассмотрения (N-1)!/2 туров в симметричной задаче и (N-1)! туров в несимметричной, а факториал, как показано в следующей таблице, растет удручающе быстро (табл. 1), однако быстродействие современных ПК позволяет справиться с этой задачей.

Таблица 1

5!	10!	15!	20!	25!	30!	35!	40!	45!	50!
~102	~106	~1012	~1018	~10125	~1032	~1040	~1047	~1056	~1064

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

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

Первое, что нужно сделать, решая задачу коммивояжера, это организовать генерацию перестановок. Занумеруем города числами от 1 до N. Все перестановки можно получить, выбирая из множества [2..N] один элемент всевозможными способами и присоединяя к нему поочередно перестановки и из оставшихся элементов. Это рекурсивный алгоритм, т.к. для построения перестановок из N элементов он нуждается в перестановках из N-1 элемента. Первый элемент в сгенерированной перестановке всегда 1, т.к. мы предполагаем, что автотранспортное предприятие расположено в нем и отсюда начинается маршрут. Последний элемент в перестановке также 1, потому что маршрут считается замкнутым – транспорт возвращается в город с номером 1. Добавим, что единственная перестановка из одного элемента – это сам элемент.

Реализуем алгоритм в среде Паскаль-ABC. Запрограммируем получение перестановок в виде рекурсивной процедуры.

Расчет проведен для следующей симметричной матрицы С_6х6 расстояний между городами.

Таблица 2

	1	2	3	4	5	6
1	∞	6	4	8	7	14
2	6	∞	7	11	7	10
3	4	7	∞	4	3	10
4	8	11	4	∞	5	11
5	7	7	3	5	∞	7
6	14	10	10	11	7	∞

Множество переставляемых элементов сделаем параметром процедуры. Другим параметром будет позиция перестановки, которая заполняется данным вызовом процедуры. Все перестановки будем поочередно строить во внешнем массиве из N целых чисел, за исключением числа 1.

Процедура Comm строит перестановки в массиве А. Перестановка готова, когда S=[]. Процедура дополнена подсчетом длины пути, заданного перестановкой, и выбором самого короткого из них. Для хранения кратчайшего из построенных маршрутов и его длины воспользуемся внешними переменными Аmin и Lmin. Расстояния между городами записаны в двумерном массиве Dist. Листинг программы приведен на рис. 2.

Рис. 2. ‒ Листинг в среде Паскаль-ABC программы нахождения замкнутого маршрута

с минимальной длиной пути

В результате решения по данной программе получен оптимальный замкнутый маршрут (рис. 3) движения коммивояжера: 1→2→6→5→4→3→1, длина пути которого составляет 6+10+7+5+4+4=36 условных единиц.

Рис. 3. ‒ Результаты решения задачи коммивояжера

Оптимальный замкнутый маршрут с минимальной длиной пути можно изобразить в виде следующего графа (рис. 4).

Рис. 4. ‒ Оптимальный замкнутый маршрут с минимальной длиной пути

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

Код для цитирования: Скопировать