Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Идея динамического программирования (ДП)




Читайте также:
  1. Алгоритм решения транспортной задачи линейного программирования методом потенциалов
  2. Алгоритмизация и программирование. Технологии программирования.
  3. Алгоритмизация и программирование. Технологии программирования.
  4. Билет 9. Линейный алгоритм. Графические элементы для создания блок-схемы алгоритма. Запись арифметического выражения в языке программирования.
  5. Виды оптимального программирования, их краткая характеристика.
  6. Вопрос 23. Гиппердинамический синдром. Основные направления работы по преодолению гиппердинамического синдрома у детей.
  7. Вопрос №37. Производительность, мощность и КПД динамического насоса.
  8. Дайте общую математическую формулировку задач дискретного программирования
  9. Дайте общую математическую формулировку задач нелинейного программирования
  10. Двойственные задачи линейного программирования. Теоремы двойственности

Метод ДП (Р. Беллман, В.С. Михалевич, Н.З. Шор ) можно трактовать как алгоритмическую версию рассуждений по индукции.

Пусть sk(y), 1 £ k £ n, 0 £ y £ Y, — оптимальное значение целевой функции задачи (1) – (3), где n заменено на k, Y заменено на y.

Требуется найти sn(Y) и набор переменных, на котором достигается это значение.ТЕОРЕМА 1.Пусть f1, … , fn ­—монотонно неубывающие функции. Тогда справедливы следующие рекуррентные соотношения:

s1(y) = f1(y), 0 £ y £ Y; (4)
sk(y) = max {sk-1(y - x) + fk(x) | 0 £ x £ y}, 2 £ k £ n, 0 £ y £ Y, (5)

Доказательство:Соотношение (4)очевидно. По определению

sk(y) ³ max {sk-1(y - x) + fk(x) | 0 £ x £ y}.

Пусть теперь — такой вектор, что и

.

Поскольку имеем

. Алгоритм ДП вычисляет множество Sk ={sk(y) | 0 £ y £ Y}, k =1,…,n с помощью соотношений (4) и (5), где на каждом шаге оптимизируется ровно одна переменная.

  Процесс вычисления S1,…,Sn называется прямым ходом алгоритма. Число операций » Y 2n Память » Y n .  
y S1(y) S2(y) Sn(y)
       
       
       
       
Y       Sn(Y)

 

При обратном ходе алгоритма вычисляются значения , с учетом того, что уже известны Sk(y). Например, определяется из уравнения и так далее.

Число операций » Y n. Память » Y Характеристики алгоритмов

 

Для оценки качества алгоритмов будем использовать два параметра:

TA трудоемкость (число элементарных операций алгоритма A);

ПА — требуемый объем памяти.

Элементарная операция — одна из арифметических операций: сложение, вычитание, умножение, деление или логическая операция сравнение двух чисел.

Нас будет интересовать зависимость параметров алгоритма от длины записи исходных данных задачи с точностью до порядка величин.

Пример: При Т = 3/2 n2 , будем писать T = O(n2) или T » n2.


Дата добавления: 2015-04-21; просмотров: 5; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты