назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [ 65 ] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


65

Рассуждая аналогично для нахождения /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 ООО форелей. Применяя рекурсию по методу динамического программирования, определить план отлова, который максимизирует суммарную чистую прибыль за период Т лет.

Решение.

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

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [ 65 ] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]