Проблема размерности в динамическом программировании.

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

Увеличение количества переменных состояния вызывает рост числа возможных вариантов решения, ассоциированных с каждым из этапов. Это может привести к так называемой проблеме «проклятие размерности», которая является серьезным препятствием при решении задач динамического программирования средней и большой размерности.

В качестве примера рассмотрим задачу о загрузке рюкзака, но уже при двух ограничениях (например, ограничение по весу и по объему):

(1)

где , . Поскольку в задаче имеется два вида ресурсов , то необходимо ввести два параметра состояния и . Обозначим , , . Тогда ограничения (1) можно привести к виду:

(2)

где . В рекуррентных уравнениях метода динамического программирования для задачи о «ранце» с двумя ограничениями (1):

каждая из функций , является функцией двух переменных. Если каждая из переменных , может принимать 10² значений, то функцию приходится табулировать в 10⁴ точках. В случае трех параметров при тех же предположениях требуется вычислять 10⁸ степени значений функций .

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