6.2. Основные понятия и определения динамического программирования

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

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

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

(6.3)

(где l_i — оптимальное решение на i-м шаге.

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

6.2.1. Жадный алгоритм.

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

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

Таким образом, будут найдены условно-оптимальные решения на каждом шаге. Далее выполняется переход от условно-оптимального решения к безусловно-оптимальному решению на каждом шаге, т. е. выполняются вычисления от первого шага к последнему шагу, ориентируясь на полученные условно-оптимальные реше­ния. Теперь на первом шаге известна «стоимость» решения задачи от второго шага до последнего шага и, следовательно, можно ука­зать оптимальное решение на первом шаге (снизить «стоимость» первого шага). Далее аналогично выполняются второй, третий и т.д. шаги.

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

Пример 6. Проложить полотно железной дороги по кратчайшему, с эконо­мической точки зрения, пути между пунктами А и Б. На географи­ческой карте строится некоторая прямоугольная область, где в ле­вом нижнем углу помещен пункт А, а в правом верхнем углу — пункт Б. Прямоугольная область по горизонтали и по вертикали разделяется на произвольное количество отрезков, и по границам отрезков строится сетка. Для каждой стороны элементарного пря­моугольника определяется стоимость прокладки пути.

Для упрощения решения задачи положим, что путь может про­кладываться только по границам элементарных прямоугольных областей (т. е. под углом 90°), заранее известна стоимость строи­тельства по каждому элементарному отрезку, и путь от пункта Б к пункту А прокладывается в направлении справа налево и сверху вниз без петель. Таким образом, каждый возможный путь от пунк­та А до пункта Б будет представлять собой ломаную линию. Надо проложить такой путь от А к Б, чтобы суммарные затраты на его строительство были минимальны. Возможны два варианта: пол­ный перебор всех возможных путей, что очень долго и трудно, и использование динамического программирования с разделением задачи по шагам.

Разделим расстояние между пунктами А и Б на 17 отрезков (шагов) по горизонтали и на 8 отрезков (шагов) по вертикали. Тогда длина любого пути составит т= 17 + 8 = 25 отрезков (ша­гов). На рисунке указаны стоимости строительства пути по каж­дому отрезку.

Перемещение от Б к А выполняется последовательно по элемен­тарному пути (шагу) к следующей узловой точке. Каждая узловая точка характеризуется двумя координатами: горизонтальной и верти­кальной. Обе координаты целочисленные и большие нуля: 0≤х≤ 17 и 0≤у≤8. В каждой узловой точке будем определять условное оп­тимальное управление (движение по горизонтали или движение по вертикали). Направление движения выбирается из условия: стои­мость строительства всех остальных отрезков пути, включая текущий отрезок, должна быть минимальной. Эту стоимость будем называть условно-оптимальной.

Итак, запустим процедуру поиска условно-оптимального реше­ния от конца к началу (от пункта Б к пункту А). На последнем 25-м шаге будем находиться в верхнем правом углу (пункт Б). Попасть в пункт Б можно с 24-го шага и возможны два варианта: двигаться по горизонтали (стоимость 11, узел Б₁) или двигаться по вертикали (стоимость 15, узел Б₂) .

Рис.6

Рис.7

Из узла Б₁ к пункту Б можно двигаться только в одном направ­лении — по горизонтали, и стоимость движения составит 11. Точно также из узла Б₂ к пункту Б можно двигаться только в одном на­правлении — по вертикали, и стоимость движения составит 15. Та­ким образом, для последнего 25-го шага предпочтительнее движе­ние из узла Б₁. Теперь рассмотрим предшествующий 24-й шаг. Пре­дыдущий 23-шаг мог закончиться в одном из узлов В₁, В₂ и В₃. Из узла В₁ движение возможно только в одном направлении — по го­ризонтали к узлу Б₁, и стоимость этого перехода составит 11, а сум­марная стоимость до конечного пункта Б — 22. Из узла В₂ возмож­ны два направления движения:

• В₂ — Б₁ — Б с общей стоимостью движения 11 + 15 = 26;

• В₂ — Б₂ — Б с общей стоимостью движения 15 + 12 = 27. Наилучший путь первый, и его стоимость 26 поместим в кру­жок В₂.

Из узла В₃ движение возможно только в одном направлении — по вертикали к узлу Б₂, и общая стоимость движения составит 15 + 14 = 29.

Наилучший вариант движения от узла В₁ к узлу Б₁ так как его суммарная стоимость составит 22.

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

По изложенному алгоритму выполняется условная оптимизация: в каждой узловой точке известно направление движения и стоимость оставшегося пути. Дойдя до пункта А, получим условную оптималь­ную стоимость строительства железнодорожного пути, равную 262.

Рис.8

Во время движения от пункта Б к пункту А несколько раз воз­никала ситуация выбора: куда идти, влево или вниз (по горизонтали или по вертикали), при одинаковой стоимости работ (вершины Е₁, М₁, Р₁, С₁, Ф₁,Х₁). В данной ситуации выбор направления движения был произвольным, так как при повторном просчете неудачный вы­бор будет исправлен.

Теперь при прямом просчете алгоритма возможно улучшение полученных решений на отдельных шагах. Переходим к безуслов­ному оптимальному управлению — определению пути от пункта А к пункту Б самым дешевым способом.

Начинаем движение от пункта А вверх (по вертикали), хотя ус­ловно-оптимальное решение дало результат по горизонтали. Двигаясь из пункта А по вертикали, ищем самый короткий («деше­вый») путь к одной из узловых точек, в которых был неоднознач­ный выбор (E₁, M₁, P₁, С₁ Ф₁ X₁). Если вновь пройденный путь дает лучшие результаты, чем ранее пройденный условно-оптимальный путь, то условно-оптимальный участок пути заменяем на безуслов­но-оптимальный путь.

От узловой точки P₁ до пункта Б стоимость работ составляет 145. По вновь пройденному оптимальному пути, стоимость работ состав­ляет 95.

Рис.9

Итоговая сумма 145 + 95 = 240, что меньше условно-оптимально­го решения (262). Поэтому условно-оптимальное решение от пункта А до узловой точки P₁ заменим на только что найденное безусловно-оптимальное решение. Далее от узловой точки P₁ также возможен альтернативный путь до узловой точки Mi .

Рис.10

Стоимость каждого из путей условно-оптимального и безусловно-оптимального одинаковая, поэтому можно выбрать любой из путей.

Но от узловой точки P₁ до узловой точки E₁ можно добраться, минуя узловую точку М₁. Рассмотрим этот путь (на рисунке показан пунктирной линией).

Рис.11

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

От узловой точки М₁ до узловой точки E₁ можно добраться дру­гим путем.

Рис.12

Стоимость движения по этому пути составит 191 + 52 = 243, что «дороже» (длиннее), чем по ранее пройденному пути, поэтому за­мену пути выполнять не будем [3].

Больше альтернативных разветвлений не было. Оптимизация закончена. Безусловно-оптимальный путь показан на рисунке. Его стоимость составляет 240. Причем отрезок пути от узловой точки P₁ до узловой точки M₁ можно выполнить двумя вариантами, одинако­выми по стоимости.

Рис.13