Понятие Динамического программирования. Классификация задач динамического программирования. Компьютерная технология решения задачи динамического программирования.
Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.
Основные необходимые свойства задач, к которым возможно применить этот принцип:
Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.
Задача должна быть определена для любого числа шагов и иметь структуру, не зависящую от их числа.
При рассмотрении k-шаговой задачи должно быть задано некоторое множество параметров, описывающих состояние системы, от которых зависят оптимальные значения переменных. Причем это множество не должно изменяться при увеличении числа шагов.
Выбор решения (управления) на k-м шаге не должен оказывать влияния на предыдущие решения, кроме необходимого пересчета переменных.
Задача о выборе траектории, задача последовательного принятия решения, задача об использовании рабочей силы, задача управления запасами — классические задачи динамического программирования.
Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи.
В основе решения всех задач динамического программирования лежит "принцип оптимальности" Беллмана, который выглядит следующим образом:
Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Этот принцип впервые был сформулирован Р. Беллманом в 1953 г. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование- процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.
Классификация:
Нисходящее: задача разбивается на подзадачи меньшего размера, они решаются, и затем комбинируются для решения исходной задачи.
Восходящее: все подзадачи, которые впоследствии понадобятся для решения исходной задачи, просчитываются заранее и затем используются для построения решения исходной задачи Восходящее ДП лучше нисходящего в смысле размера необходимого стека и количества вызовов функций.
Динамическое программирование.
Примеры задач:
· Наибольшая общая подпоследовательность
· Наибольшая увеличивающаяся подпоследовательность
· Задача о редакционном расстоянии
· Порядок перемножения матриц
· Задача о коммивояжере
· Наибольшее независимое множество вершин дерева
· Задача о кратчайших путях
Система Mathematica объединяет в себе запас мировых математических знаний, накопленных в справочной литературе, и использует свои собственные
революционные алгоритмы, чтобы развивать эти знания.
Умение проводить аналитические расчеты — одно из главных достоинств этой программы, автоматизирующей математические расчеты. Mathematica умеет преобразовывать и упрощать алгебраические выражения, дифференцировать и вычислять определенные и неопределенные интегралы, вычислять конечные и бесконечные суммы и произведения, решать алгебраические и дифференциальные уравнения и системы, а также разлагать функции в ряды и находить пределы
Mathematica позволяет строить двух и трехмерные графики различных типов в виде точек и линии на плоскости, поверхностей, а также контурные, градиентные (dencity plot), параметрические. Mathematica выполняет построение графика в три этапа. На первом создается множество графических примитивов, на втором они преобразуются в независимое от вычислительной платформы описание на языке PostScript, а на третьем это описание переводится в графический формат для той системы, на которой установлена Mathematica.
Система MatLab
Данная система ориентирована на матричные и векторные вычисления (её названием является сокращение словосочетания Matrix Laboratory) и предназначена в основном для численного моделирования технических систем. Её последние версии содержат элементы универсальных систем компьютерной алгебры: специальный модуль MatLab Notebook, позволяющий, в том числе, использовать возможности Microsoft Word для оформления документов, а также приобретённый у компании Maple Waterloo модуль основной символьной библиотеки системы Maple V 4.0 для выполнения некоторых аналитических расчётов. Входной язык в определённой мере напоминает BASIC (с элементами Фортрана и Паскаля). Интерфейс менее доступный и красочный, чем у системы MathCAD, однако скорость вычислений выше.
Использование в образовании нецелесообразно; система предназначена для профессиональной работы в области математики и смежных областях.
Система MatLab предназначена для выполнения инженерных и научных расчетов и высококачественной визуализации получаемых результатов. Эта система применяется в математике, вычислительном эксперименте, имитационном моделировании.
В пакет входит множество хорошо проверенных численных методов (решателей), операторы графического представления результатов, средства создания диалогов. Отличительной особенностью MatLab по сравнению с обычными языками программирования является матричное представление данных и большие возможности матричных операций над данными. Используя пакет MatLab можно, как из кубиков конструктора, построить довольно сложную математическую модель, или написать свою программу (весьма похожую на Фортран-программу). А можно используя SIMULINK и технологию визуального моделирования составить имитационную модель или систему автоматического регулирования.
Гибкий язык MatLab дает возможность инженерам и ученым легко реализовывать свои идеи. Мощные численные методы и графические возможности позволяют проверять предположения и новые возникающие идеи, а интегрированная среда дает возможность быстро получать практические результаты.