Полиномиальные алгоритмы

Определение. Алгоритм A называют полиномиальным, если его трудоемкость T_A ограничена полиномом от длины записи исходных данных, то есть существует константа c > 0 и натуральное число k такие, что T_A £ c L^k, где L — длина записи исходных данных.

Пример: Пусть f_i (x_i) = a_i x_i, тогда ,

но T_ДП = O(Y²n), то есть алгоритм ДП не является полиномиальным.

Обобщим задачу (1)–(3):

Если h_i(x) — целочисленные монотонно неубывающие функции, то вместо (4)–(5) можно использовать следующие рекуррентные соотношения:

s1(y) = f1(x* ), где x* = max{x £ a1 | h1(x) £ y}, 0 £ y £ Y;	(4¢)
sk(y) = { fk(x) + sk-1(y - hk(x))}, 2 £ k £ n, 0 £ y £ Y.	(5¢)

Упражнение 1. Доказать справедливость соотношений (4¢)–(5¢).

Обратная задача — поиск наименьших затрат на получение заданного количества продукции:

Если f_k(x) — целочисленные монотонно неубывающие функции, то для решения задачи (6)–(8) можно использовать идеи динамического программирования.

Пусть

Для 1£ k £ n, 0 £ d £ D обозначим через t_k(d) — оптимальное решение задачи (6)–(8), в которой n заменено на k, а D заменено на d.

Требуется найти t_n(D).

0 £ d £ D,	(9)
tk(d) = min{tk–1(d – fk(x)) + hk(x)| 0 £ x £ ak, x £ }, k ³ 2, 0 £ d £ D.	(10)

Рекуррентные соотношения

Упражнение 2. Доказать справедливость соотношений (9)–(10).

ТЕОРЕМА 2:Предположим, что D — наибольшее число, для которого оптимальное значение целевой функции задачи (6)–(8) не превосходит Y. Тогда оптимальное значение целевой функции задачи (1¢)–(3¢) равно D.

Доказательство: Пусть D удовлетворяет условию теоремы

и — соответствующее решение задачи (6)–(8).

Значит

и

Следовательно, D не превосходит оптимального решения D₁ задачи (1¢)–(3¢). Если бы D₁ было больше D, то решение задачи (6)–(8), в которой D заменено на D₁, тоже не превышало бы Y, что противоречит максимальности D.