Большинство задач дискретной оптимизации являются NP-трудными. Это значит, что в общем виде нет аналитического метода решения таких задач, а количество вариантов перебора растёт как экспонента от размерности задачи.

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

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

 Эта задача формулируется очень просто, однако, к сожалению, никто не знает точного метода её решения.

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

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

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

Задачи коммивояжера небольшой размерности можно решать на компьютере. Для этого нужно в поисковой строке google набрать запрос «задача коммивояжера онлайн». Например, сервис  позволяет решать онлайн задачи с количеством пунктов до 14. Этого вполне достаточно для курьера, составляющего план доставки товаров в течение дня.

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

Пусть турист, находящийся во Львове, хочет совершить турне по таким городам: Братислава, Будапешт, Вена, Краков, Прага.

Чтобы решить такую задачу, нужно предварительно подготовить исходные данные – узнать расстояния по автодорогам между всеми городами. Это можно сделать, например, при помощи сервиса www.della.ua/distance.

В сервисе https://math.semestr.ru/kom/index.php выберем количество пунктов – 7, перенесём данные в появившуюся таблицу и нажимаем клавишу «далее».

В окне появляется линейка прокрутки с ходом решения, нас интересуют только выводы (в конце). Они такие:

В результате по дереву ветвлений гамильтонов цикл образуют рёбра:
(1,5), (5,6), (6,4), (4,2), (2,3), (3,1). 
Длина маршрута равна F(Mk) = 2039.
Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера.

Переходя от цифр к названиям городов, получаем оптимальный маршрут Львов–Краков–Прага–Вена–Братислава–Будапешт–Львов, длина которого равна 2039 км. Поскольку матрица расстояний симметрична (т.е. d(i,j) = d(j,i)), то маршрут, пройденный в обратном направлении, будет иметь такую же длину.

Оказывается, решая задачу коммивояжера, можно уменьшать не только пройденное расстояние, но и время, затрачиваемое на последовательность операций. Здесь можно вспомнить о двух значениях английского слова «way». Первое – это путь, дорога. Второе – это способ сделать что-нибудь.

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

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

Например, пусть на кухонном комбайне нужно выполнить две операции: 1) выжать яблочный сок, 2) измельчить лук для котлет. Заметим, что в этом случае следует выбрать последовательность действий яблоки–лук.

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

После окончания двух операций нужно будет помыть комбайн. Но, если выбрать последовательность действий лук–яблоки, то комбайн придётся мыть дважды – вряд ли кто-то захочет пить яблочный сок с лучным привкусом.

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

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

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

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

Для каждого куска зададим координаты начала и конца, как если бы этот кусок вырезался с самого начала рулона.

Пусть требуется вырезать шесть таких кусков:

0-6, 2-8, 4-12, 7-12, 8-11, 9-16 (в дециметрах).

Назовём первым пунктом начало/конец операции раскройки, вторым – 1-й кусок, и т.д., седьмым – 6-й кусок:

Назовём расстоянием между пунктами i и j ширину куска (в дециметрах), которую придётся вырезать и пустить в отходы при переходе от i-го пункта к j-му. Например, d(2,3) = 6, поскольку 2-й пункт заканчивается на отметке 6 дм, а 3-й начинается на 2 дм, следовательно, его надо выбирать уже на следующем метре рулона.

Между ними лежит полоса шириной 6 дм. В то же время d(3,2) = 2, поскольку 3-й пункт заканчивается на отметке 8 дм, а 2-й начинается на 0 дм на следующем метре. Здесь, как и в задаче переналадки, может нарушаться аксиома метрики.

Расстояние от 1-го пункта до всех остальных равно координате левого края соответствующего куска (например, d(1,3) = 2), а расстояние от всех пунктов до 1-го положим равным нулю (когда уже вырезаны все куски, то переходим в состояние «конец раскройки», при этом ничего не вырезаем, отходы равны нулю).  

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

В окне появляется линейка прокрутки с ходом решения, нас интересуют только выводы (в конце). Они такие:

В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,2), (2,7), (7,5), (5,4), (4,3), (3,6), (6,1) 
Длина маршрута равна F(Mk) = 6.
Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера

Значит, при оптимальной раскройке отходы составят всего 60 см.

На основании полученного решения задачи коммивояжера составим план раскройки рулона. Он будет таким:

кусок 2 - отх. 30 см - кусок 7 - отх. 10 см - кусок 5 - отх. 20 см- кусок 4 - кусок 3 - кусок 6.

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

С.И. Доценко, кандидат физико-математических наук, старший научный сотрудник факультета компьютерных наук и кибернетики КНУ имени Тараса Шевченко

По теме: