Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
3.7.2. Решение задачи коммивояжера методом динамического программирования
В основе метода динамического программирования лежит простая идея осуществления сравнения различных вариантов допустимых решений задачи (по значению целевой функции) не в конце построения множества всех возможных вариантов, а на каждом шаге построения возможных вариантов [16], [35]. Применительно к задаче коммивояжера содержание работы алгоритма на 
-ом шаге, 
состоит в том, что имеющиеся пути коммивояжера “длины ” (т.е. проходящие через вершин) удлиняем на единицу, т.е. получаем пути, проходящие через 
вершин.
Пусть нам задан 
-вершинный граф 
, в котором вершины перенумерованы индексом 
; 
, 
, 
– матрица длин, т.е. весов 
дуг 
. Так как искомый гамильтонов контур есть замкнутый путь, то, не умаляя общности, можно считать, что начальной является вершина 0.
Пусть дан оптимальный путь коммивояжера 
. Рассмотрим в 
отрезок пути, начинающийся в 0 и заканчивающийся вершиной 
: 
; этот путь содержит промежуточных вершин. Очевидно, что так как – минимальный гамильтонов контур, то его часть 
, соединяющая вершины 0 и 
и проходящая в некотором порядке через вершины 
должна иметь минимальную длину. Введем обозначение
(3.29)
– длина пути минимальной длины, соединяющего вершины 0 и и проходящего один и только один раз через каждую из вершин 
.
В обозначениях (3.29) общий принцип оптимальности в теории динамического программирования [16] применительно к задаче коммивояжера имеет следующий вид:
(3.30)
Здесь уместно напомнить, что функция (3.29) симметрична по аргументам 
, т.е. не изменяется при любой их перестановке.
Перейдем непосредственно к изложению алгоритма.
Шаг 0. Вычисляем функцию
, 
, если дуга 
,(3.31)
Æ – пустое множество. Запоминаем все 
значений этой функции.
Шаг 1. Вычисляем функцию
(3.32)
, 
.
Запоминаем все 
значений функции (3.32), после чего вычеркиваем из памяти таблицу значений функции (3.31).
Шаг (
). Для всех 
и всех 
наборов 
вычисляем функцию 
по формуле (3.30). При этом всякий раз функция (3.30) вычисляется только для таких наборов, что 
. Для каждого значения функции (3.30) наряду с ним запоминаем оптимальную перестановку элементов , на которой реализуется фигурирующий в определении (3.29) путь 
. По окончанию вычислений вычеркиваем из памяти полученную на предыдущем шаге 
таблицу значений 
, а также соответствующие каждой функции оптимальные пути.
Подсчитаем трудоемкость алгоритма динамического программирования на - ом шаге. Количество значений 
функции 
, подлежащих вычислению и запоминанию, равно
(3.33)
На одно значение функции требуется 
действий (
выборов из таблицы, 
сложений, 
сравнений). Необходимый объем памяти 
(до вычеркивания из памяти таблиц и соответствующих оптимальных перестановок из элементов 
)) составляет
(3.34)
Шаг . Имея таблицу значений функций 
и список соответствующих им оптимальных перестановок из элементов 
, вычисляем функцию
Перестановка, на которой достигается этот минимум, однозначно определит искомый оптимум задачи коммивояжера.
Просуммировав величины (3.33) по шагам 
, получим выражение для суммарного объема 
необходимых вычислений: 
операций. Аналогично согласно (3.34) получим, что для решения задачи коммивояжера с помощью алгоритма динамического программирования требуется память 
ячеек.
Нетрудно убедиться, что реализация этого алгоритма на современных ПЭВМ ограничивается как по оперативной памяти, так и по быстродействию (продолжительности процесса счета) значениями 
порядка 50.