Ремонт принтеров, сканнеров, факсов и остальной офисной техники


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




[109]

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

17.2. Когда применим жадный алгоритм?

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

Принцип жадного выбора

Говорят, что к оптимизационной задаче применим принцип жадного выбора (greedy-choice property), если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие межде жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берёт «самый жирный кусок», а потом уже пытается сделать наилучший выбор среди оставшихся, каковы бы они ни были; алгоритм динамического программирования принимает решение, просчитав заранее последствия для всех вариантов.

Как доказать, что жадный алгоритм даёт оптимальное решение? Это не всегда тривиально, но в типичном случае такое доказательство следует схеме, использованной в доказательстве теоремы 17.1. Сначала мы доказываем, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не худшее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции.

Оптимальность для подзадач

Говоря иными словами, решаемые с помощью жадных алгоритмов задачи обладают свойством оптимальности для подзадач (have optimal substructure): оптимальное решение всей задачи содержит в себе оптимальные решения подзадач. (С этим свойством мы уже встречались, говоря о динамическом программировании.) Например, при доказательстве теоремы 17.1 мы видели, что если А - оптимальный набор заявок, содержащий заявку номер 1, то А = А\{1} - оптимальный набор заявок для меньшего множества


заявок S, состоящего из тех заявок, для которых s4- f\. Жадный алгоритм или динамическое программирование?

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

Дискретная задача о рюкзаке (0-1 knapsack problem) состоит в следующем. Пусть вор пробрался на склад, на котором хранится га вещей. Вещь номер г стоит V{ долларов и весит W{ килограммов (vi и Wi - целые числа). Вор хочет украсть товара на максимальную сумму, причём максимальный вес, который он может унести в рюкзаке, равен W (число W тоже целое). Что он должен положить в рюкзак?

Непрерывная задача о рюкзаке (fractional knapsack problem) отличается от дискретной тем, что вор может дробить краденые товары на части и укладывать в рюкзак эти части, а не обязательно вещи целиком (если в дискретной задаче вор имеет дело с золотыми слитками, то в непрерывной - с золотым песком).

Обе задачи о рюкзаке обладают свойством оптимальности для подзадач. В самом деле, рассмотрим дискретную задачу. Вынув вещь номер j из оптимально загруженного рюкзака, получим решение задачи о рюкзаке с максимальным весом W - Wj и набором из га - 1 вещи (все вещи, кроме j-й). Аналогичное рассуждение проходит и для непрерывной задачи: вынув из оптимально загруженного рюкзака, в котором лежит w килограммов товара номер j, весь этот товар, получим оптимальное решение непрерывной задачи, в которой максимальный вес равен W - w (вместо W), а количество j-ro товара равно Wj - w (вместо Wj).

Хотя две задачи о рюкзаке и похожи, жадный алгоритм даёт оптимум в непрерывной задаче о рюкзаке и не даёт в дискретной. В самом деле, решение непрерывной задачи о рюкзаке с помощью жадного алгоритма выглядит так. Вычислим цены (в расчёте на килограмм) всех товаров (цена товара номер г равна Vi/wi). Сначала вор берёт по максимуму самого дорогого товара; если весь этот товар кончился, а рюкзак не заполнен, вор берёт следующий по цене товар, затем следующий, и так далее, пока не наберёт вес W. Поскольку товары надо предварительно отсортировать по ценам, на что уйдёт время О (га log п), время работы описанного алгоритма будет О (га log га). В упражнении 17.2-1 мы попросим вас доказать, что описанный алгоритм действительно дает оптимум.


Рис. 17.2 В дискретной задаче о рюкзаке жадная стратегия может не сработать, (а) Вор должен выбрать две вещи из трёх с тем, чтобы их суммарный вес не превысил 50 кг. (б) Оптимальный выбор - вторая и третья вещи; если положить в рюкзак первую, то выбор оптимальным не будет, хотя именно она дороже всех в расчёте на единицу веса, (в) Для непрерывной задачи о рюкзаке с теми же исходными данными выбор товаров в порядке убывания цены на единицу веса будет оптимален.

Чтобы убедиться в том, что аналогичный жадный алгоритм не обязан давать оптимум в дискретной задаче о рюкзаке, взгляните на рис. 17.2а. Грузоподъёмность рюкзака 50 кг, на складе имеются три вещи, весящие 10, 20 и 30 кг и стоящие 60, 100 и 120 долларов соответственно. Цена их в расчёте на единицу веса равна 6, 5 и 4. Жадный алгоритм для начала положит в рюкзак вещь номер 1; однако оптимальное решение включает предметы номер 2 и 3.

Для непрерывной задачи с теми же исходными данными жадный алгоритм, предписывающий начать с товара номер 1, даёт оптимальное решение (рис. 17.2в). В дискретной задаче такая стратегия не срабатывает: положив в рюкзак предмет номер 1, вор лишается возможности заполнить рюкзак «под завязку», а пустое место в рюкзаке снижает цену наворованного в расчёте на единицу веса. При решении дискретной задачи о рюкзаке, чтобы решить, класть ли данную вещь в рюкзак, надо сравнить решение подзадачи, возникающей, если данная вещь заведомо лежит в рюкзаке, с подзадачей, возникающей, если этой вещи в рюкзаке заведомо нет. Тем самым дискретная задача о рюкзаке порождает множество перекрывающихся подзадач - типичный признак того, что может пригодиться динамическое программирование. И действительно, к дискретной задаче о рюкзаке оно применимо (см. упражнение 17.2-2).

Упражнения

17.2-1 Докажите, что для непрерывной задачи о рюкзаке выполнен принцип жадного выбора.



[стр.Начало] [стр.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] [стр.294]