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


[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


142

10.1. Рекуррентная природа вычислений ДП

есть три возможных маршрута, по которым можно достичь узла 5, а именно (2, 5), (3, 5) и (4, 5). Эта информация вместе с кратчайшими расстояниями к узлам 2, 3, и 4 определяет кратчайшее (накопленное) расстояние к узлу 5 следующим образом.

Кратчайший

I = min

чпуть к узлу 5 I =2.з.4

Кратчайший (Расстояние от путь к узлу i J узла / к узлу 5, 7 + 12 = 19

8+ 8 = 16 5+ 7 = 12

Аналогично для узла 6 имеем следующее.

Кратчайший \( Кратчайший

= тЫ

путь к узлу 6) =3 4 И путь к узлу i

-12 (изузла4).

Расстояние от чузла ( к узлу 6

S+ 9 = 17 тт< ? = 17 (изузла3).

15+ 13 = 18 1

Этап 2. Итоговые результаты.

Кратчайший путь к узлу 5 равен 12 миль (из узла 4).

Кратчайший путь к узлу 6 равен 17 миль (из узла 3).

Последним шагом является третий этап. Конечный узел 7 можно достичь как из узла 5, так и 6. Используя итоговые результаты этапа 2 и расстояния от узлов 5 и 6 к узлу 7, получаем следующее.

Кратчайший4 путь к узлу 1 /

12 + 9 = 21 тт{ } = 21 (из узла 5).

17 + 6 = 23 v У

Этап 3. Итоговые результаты.

Кратчайший путь к узлу 7 равен 21 миле (из узла 5).

Приведенные вычисления показывают, что кратчайшее расстояние между узлами 1 и 7 равно 21 миле. Города, через которые проходит кратчайший маршрут, определяются следующим образом. Из итоговых результатов третьего этапа следует, что узел 7 связывается с узлом 5. Далее из итоговых результатов второго этапа следует, что узел 4 связывается с узлом 5. Наконец, из итоговых результатов первого этапа следует, что узел 4 связывается с узлом 1. Следовательно, оптимальным маршрутом является последовательность 1-> 4-* 5-* 7.

Теперь покажем, как рекуррентные вычисления динамического программирования можно выразить математически. Пусть Дх,-) - кратчайшее расстояние до узла х, на этапе /, d(xLljci) - расстояние от узла до узла дг,. Тогда / вычисляется на основе значений fLl с помощью следующего рекуррентного уравнения.

/(*,)= min {rf(*w,x,) + /,-i(*,-,)}. 1 = 1.2,3.

все допустимые L 1

I*.-! -x, )-маршругы

При / = 1 полагаем /0(*0) = 0. Это уравнение показывает, что кратчайшие расстояния f{x) на этапе i должны быть выражены как функции следующего узла дг,. В терминологии динамического программирования дг, именуется состоянием системы на этапе /.



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

Определение состояния системы приводит к следующему унифицированному положению.

Принцип оптимальности. На каждом этапе оптимальная стратегия определяется независимо от стратегий, использованных на предыдущих этапах.

Применение принципа оптимальности демонстрируется вычислениями из примера 10.1.1. Например, на этапе 3 мы используем кратчайшие пути к узлам 5 и 6 и не интересуемся, как эти узлы были достигнуты из узла 1.

УПРАЖНЕНИЯ 10.1

1. Решите задачу из примера 10.1.1, предполагая, что используются следующие длины маршрутов:

d(l, 2) = 5,(1,3) = 9,(1,4) = 8,

d(2, 5) = 10, rf(2, 6)= 17,

d(3, 5) = 4, d(3, 6)= 10,

d(4, 5) = 9, d(4, 6) = 9,

d(5, 7) = 8,

d(6,1) = 9.

2. Я - заядлый турист. Прошлым летом мы с другом отправились в пятидневный поход по прекрасным Белым Горам в штате Нью-Гемпшир. Мы решили ограничить наше путешествие территорией, на которой расположены три хорошо известные вершины: Вашингтон, Джефферсон и Адаме. Гора Вашингтон имеет шестимильную тропу от подножия до вершины. Аналогичные тропы гор Джефферсона и Адамса имеют длину 4 и 5 миль соответственно. Тропы, соединяющие подножия этих трех гор, имеют следующую длину: 3 мили между вершинами Вашингтона и Джефферсона, 2 мили между вершинами Джефферсона и Адамса и 5 миль между вершинами Адамса и Вашингтона. В первый день мы стартовали от подножия вершины Вашингтона и вернулись в эту же точку к концу пятого дня. Нашей целью было пройти как можно более длинный путь. Мы также решили подниматься каждый день только на одну вершину и располагаться лагерем у подножия той горы, на которую мы решили восходить на следующий день. Кроме того, мы решили, что не будем подниматься на одну и ту же вершину в течение двух дней подряд. Каким было расписание нашего похода?

10.2. РЕКУРРЕНТНЫЕ АЛГОРИТМЫ ПРЯМОЙ И ОБРАТНОЙ ПРОГОНКИ

В примере 10.1.1 вычисления проводились последовательно: от первого этапа до третьего. Такая последовательность вычислений известна как алгоритм прямой прогонки. Этот же пример может быть решен с помощью алгоритма обратной прогонки, в соответствии с которым вычисления проводятся от третьего этапа до первого.



10.2. Рекуррентные алгоритмы прямой и обратной прогонки

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

Пример 10.2.1

Рекуррентное уравнение для алгоритма обратной прогонки в примере 10.1.1 имеет вид /(*,.)= min {d(x„xM) + fM{xM)}, i = l,2,3.

вес допустимые )-маршругы

где /4(х4) = 0 для xt = 7. Соответствующей последовательностью вычислений будет

и-* и-* Л-

Этап 3. Поскольку узел 7 (xt = 7) связан с узлами 5 и 6 (х3 = 5 и 6) только одним маршрутом, альтернативы для выбора отсутствуют, а результаты третьего этапа можно подытожить следующим образом.

а\Х}, х4) Оптимальное решение

Xi х4 = 7 h(Xi) xt

5 9 9 7

6 6 6 7

Этап 2. Так как маршрута (2, 6) не существует, соответствующая альтернатива не рассматривается. Используя значения f3(x3), полученные на третьем этапе, мы можем сравнить допустимые альтернативные решения, как показано в следующей таблице.

01*2, Хз) + Н(хъ)

Оптимальное решение

Хз = 5

х3 = 6

«*) х\

12 + 9 = 21

21 5

8 + 9= 17

9 + 6 = 15

15 6

7 + 9=16

13 + 6 = 19

16 5

Оптимальное решение второго этапа означает следующее. Если вы находитесь в узле (городе) 2 или 4, кратчайший путь к узлу 7 проходит через узел 5, а если в узле

3 - через узел 6.

Этап 1. Из узла 1 начинаются три альтернативных маршрута: (1, 2), (1, 3) и (1, 4). Используя значения f2(x2), полученные на втором этапе, вычисляем данные следующей таблицы.

Оптимальное решение на первом этапе показывает, что кратчайший путь проходит через город 4. Далее из оптимального решения на втором этапе следует, что из города

4 необходимо двигаться в город 5. Наконец, из оптимального решения на третьем этапе следует, что город 5 связан с городом 7. Следовательно, полным маршрутом, имеющим кратчайшую длину, является 1-> 4-> 5-> 7, и его длина равна 21 миле.

[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]