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

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



НазваниеМетод динамического программирования
Дата конвертации16.11.2012
Размер444 b.
ТипРешение


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


Для задач, общее решение которых может быть получено как результат решений некоторого ряда подзадач

    • Для задач, общее решение которых может быть получено как результат решений некоторого ряда подзадач
    • (d1, d2, …, dp,…, dq),
    • применяется метод динамического программирования


Метод динамического программиро-вания (метод Гамильтона-Якоби-Беллмана) ориентирован на поиск оптимального управления широкого класса систем, в том числе для решения задач планирования, распределение ресурсов, снабжения, разрешения игровых ситуаций, построение алгоритмов решения задач и т.д.

  • Метод динамического программиро-вания (метод Гамильтона-Якоби-Беллмана) ориентирован на поиск оптимального управления широкого класса систем, в том числе для решения задач планирования, распределение ресурсов, снабжения, разрешения игровых ситуаций, построение алгоритмов решения задач и т.д.



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

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



Каждое решение dp должно являться локальным решением, которе оптимизировало бы некоторый глобальный критерий качества, например, стоимость путешествия, длину пройденного пути, массу перевезённого груза, место, занимаемое файлом на диске, и т.п. Для того, чтобы данный метод был применим, необходимо, чтобы решаемая задача отвечала принципу оптимальности:

  • Каждое решение dp должно являться локальным решением, которе оптимизировало бы некоторый глобальный критерий качества, например, стоимость путешествия, длину пройденного пути, массу перевезённого груза, место, занимаемое файлом на диске, и т.п. Для того, чтобы данный метод был применим, необходимо, чтобы решаемая задача отвечала принципу оптимальности:


jpg" alt="">

^

если (d1, d2, …, dp+1,…, dq) – оптимальный ряд принимаемых решений, то и ряды (d1, d2, …, dp) и (dp+1,…, dq) должны быть оптимальными.

  • если (d1, d2, …, dp+1,…, dq) – оптимальный ряд принимаемых решений, то и ряды (d1, d2, …, dp) и (dp+1,…, dq) должны быть оптимальными.



Например, если кратчайшая дорога от Нижнего Новгорода до Москвы проходит через Владимир, то и оба участка этой дороги – Нижний Новгород - Владимир и Владимир -Москва – также должны быть самыми короткими. Следовательно, задачи нахождения кратчайшего пути удовлетворяют принципу оптимальности.

  • Например, если кратчайшая дорога от Нижнего Новгорода до Москвы проходит через Владимир, то и оба участка этой дороги – Нижний Новгород - Владимир и Владимир -Москва – также должны быть самыми короткими. Следовательно, задачи нахождения кратчайшего пути удовлетворяют принципу оптимальности.



В QBasic метод динамического программирования может быть реализован с помощью массивов, элементы которых вычисляются при помощи определённых рекуррентных соотношений. В общем случае, рекуррентные соотношения бывают следующих двух типов:

  • В QBasic метод динамического программирования может быть реализован с помощью массивов, элементы которых вычисляются при помощи определённых рекуррентных соотношений. В общем случае, рекуррентные соотношения бывают следующих двух типов:



Каждое принимаемое решение dp зависит от решений dp+1, …, dq. Будем говорить, что в этом случае применяется метод «вперёд». В этом методе решения будут приниматься в порядке dq, dq-1, …, d1.

  • Каждое принимаемое решение dp зависит от решений dp+1, …, dq. Будем говорить, что в этом случае применяется метод «вперёд». В этом методе решения будут приниматься в порядке dq, dq-1, …, d1.

  • Каждое принимаемое решение dp зависит от решений d1, …, dp-1. Будем говорить, что в этом случае применяется метод «назад». В этом методе решения будут приниматься в порядке d1, d2, …, dq.



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

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





Похожие:

Метод динамического программирования iconДокументы
1. /CИСТЕМА ПРОГРАММИРОВАНИЯ НА МАКРОАССЕМБЛЕРЕ MS-DOS/A1P0.TXT
2. /CИСТЕМА...

Метод динамического программирования iconДокументы
1. /Страуструп - Язык программирования С++/CHAP000.TXT
2. /Страуструп...

Метод динамического программирования iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Метод динамического программирования iconМинистерство образования Российской Федерации
Тьюринга, теория рекурсивных функций. Также в пособие включены сведения, имеющие практическое применение в области программирования:...
Метод динамического программирования iconУстойчивый метод декомпозиции и фильтрование временных рядов
Стойкий сходящийся итерационный метод для выявления в данных компонентов imf, является более устойчивым и предсказуемым, чем эмпирический...
Метод динамического программирования iconТема : Работа с массивами и матрицами в языке программирования
В программе используется одномерный целочисленный массив a с индексами от 0 до Ниже представлен фрагмент программы, записанный на...
Метод динамического программирования iconТема : Работа с массивами и матрицами в языке программирования
В программе используется одномерный целочисленный массив a с индексами от 0 до Ниже представлен фрагмент программы, записанный на...
Метод динамического программирования iconЯзык программирования Паскаль (Pascal) Виды языков программирования
Это и есть элементы формальности, организующие структуру программы. Их не так много, но их значение трудно переоценить. Служебные...
Метод динамического программирования iconДокументы
1. /метод рекомендации/rezol.doc
2. /метод...

Метод динамического программирования iconДокументы
1. /ЯЗЫК ПРОГРАММИРОВАНИЯ PERL/Perl1.txt
2. /ЯЗЫК...

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов