Динамическому программированию

Курсовая работа по разделу “Динамическое программирование” может быть выполнена на тему: Область применения метода динамического программирования и эффективность его использования.

Усвоив принцип оптимальности Р. Беллмана, студент должен как этот принцип действует при решении задач, рассматриваемых обучающей компьютерной программой. Необходимо понять из-за чего возникает влияние предыстории, как оно мешает применению динамического программирования и к чему может привести игнорирование этого влияния предыстории при бездумном применении алгоритма динамического программирования при решении соответствующих задач. Необходимо понимать, что речь идёт не только о получении решений, существенно отличных от оптимальных, но в сложных задачах при наличии ограничений на искомую траекторию может вообще привести к остановке алгоритма из-за отсутствия допустимых продолжений процесса поиска. Целесообразно привести конкретные примеры задач такого рода.

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

- отсутствие производных целевой функции в отдельных точ­ках несущественно для метода динамического программирова­ния;

- метод динамического программирования нечувствителен к наличию локальных экстремумов целевой функции;

- метод динамического программирования можно использо­вать при анализе любых многоэтапных процессов выработки решения;

- наличие ограничений на положение отдельных точек иско­мой траектории не приводит к осложнениям при использовании динамического программирования.

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

Целесообразно также показать как различная формализация понятия “состояние системы” влияет на применимость метода динамического программирования при наличии ограничений и привести конкретные примеры.

В курсовой работе следует остановиться также и на вопросе применимости динамического программирования при решении не только дискретных, но и непрерывных задач. Показать влия­ние искусственного введения дискретности. Например, можно ли при этом пропустить локальный экстремум?

Целесообразно рассмотреть и вопрос использования для со­кращения времени счёта следующей двухэтапной схемы:

1. Решаем задачу с крупным шагом. Находим оптимальную траекторию.

2. Относительно полученной траектории разбиваем сетку с мелким шагом и повторяем расчёт.

Гарантирует ли такой приём нахождение оптимального ре­шения?

Эти вопросы рассматривались в курсе лекций, ответы на них есть и в лите­ратуре [4,5].