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

2.1. Описание задачи коммивояжера и ее формулировка в виде целочисленной задачи линейного программирования были даны в § 3 гл. 2; в § 3 гл. 10 излагался метод ветвей и границ для ее решения. В этом параграфе мыприведем другой алгоритм, основанный на идеях динамического программирования и предложенный одновременно и независимо Беллманом [54] и Хелдом и Карпом [94].

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

чисел минимизирующую суммарный пройденный путь

(Ясно, что в силу замкнутости искомого цикла безразлично, какой город считать начальным; поэтому в качестве начального фиксирован город 0.)

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

Обозначим через

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

Перестановку городов на которой реализуется фигурирующий в определении (2.2) кратчайший путь, обозначим через

Излагаемый ниже алгоритм основан на следующей простой теореме.

Теорема 2.1. Пусть

и Тогда

Доказательство непосредственно следует из определений (2.2) и (2.3).

2.3. Перейдем непосредственно к изложению алгоритма.

Шаг 0. Вычисляем функцию

Количество значений функции подлежащих вычислению, есть

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

Шаг 1. Вычисляем функцию

По окончании вычеркиваем из памяти таблицу значений

Количество значений функции подлежащих вычислению, равно

На одно значение функции требуются три действия (два выбора из таблицы и одно сложение). Необходимый объем памяти вычеркивания из памяти таблицы

Шаг Вычисляем функцию

для всех значений при :

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

Количество значений функции подлежащих вычислению, равно

На одно значение функции требуется действий (2k выборов из таблицы, 4 сложений, сравнений). Необходимый объем памяти вычеркивания из памяти таблиц составляет

Шаг . Вычисляем функцию

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

Количество значений функции подлежащих вычислению, равно здесь

На одно значение функции требуется действий выборов из таблицы, сложений, сравнений). Необходимый объем памяти

2.4. Получим теперь выражение для суммарного объема необходимых вычислений Прежде всего

где количество значений функции подлежащих вычислению, а

— количество операций, приходящихся на одно значение. Находим:

При всех имеем

Таким образом,

Преобразуем теперь последнюю сумму в выражении для Обозначим

Тогда

откуда

Окончательно имеем

Отметим, что полный перебор составляет т. е. существенно больше

2.5. Получим выражение для максимального потребного объема памяти Имеем

Но

так что

где - целая часть от

Отдельно рассмотрим два случая.

I случай.

II случай.

Но (см. I случай)

так что

Итак, в обоих случаях

В конечном счете удалось (по сравнению с полным перебором, для которого достигнуть существенного сокращения объема вычислений за счет заметного увеличения объема памяти.