Инструменты пользователя

Инструменты сайта


examination:mo:question15

Принцип Беллмана. Метод динамического программирования. Общая характеристика метода.

Метод динамического программирования основан на применении принципа оптимальности Беллмана: каково бы ни было состояние системы перед очередным шагом, необходимо выбирать управление на этом шаге так, чтобы доход на данном шаге вместе с оптимальным доходом на всех последующих шагах был максимальным. Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на ом шаге, затем на двух последних шагах, затем на трёх последних шагах и т. д., вплоть до первого шага. Таким образом, решение рассматриваемой задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, ом шаге. Для того чтобы найти это решение, очевидно, нужно сделать различные предположения о том, как мог окончиться последний шаг, и с учётом этого выбрать управление обеспечивающее максимальное значение функции дохода W(X^(n-1); Un) Такое управление, выбранное при определённых предположениях о том, как окончился предыдущий шаг, называется условно оптимальным управлением.

Итак, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предшествующего шага. Для того чтобы построить алгоритм решения задач динамического программирования, дадим математическую формулировку принципа оптимальности Беллмана. Пусть F0(X^(0)) − максимальный доход, получаемый за n шагов при переходе системы S из начального состояния X^(0) в конечное состояние X^(n) при реализации оптимальной стратегии управления U*=(U1*, U2*, … Un*) а Fk(X^(k))- максимальный доход, получаемый при переходе из любого состояния X^(k) в конечное состояние X^(n) при оптимальной стратегии управления на оставшихся n-k шагах.

Тогда,

при k=0,n.

Последнее выражение представляет собой математическую запись принципа оптимальности Беллмана и называется основным функциональным уравнением Беллмана. С использованием этого уравнения находится решение рассматриваемой задачи динамического программирования.

Однако есть одно серьезное осложнение. Дело в том, что попятная процедура предусматривает построение функций S(x, t) и ut(x), зависящих от n-мерного вектора x. По этому вектору x не нужно выполнять операций минимизации, но даже простое табулирование и хранение функций n переменных представляют большие трудности. Если, к примеру, составлять таблицы, придавая каждой переменной 100 значений, то для хранения таблицы одной функции n переменных понадобится 100n ячеек памяти. Всего же попятная процедура, в которой участвуют функции S(x, t) и ut(x), потребует (m + 1)N i i 100n ячеек.

Отсюда понятно, что вычислительная реализация метода динамического программирования сталкивается с большими трудностями. Эти трудности Р. Беллман назвал проклятием размерности. Для преодоления этих трудностей были предложены подходы, позволяющие сократить объем вычислений и потребности в памяти при построении оптимального управления. При этом, однако, приходится либо существенно пожертвовать точностью вычислений, либо отказаться от построения управления, оптимального в глобальном смысле, и ограничиться нахождением управлений и траекторий, оптимальных в локальном смысле, то есть по отношению к малым (локальным) вариациям этих траекторий.

Пример использования:

Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом.

Формулировка задачи

Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа. Заметим, что кратчайших путей может не существовать. Так, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой (каждый обход цикла уменьшает длину пути). Цикл, сумма весов рёбер которого отрицательна, называется отрицательным циклом.

examination/mo/question15.txt · Последние изменения: 2014/01/15 12:19 (внешнее изменение)