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

Очевидно, что сформулированная выше задача (1) является частным случаем задачи (2). В самом деле, приписывая случайным образом дугам заданного ориентированного графа G конечные веса, получаем задачу коммивояжера. Если решение для этой задачи, т.е. кратчайший гамильтонов цикл, имеет конечное значение, то это решение является гамильтоновым циклом ориентированного графа G (т.е. ответом на задачу 1). Если же решение имеет бесконечное значение, то G не имеет гамильтонова цикла.

С другой стороны можно дать еще одну интерпретацию задачи 1). Рассмотрим снова полный ориетированный граф G1 с общей матрицей весов дуг [cij] и рассмотрим задачу нахождения такого гамильтонова цикла, в котором самая длинная дуга минимальна. Эту задачу можно назвать минимаксной задачей коммивояжера. Тогда классическую задачу коммивояжера в той же терминологии можно было бы назвать минисуммной задачей коммивояжера. Покажем теперь, что задача (1) действительно эквивалентна минимаксной задаче коммивояжера.

В вышеупомянутом полном ориентированном графе G1 мы можем наверняка найти гамильтонов цикл. Пусть это будет цикл Ф1, и пусть вес самой длинной его дуги равен ĉ1. Удалив из G1 любую дугу, вес которой не меньше ĉ1, получим ориентированный граф G2. Найдем в ориентированном графе G2 гамильтонов цикл Ф2, и пусть вес его самой длинной дуги равен ĉ2. Удалим из G2 любую дугу, вес которой не меньше ĉ2, и так будем продолжать до тех пор, пока не получим ориентированный граф Gm+1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фm в Gm (с весом ĉm) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Gm+1 следует, что в G1 не существует никакого гамильтонова цикла, не использующего по крайней мере одну дугу с весом, большим или равным ĉm.

Таким образом, алгоритм нахождения гамильтонова цикла в ориентированном графе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном ориентированном графе G может быть найден с помощью построения полного ориентированного графа G1 с тем же самым множеством вершин, что и в G, дугам которого, соответствующим дугам из G, приписаны единичные веса, а остальным дугам — бесконечные веса. Если решение минимаксной задачи коммивояжера для G1 имеет конечный вес (на самом деле равный единице), то в графе G может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе G не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот.

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

§4. Методы построения гамильтоновых циклов в графе.

Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G гамильтонов цикл. Критерии существования, данные выше, представляют теоретический интерес, но являются слишком общими и не пригодны для произвольных графов, встречающихся на практике. Алгебраические методы определения гаильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера. Более приемлемым является способ Робертса и Флореса, который не предъявляет чрезмерных требований к памяти компьютера, но время в котором зависит экспоненциально от числа вершин в графе. Однако другой неявный метод перебора имеет для большинства типов графов очень небольшой показатель роста времени вычислений в зависимости от числа вершин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах. Ниже будут описаны алгебраический метод, перебор с возвратами, его улучшение, мультицепной метод.

§5. Алгебраический метод построения гамильтоновых циклов

Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи x1, x2, … ,xk-1, xk определяется как выражение вида x2*x3* …xk-1, не содержащее две концевые вершины x1 и xk. «Модифицированная матрица смежности» B=[β(i,j)] — это (n×n)- матрица, в которой β(i,j) — xj, если существует дуга из xi в xj и нуль в противном случае. Предположим теперь, что у нас есть матрица PL = [pL(i ,j)], где pL(i,j) — сумма внутренних произведений всех простых цепей длины L (L≥1) между вершинами xi и xj для xi≠xj. Положим pL(i,i)=0 для всех i. Обычное алгебраическое произведение матриц B*PL = P’L+1 = [p’L+1(s,t)] определяется как т.е. p’L+1(s,t) является суммой внутренних произведений всех цепей из xs в xt длины l+1. Так как все цепи из xk в xt, представленные внутренними произведениями из pL(k,t), являются простыми, то среди цепей, получающихся из указанного выражения, не являются простыми лишь те, внутренние произведения которых в pL(k,t) содержат вершину xs. Таким образом, если из p’L+1(s,t) исключить все слагаемые, содержащие xs (а это можно сделать простой проверкой), то получим pL+1(s,t). Матрица PL+1=[pL+1(s,t)], все диагональные элементы которой равны 0, является тогда матрицей всех простых цепей длины L+1.

Вычисляя затем B*PL+1, находим PL+2 и т.д., пока не будет построена матрица Pn-1, дающая все гамильтоновы цепи (имеющие длину n-1) между всеми парами вершин. Гамильтоновы циклы получаются тогда сразу из цепей в Pn-1 и тех дуг из G, которые соединяют начальную и конечную вершины каждой цепи. С другой стороны, гамильтоновы циклы даются членами внутреннего произведения вершин, стоящими в любой диагональной ячейке матрицы B*Pn-1 (все диагональные элементы этой матрицы одинаковые).