Математическое обеспечение метода динамического программирования будущего

Уравнение Беллмана (уравнение динамического программирования) — это основное математическое соотношение, которое связывает значение оптимального решения задачи в текущем состоянии со значением в следующем состоянии. Его в 1953 году сформулировал американский математик Ричард Беллман, разбив сложную многошаговую задачу на простые повторяющиеся шаги.

Главные идеи метода

Принцип оптимальности: Оптимальное поведение имеет свойство того, что какими бы ни были начальное состояние и решение на первом шаге, последующие решения должны составлять оптимальную стратегию относительно состояния, полученного после первого шага.

Разделение на подзадачи: Сложная задача о длинном пути делится на один текущий шаг и оставшуюся часть задачи.

Рекуррентность: Общий результат выражается через ту же функцию, но для следующего момента времени или состояния.

Автор уравнения, Ричард Эрнест Беллман (Richard Ernest Bellman) (26 августа 1920 года — 19 марта 1984 года) — американский математик, один из ведущих специалистов в области математики и вычислительной техники, член Национальной инженерной академии США и Национальной академии наук США. Автор книг "Динмаическое программирование", "Введение в теорию матриц", "Некоторые вопросы математической теории процессов управления", "Прикладные задачи динамического программирования", "Кибернетика и медицинская диагностика" и др.

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

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

Теория динамического программирования родилась из ряда технико-экономических задач, таких, как задача о наиболее эффективном использовании оборудования или задача о наиболее выгодной политике закупок.

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 году он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE.

Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме. Слово «программирование» в словосочетании «динамическое программирование» в действительности к «традиционному» программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация».

Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определённое расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

Телеграм: t.me/ainewsline

Источник: www.koob.ru

Комментарии: