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


[Старт] [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]


64

Глава 7

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Динамическое программиро-

г г гОсновное рекуррентное соот-

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

тимизационные задачи. В большинстве приложений динамическое программирование получает оптимальное решение путем движения в обратном направлении - от конца задачи к началу. Задача большой размерности заменяется серией задач меньшей размерности.

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

Пример (игра со спичками). Пусть на столе лежат 30 спичек. Каждый игрок должен взять 1, 2 или 3 спички. Проигравшим считается тот, кто взял последнюю спичку. Может ли первый игрок всегда добиться выигрыша?

Решение.

Очевидно, что тот игрок, перед ходом которого на столе осталась только одна спичка, проигрьгоает. Если на столе остается 5 спичек, то тот, кто делает ход, проигрьшает. Это следует из того, что какой бы он ход ни сделал, другой игрок всегда может совершить такой ход, после которого на столе останется 1 спичка.

Действительно, если, например, на столе остается 5 спичек и очередным ходом забирается 2 спички, то следующий игрок забирает две спички и он выиграл. Рассуждая аналогичным образом, логично прийти к заключению, что тот игрок, перед ходом которого на столе остается 5, 9, 13, 17, 21, 25 или 29 спичек, проигрывает при правильной игре его про-



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

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

Пример. Джо Кучер живет в Нью-Йорке, но планирует перебраться в Лос-Анджелес. Средства Джо ограниченны, поэтому он решил проводить каждую ночь во время своего путешествия не в гостиницах, а у своих друзей. У него есть друзья в Колумбии, Нэшвиле, Луисвилле, Канзас-Сити, Омахе, Далласе, Сан-Антонио и Денвере. Джо знает, что после одного дня пути он может достичь Колумбии, Нэшвила и Луисвилля. После двух дней пути он может достичь Канзас-Сити, Омахи и Далласа. После трех дней пути он может достичь Сан-Антонио и Денвера. А после четырех дней пути он может достичь Лос-Анджелеса. Где должен останавливаться Джо, чтобы минимизировать протяженность всего маршрута? Расстояния между городами указаны на рис. 7.1.

Колумбия 2

680

Канзас-Сити 5

Лос-Анджелес 10

1030

Луисвилль 4



Решение.

Применим принцип обратного хода. Сначала проведем классификацию городов. Скажем, что город относится к 77-му классу, если в нем можно оказаться утром п-го дня. Так, например, Денвер и Сан-Антонио будут отнесены нами к 4-му классу.

Согласно принципу обратного хода, мы начинаем находить кратчайшие пути в Лос-Анджелес из городов 4-го класса. Далее, используя эту информацию, мы сможем найти кратчайшие пути в Лос-Анджелес из городов 3-го класса. Далее из городов 1-го класса, т.е. из Нью-Йорка.

Для удобства записи каждому из 10 городов присвоен номер от 1 до 10 (см. рис. 7.1). Мы также обозначим через cj - расстояние между /-м

и>м городами. Например, с = 580 - это расстояние между Нэшвилом и Канзас-Сити. Мы также обозначим через (/) кратчайшее расстояние

от города / до Лос-Анджелеса, полагая, что город / принадлежит классу t. Этапы будем нумеровать с конца.

Этап 4. Первоначально, согласно нашему плану, определим кратчайшие пути до Лос-Анджелеса из городов 4-го класса. Поскольку эти пути единственны, мы сразу получаем следующие результаты: /4(8) = 1030, /4(9) = 1390.

Этап 3. Теперь совершим еще один шаг в сторону начала и рассмотрим города класса 3. Например, для того чтобы найти /з(5); мы заметим, что существует два возможных пути из города 5 (Канзас-Сити) в Лос-Анджелес:

Vпуть 1: из города 5 в город 8 и далее кратчайшим путем в 10;

Vпуть 2: из города 5 в город 9 и далее кратчайшим путем в 10. Длина пути 1 может быть вычислена как с + /(8), а длина пути 2

может быть вычислена как С59 + /4(9). Следовательно, кратчайший путь

из города 5 в город 10 может быть записан как

/з(5) = тт

58 + /4(8) = 610 +1030 = 1640* .59+/4(9) = 790+ 1390 = 2180.

(* - обозначает случай, на котором достигается минимум). Таким образом, мы нашли кратчайший путь из города 5 в город 10: 5 - 8 - 10 и его длину 1 640. Заметим, что мы использовали при этом результаты предыдущего шага, а именно /4(8) и/4(9).

[Старт] [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]