Динамическое программирование - Решение задач методами динамического программирования, нахождение кратчайшего пути

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

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

Оптимальное решение задачи в целом складывается из оптимальных решений на каждом шаге

Где - оптимальное решение на I-М шаге.

В этом случае говорят, что целевая функция L обладает "аддитивным критерием качества".

Нахождение кратчайшего пути.

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

Учитывая вышесказанное, выполнить вычисления в задачах динамического программирования удобнее от конца к началу. Действительно легко можно планировать последний, M-1. Выполняя вычисления по последнему шагу, надо сделать ряд предположений: как закончился предыдущий, M-1, шаг и для каждого предположения найти условно-оптимальное решение на M-М шаге. Аналогично выполняются M-1, M-2 и т. д. шаги, вплоть до первого шага. Таким образом, будут найдены условно-оптимальные решения на каждом шаге. Далее выполняется переход от условно-оптимального решения к безусловно-оптимальному решению на каждом шаге, т. е. выполняются решения о первого шага к последнему, ориентируясь на полученные условно-оптимальные решения. Теперь на первом шаге известна "стоимость" решения задачи от второго шага до последнего шага и, следовательно, можно указать оптимальное решение на первом шаге (снизить "стоимость" первого шага). Далее выполняются аналогично второй, третий и т. д. шаги.

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

3. Специальная часть

Похожие статьи




Динамическое программирование - Решение задач методами динамического программирования, нахождение кратчайшего пути

Предыдущая | Следующая