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|).¨
Алгоритмы ДП применимы в случаях, когда в процессе принятия решений удается:
Ø выделить отдельные этапы (шаги) процесса;
Ø осуществить оптимизацию управления на каждом шаге;
Ø показать, что последующие решения не влияют на качество решений, принятых на предыдущих шагах (принцип оптимальности).
Ниже рассмотрены три задачи, для решения которых используется метод ДП.
< Предыдущая | Следующая > |
---|