4. Задачи динамического программирования

   1. Задачи динамического программирования. Её решение методом динамического программирования.

Определение. Задача динамического программирования (ДП) – это задача оптимального управления некоторым многошаговым процессом.

Подобных задач, ровно как и методов их решения, существует великое множество. Изобретаются они в каждом конкретном случае индивидуально, но все объединены общей идей решения – так называемого метода решения задачи через чайник: что бы вскипятить воду, нужно налить её в чайник, поставить его на плиту, включить плиту и т.д. Если же вода в чайнике уже налита, то нужно её вылить. А что делать дальше, мы уже знаем. Таким образом, в процессе решения мы сводим задачу к той, решать которую уже научились на предыдущем шаге.

Рассуждения при этом приводятся примерно следующие.

Нам необходимо найти оптимальное решение в конце маршрута. Если бы мы знали оптимальное решение для всех предыдущих этапов, то нашли бы решение для последнего. Чтобы найти решение для предпоследнего этапа, мы должны знать решение для второго с конца этапа, и т.д. То есть, разрабатывается метод динамического программирования с конца. Реализуется же он с начала: высчитываем оптимальные значение с самого начала и находим оптимальную стоимость. После этого необходимо найти собственно оптимальный маршрут. Его находим с конца.

Задача. Рассмотрим задачу оптимального управления многошаговым процессом. Над ребрами данного графа проставлены стоимости переходов из одной вершины в другую. Необходимо найти путь по которому с минимальными затратами можно попасть из S⁽⁰⁾в S⁽⁵⁾ (см. рисунок 4.1).

Рисунок 4.1. – исходный граф.

Идея решения. В принципе мы умеем решать подобные задачи по алгоритму Дейкстры и Форда-Беллмана. Попробуем теперь решить эту задачу методом динамического программирования. Он изобретается с конца. Нам необходимо найти минимально возможную сумму, имея которую, мы можем добраться до S⁽⁵⁾.

Рассуждаем так: если бы мы знали «стоимости» всех вершин. Из которых мы можем попасть в S⁽⁵⁾ (то есть вершин ), то мы бы нашли стоимости всех вершинS⁽⁵⁾ (для этого к стоимости вершин из S⁽⁴⁾ прибавляем стоимости переездов и выбираем минимум из получившихся сумм). Чтобы найти стоимости S⁽⁴⁾ мы должны знать стоимости S⁽³⁾ и т.д. Так спускаемся до вершины S⁽⁰⁾, стоимость которой равна нулю.

Итак,

Здесь – минимально возможная сумма денег, имея которую мы можем добрать отИмеем:

Рисунок 4.2. – Здесь – полученный стоимости вершин.

10

Реализация метода ДП происходим от начала к концу (то есть слева направо в нашем случае). Самый внешний цикл – по i; в нём в прямом порядке перебираем уровни вершин. Следующий по вложенности цикл – по j; в нём перебираем вершины одного уровня. Самый внутренний цикл – по k. Изменение направления прохода двух вложенных циклов не повлияет на конечный результат.

Последний этап – восстановление оптимального пути – реализуется из конца в начало. Для этого смотрим, из какой вершины предыдущего уровня была достигнута стоимость нашей вершины, постепенно продвигаясь справа налево.

Рисунок 4.3. – Восстановление оптимально пути.