Рассуждая аналогично для нахождения /3(6), заметим, что кратчайший путь из города 6 проходит либо через город 8, либо 9. Отсюда следует:
/з(6) = тт
68+ /4(8) = 540+ 1030 = 1570* 69+/4(9) = 940+ 1390 = 2330.
Таким образом, у(6) = 1570 и кратчайший путь из города 6 в 10: 6 - 8 - 10.
Для нахождения (7), заметим, что:
Г С73 + /4(8) = 790 + 1030 = 1 820 fJ7) = mm<
179 + /4 (9) = 270 + 1390 = 1660 .
Таким образом, /з(7) = 1660, а кратчайший путь из города 7 в город 10:7 - 9-10.
Этап 2. Вычисленные ранее величины (5), f(6) и/3(7) позволяют сделать еще один шаг назад и вьтислить /2(2), /2(3) и/2(4), а также определить кратчайшие пути в Лос-Анджелес из городов 2, 3 и 4.
Найдем кратчайший путь из города 2 в город 10. Заметим, что любой из возможных путей проходит через города 5, 6 или 7. Отсюда
/2 (2) = min
с25+/з(5) = 680 + 1640 = 2 320* 2б+/з(6) = 790 + 1570 = 2 360 %+/з(7) = 1050 + 1660 = 2 710.
Таким образом, /2(2) = 2 320, кратчайший путь из города 2 проходит
через город 5, а далее кратчайшим путем 5 - 8 - 10, определенным нами на этапе 3, и, следовательно, есть 2 - 5 - 8 - 10. Аналогично
/2(3) = min
35+/3(5) = 580+ 1640 = 2 220* /3(6) = 760+ 1570 = 2 330 + /з(7) = 660 + 1 660 = 2 320.
Следовательно, /(З) = 2 220, а кратчайший путь из 3 в 10 проходит
через 5, а далее кратчайшим путем 5 - 8 - 10, определенным нами на этапе 3, следовательно, и есть 3 - 5 - 8 - 10.
Аналогично
/2 (4) = min
45+/з(5) = 510 + 1640 = 2150* 46+/з (6) = 700+ 1570 = 2 270 47 + /з (7) = 83 О +1 660 = 2 490.
Следовательно, /2(4) = 2 150, а кратчайший путь из 4 в 10 есть 4 - 5 8 -10.
Этап 1. Теперь мы можем использовать найденные значения /2(2), /2(3) и/2 (4) для нахождения /(1). Рассуждая аналогично, можно получить соотношение
2+/2(2) = 550+2320 =2870* /i(l) = min I с,з + /2(3) =900+2 220 =3120 [4 + Л (4) = 770 + 2150 = 2 920.
Таким образом, /(I) = 2 870, а кратчайший путь из 1 в 10 проходит через город 2, а далее по кратчайшему пути из 2 в 10, найденному нами на предыдущем этапе. Итак, оптимальным является маршрут 1 - 2 - 5 - 8 - 10.
7.1. Основная рекуррентная формула метода динамического программирования
Во многих примерах, использующих метод динамического программирования (задача о закупке оборудования или задача о кратчайшем пути), каждый очередной итог состоит в рассмотрении всех состояний, в котором система может находиться на данном шаге. В этом случае основная рекурсивная формула динамического программирования (в случае решения задачи минимизации) может быть записана в виде
/ (/) = min { (стоимость шага t) + + /1 (новое состояние перед шагом t+1) },(7.1)
где минимум в соотношении (7.1) берется по всем возможным решениям в ситуации, когда система на шаге t находится в состоянии /. В соотношении (7.1) величина }(/) есть минимальная стоимость завершения задачи из состояния / (допустим, задача заканчивается на шаге Т), если предположим, что на шаге / система находится в состоянии /.
Соотношение (7.1) отражает тот факт, что минимальная стоимость затрат, необходимых, чтобы от шага / дойти до конца задачи, может быть получена минимизацией суммы затрат самого шага / и минимальных затрат, которые необходимы для того, чтобы от шага t + 1 дойти до конца задачи.
Корректность соотношения (7.1) в конкретной задаче зависит от трех важных обстоятельств:
1)правильной спецификации всех возможных шагов на этапе / и из данного состояния /;
2)определения, как зависят текущие затраты на этапе t от значения t, текущего состояния и решения, принятого на этапе t\
3)определения, как состояние на этапе / + 1 зависит от значения состояния на этапе / и решения, принятого на этапе /.
Если понятия «состояние», «этап» и «решение» определены корректно, то перечисленные аспекты 1-3 не будут представлять большую сложность при реализации.
Рассмотрим еще ряд примеров применения метода динамического программирования с целью построения рекурсивных соотношений типа (7.1).
Пример. Владелец озера должен решить, сколько форели вылавливать и продавать каждый год. Если он продает х форелей в течение года /, то доход составляет г(х). Стоимость отлова х форелей в течение года есть функция с (х, Ь)отх - количества вьшавливаемых форелей и - количество форелей на начало года. Конечно, форель размножается. Предположим, что количество форелей к началу каждого года возрастает на 20 % по сравнению с количеством на конец предыдущего. Предположим также, что в начале первого года в озере 10 ООО форелей. Применяя рекурсию по методу динамического программирования, определить план отлова, который максимизирует суммарную чистую прибыль за период Т лет.
Решение.
В задачах, в которых решения надо принимать в несколько моментов времени, часто существует альтернатива между текущей выгодой и выгодой будущих периодов. Например, мы можем отловить сразу много форели, но тогда озеро опустеет и отлов в последующие годы снизится. С другой стороны, если отловить мало форели, то хотя мы заработаем мало, но сможем рассчитывать на большие уловы, а следовательно, и на большие прибьши в конце нашего временного периода.