Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Алгоритм решения задач методом динамического программирования. Уравнение Беллмана.
|
|
Динамическое программирование – метод решения задач оптимизации, характеризующиеся следующими этапами:
0. Задача 
состоит в оптимизации функции f на множество M.
1. Инвариантное погружение (составление семейства задач). Подбираем семейство задач: 
, каждая из которых состоит в поиске оптимального элемента 
с учетом ограничений: 
2. Вывод уравнения Беллмана. 
– решение задачи оптимизации 
, т.е. то значение x, при котором целевая функция принимает значение 
– функция Беллмана. А уравнением Беллмана называется уравнение, в которое входит функция Беллмана и значение – оптимальное значение.
3. Решение семейства задач.
3.1. Находим более простые задачи и решаем их.
3.2 Находим значение функции Беллмана B(t) и , найденные на предыдущем этапе и подставляем в уравнение Беллмана. Получаем новое решение.
Пункт 3.2 повторяем до тех пор, пока не найдем решение нашей задачи.
Уравнение Беллмана:
где 
- точка максимума.
|
|