Проблема размерности в динамическом программировании.
В рассмотренных примерах (задача о загрузке рюкзака и задача о надежности) для описания состояний системы использовалась только одна переменная, одной переменной задавалось и управление. В общем случае в моделях динамического программирования состояния и управления могут быть описаны с помощью нескольких переменных, образующих вектора состояния и управления.
Увеличение количества переменных состояния вызывает рост числа возможных вариантов решения, ассоциированных с каждым из этапов. Это может привести к так называемой проблеме «проклятие размерности», которая является серьезным препятствием при решении задач динамического программирования средней и большой размерности.
В качестве примера рассмотрим задачу о загрузке рюкзака, но уже при двух ограничениях (например, ограничение по весу и по объему):
(1)
где , . Поскольку в задаче имеется два вида ресурсов , то необходимо ввести два параметра состояния и . Обозначим , , . Тогда ограничения (1) можно привести к виду:
(2)
где . В рекуррентных уравнениях метода динамического программирования для задачи о «ранце» с двумя ограничениями (1):
каждая из функций , является функцией двух переменных. Если каждая из переменных , может принимать 102 значений, то функцию приходится табулировать в 104 точках. В случае трех параметров при тех же предположениях требуется вычислять 108 степени значений функций .
Итак, наиболее серьезным препятствием практического применения динамического программирования оказывается число параметров задачи.
Дата добавления: 2022-04-12; просмотров: 75;