Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 100
Текст из файла (страница 100)
460 Части ГК усовершенствованные методы разработки и аназиза Сравнение жадных алгоритмов и динамического программирования Поскольку свойство оптимальной подструктуры применяется и в жадных алгоритмах, и в стратегии динамического программирования, может возникнуть соблазн разработать решение в стиле динамического программирования для задачи, в которой достаточно применить жадное решение. Не исключена также возможность ошибочного вывода о применимости жадного решения в той ситуации, когда необходимо решать задачу методом динамического программирования.
Чтобы проиллюстрировать тонкие различия между этими двумя методами, рассмотрим две разновидности классической задачи оптимизации. Дискретная задача о рюкзаке (0-1 )спарзас1г ргоЫеш) формулируется следующим образом. Вор во время ограбления магазина обнаружил и предметов. Предмет под номером з имеет стоимость гь и вес и,, где н оы и зо, — целые числа. Нужно унести вещи, суммарная стоимость которых была бы как можно большей, однако грузоподъемность рюкзака ограничена и равна Иг, где Из — целая величина.
Какие предметы следует взять с собой? (Предмет не может быть разделен на части или взят более одного раза.) Ситуация в контннуаньной задаче о рюкзаке (Ггасг(опа! )гпарзаск ргоЫеш) та же, но теперь тот илн иной товар вор может брать с собой частично, а не делать каждый раз бинарный выбор — брать или не брать (О-1). В дискретной задаче о рюкзаке в роли предметов могут выступать, например, слитки золота, а для контннуальной задачи лучше подходят такие товары, как золотой песок.
В обеих разновидностях задачи о рюкзаке проявляется свойство оптимальной подструктуры. Рассмотрим в дискретной задаче наиболее ценную загрузку, вес которой не превышает И'. Если вынуть из рюкзака предмет под номером у, то остальные предметы должны быть наиболее ценными; при этом их вес не должен превышать И' — ю и их можно составить из и — 1 исходных предметов, из множества которых исключен предмет под номером у. Для аналогичной континуальной задачи можно привести такие же рассуждения. Если удалить из оптимально загруженного рюкзака часть товара с индексом Г, которая весит ш, остальное содержимое рюкзака будет наиболее ценным и состоящим из и — 1 исходных товаров, вес которых не превышает величину Из — ш плюс и — ш кг товара с индексом з) Несмотря на сходство сформулированных выше задач, континуальная задача о рюкзаке допускает решение на основе жадной стратегии, а дискретная — не допускает.
Чтобы решить континуальную задачу, вычислим сначала стоимость единицы веса и,/ш, каждого товара. Придерживаясь жадной стратегии, вор сначала загружает как можно больше товара с максимальной удельной стоимостью (стоимостью единицы веса). Если запас этого товара исчерпается, а грузоподъемность рюкзака — нет, он загружает как можно больше товара, удельная стоимость которого будет второй по величине. Так продолжается до тех пор, пока вес товара не достигает допустимого максимума.
Таким образом, вместе со временем сортировки товаров по нх удельной стоимости время работы алгоритма равно 0(п !яп). Доказательство того, что контннуальная задача о рюкзаке обладает свойством жадного выбора, предлагается провести в упражнении 16.2.1. Глава /6. Жадные аггоряя)иы бб/ $80 $120 П)няат З Прсягяг 2 )$6 $60 $!00 $!20 рьяны (а) $120 = $220 (б) (я) Рнс. 1(ьз. Контрпример, покатываюший, что жаднаа стратег)ш не работает в дискретной залаче о рюкзаке.
(в) Вор должен выбрать подмножество трех предметов, вес жпорых не должн превмшать 50 кг. (б) Оптимальное подмявкестяо включает предметы 2 и 3. Любое решение с предметом 1 не является оптимальным, несмотря на наивысшую удельную стоимость первого предмета. (в) В случае континуальной задачи о рюкзаке выбор товаров с наивысшей удельной стоимостью привози к оптимальному решению. Чтобы убедиться, что подобная жадная стратегия не работает в дискретной задаче о рюкзаке, рассмотрим пример, проиллюстрированный на рис.16.2,(а). Имеется 3 предмета и рюкзак, способный выдержать 50 кг. Первый предмет весит 10 кг и стоит 60 долларов. Второй предмет весит 20 кг и стоит 100 долларов.
Третий предмет весит 30 кг и стоит 120 долларов. Таким образом, один килограмм первого предмета стоит б долларов, что превышает аналогичную величину для второго (5 долларов/кг) н третьего (4 доллара/кг) предметов. Поэтому жадная стратегия должна состоять в том, чтобы сначала взять первый предмет. Однако, как видно из рис. 16.2, (б), оптимальное решение — взять второй и третий предметы, а первый — оставить. Оба возможных решения, включающих в себя первый предмет, не являются оптимальными. Однако для аналогичной континуальной задачи жадная стратегия, при которой сначала за(ружается первый товар, позволяет получить оптимальное решение, что продемонстрировано на рис. 16.2, (в). Если же сначала загрузить первый предмет в дискретной задаче, то невозможно будет загрузить рюкзак до отказа и оставшееся пустое место принедет к снижению эффективной стоимости единицы веса при такой загрузке.
Принимая в дискретной задаче решение о том, следует ли помещать тот или иной предмет в рюкзак, необходимо сравнить решение подзадачи, в которую входит этот предмет, с решением подзадачи, в которой он отсутствует, и талью после этого можно делать выбор. В сформулированной таким образом задаче возникает множество перекрывающихся подзадач, что служит признаком применимости динамического программирования.
И в самом деле, целочисленную задачу о рюкзаке можно решить с помощью динамичесюго программирования (см. упр. 16.2.2). 4б1 Часть ГК Ушвершенствованные методы разработки и аназиза Упражнении 1621 Докажите, что континуальная задача о рюкзаке обладает свойством жадного выбора. и.г.г Разработайте решение дискретной задачи о рюкзаке с помощью динамического программирования. Время работы вашего алгоритма должно быть равно 0(зз И'), где зз — количество предметов, а И' — максимальный вес предметов, которые вор может положить в свой рюкзак. и.г.з Предположим, что в дискретной задаче о рюкзаке порядок сортировки по увеличению веса совпадает с порядком сортировки по уменьшению стоимости. Сформулируйте эффективный алгоритм для поиска оптимального решения этой разновидности задачи о рюкзаке и обоснуйте его корректность.
16.2.4 Профессор едет из Киева в Москву на автомобиле. У него есть карта, на которой обозначены все заправки и указаны расстояния между ними. Известно, что если топливный бак заполнен, то автомобиль может проехать и километров (дорога достаточно ровная, так что расход топлива везде одинаков). Профессору хочется как можно реже останавливаться на заправках. Сформулируйте эффективный метод, позволяющий профессору определить, на каких заправках следует заливать топливо, чтобы количество остановок было минимальным. Докажите, что разработанная стратегия дает оптимальное решение, и определите время работы вашего алгоритма.
16.2.5 Разработайте эффективный алгоритм, который по заданному множеству (хм кз,...,кн) действительных точек на числовой прямой позволил бы найти минимальное множество закрытых интервалов единичной длины, содержащих все эти точки. Обоснуйте корректность алгоритма. 16.2.6 * Покажите, как решить непрерывную задачу о рюкзаке за время 0(п).
и.г. у Предположим, что имеется два множества, А и В, каждое из которых состоит из п положительных целых чисел. Порядок элементов каждого множества можно менять произвольным образом. Пусть а, — зчй элемент множества А, а 6, — зтй элемент множества В после переупорядочения. Рассмотрим величину П,", а,ь*. Сформулируйте алгоритм, который бы максимизировал эту величину. Докажите, что ваш алгоритм действительно максимизирует указанную величину, и определите время его работы. гбу !яаеа !б.
Жадные азгараньны 16.3. Коды Хаффмаиа Коды Хаффмана (Ни(ушап седея) — очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20 до 90;4 объема. Мы рассматриваем данные, представляющие собой последовательность символов. В жадном алгоритме Хаффмана используется таблица, содержащая частоты появления тех или иных символов. С помощью этой таблицы определяется оптимальное представление каждого символа в виде бинарной строки. Предположим, что имеется файл данных, состоящий из 100 тысяч символов, который требуется сжать.
Символы в этом файле встречаются с частотой, представленной на рис. 16.3. Таким образом, всего файл содержит шесть различных символов, а, например, символ а встречается в нем 45 тысяч раз. а Ь с 6 е Е Частота, тысяч 45 13 12 16 9 5 Кодовое слово фиксированной длины 000 001 010 011 100 101 Кодовое слово переменной длины 0 101 100 111 1101 1100 Рис. 1б.З. Задача о кодировании последовательности символов. Файл данных содержит толью символы а-Г с указанными частотами. Если назначить каждому символу трюбитовое юдовое слово, файл можно закодировать с помощью 300 тысяч битов. При использовании показаниям кодовых слов переменной двины файл кодируется толью 224 тысячами битов. Существует множество способов представить подобный файл данных.
Рассмотрим задачу по разработке бинарного символьного кода (Ьшагу с)загас1ег соде; или для краткости — просто «од), в котором каждый символ представляется уникальной бинарной строкой. Если используется код фиксированной длнны, нли равномерный код (11хеб-1епяйз соде), в котором каждый символ представлен уникальной бинарной строкой, то для представления шести символов понадобится три бита: а = 000, Ь = 001, ..., У = 101. При использовании такого метода для кодирования всего файла понадобится 300 тысяч битов. Можно ли добиться лучших результатов? С помощью кода переменной длнны, или иеравнаыериого иода (уапаЫе-! епйГ)з соде), удается получить значительно лучшие результаты, чем с помощью кода фиксированной длины.
Это достигается за счет того, что часто встречающимся символам сопоставляются короткие кодовые слова, а редко встречающимся — длинные. Такой код представлен на рис. 16.3. В нем символ а представлен 1-битовой строкой О, а символ 6 — 4-битовой строкой 1100. Для представления файла с помощью этого кода потребуется (45 1+ 13 3+ 12 3+ 16 3+ 9 4+ 5 4) 1000=224000битов. Благодаря этому экономится 25о4 объема. Кстати, как мы вскоре убедимся, для рассматриваемого файла это оптимальная кодировка символов. Часть з'У. Усовершенствованные методы разработки и анавиза Префиксные коды Здесь мы рассматриваем только те коды, в которых никакое кодовое слово не является префиксом какого-то другого кодового слова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
