3. Динамическое программирование

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

Рассмотрим

Пример 3.1. Задан ориентированный граф G=(V, A) и неотрицательные длины дуг CE, EÎA. Требуется найти кратчайший путь из вершины SÎV в вершину TÎV.

Заметим, что, если кратчайший путь из S в T проходит через вершину p, то пути из S В P и из P В T также кратчайшие. Это замечание позволяет привести одну из формулировок Принципа оптимальности: “подпуть оптимального пути оптимален”.

Обозначим через D(v) длину кратчайшего пути из S в VÎV. Тогда

Где V-(v)={iÎV: (i, v)ÎA}. Если длины кратчайших путей из S во все вершины множетва V-(V) известны, то можно найти длину кратчайшего пути из S в V. Сам кратчайший путь может быть восстановлен на обратном ходе, двигаясь из V в S.

Таким образом, для нахождения кратчайшего пути из S в T следует решить аналогичные задачи для вершин VÎV, которые могут войти в искомый путь. При этом, начиная с вершины S, на каждом шаге к частично построенному дереву кратчайших путей добавляется только одна вершина (вместе с соответствующей дугой). Процесс завершается, когда вершина T включена в дерево кратчайших путей. Так как длина кратчайшего пути до T в общем случае может быть найдена на произвольном шаге, трудоемкость описанного алгоритма равна O(|A|).¨

Алгоритмы ДП применимы в случаях, когда в процессе принятия решений удается:

Ø выделить отдельные этапы (шаги) процесса;

Ø осуществить оптимизацию управления на каждом шаге;

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

Ниже рассмотрены три задачи, для решения которых используется метод ДП.

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