Конспект установочных лекций по комплексному курсу Информатика, Теория информации

Динамическое программирование


Если нам удастся умело выбрать индуктивный принцип, по которому порождается подлежащее минимизации множество, то при некоторых обстоятельствах можно понизить сложность метода.

Пример (задача коммивояжера). Следующее предписание при вызове perm(e, v) порождает (в случайном порядке) все перестановки множества v:

fct perm == (seq node s, set node m) set seq node:

if m == Æ  then {s}

else node x = some node q: q Î m;

È     perm(insert(s, x, i), m\{x}) fi о ^ i <.

lcngth(s)

где предписание insert, которое добавляет в последовательность s элемент k после i-й позиции, определяется следующим образом:

fct insert == (seq node

s, node k, nat i: i £ length(s)) seq node:

        if i == О     then <k> о s

                                 else <first(s)> о insert(rest(s), k, i—l) fi

Задачу коммивояжера можно рассматривать как задачу минимизации на множестве всех перестановок. Пусть задано отображение d:



fct d =( node

i, node j ) nat:      ''расстояние между вершинами i и j”.

Это отображение индуцирует предписание для вычисления длин путей:

fct sd = ( seq node s ) nat:

 if    s = є         then О

elif rest(s) = є  then О

                                else d(first(s), first(rest(s)))+sd(rest(s))

         fi

Мы хотим минимизировать выражение sd(s)+d(first(s), last(s))

на множестве всех перестановок s, где s Î perm(є, v) и ÷vê= n. Мощность исследуемого множества есть О(n!), что определяет также и сложность алгоритма. При наивном способе действий придется просмотреть (n-1)! перестановок, так как одну из вершин можно зафиксировать. Естественно, в практических применениях ищется не только длина минимального пути обхода, но и сам путь. Ниже мы дадим вычислительное предписание для вычисления длины минимального пути; предписание для нахождения самого пути может быть сформулировано совершенно аналогично.

Для решения задачи коммивояжера будем вычислять функцию mintour по следующему предписанию. Пусть х() Î v- заданная начальная вершина. Вызов mintour(m, i) дает длину минимального из путей через все вершины множества m, которые начинаются в вершине х() и заканчиваются в вершине i:

fct mintour = (set node

m, node

i: i e m) nat:

            min {sd(<xo> о s): s

Î perm(s, m) Ù last(s) = i}



Содержание раздела