Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
В основе метода динамического программирования лежит простая идея осуществления сравнения различных вариантов допустимых решений задачи (по значению целевой функции) не в конце построения множества всех возможных вариантов, а на каждом шаге построения возможных вариантов [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.