Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 94
Текст из файла (страница 94)
Несмотря на сходство сформулированных выше задач, непрерывная задача о рюкзаке допускает решение на основе жадной стратегии, а дискретная — нет. Чтобы решить непрерывную задачу, вычислим сначала стоимость единицы веса 121/ю1 каждого товара. Придерживаясь жадной стратегии, вор сначала загружает как можно больше товара с максимальной удельной стоимостью (за единицу веса). Если запас этого товара исчерпается, а грузоподъемность рюкзака — нет, он загружает как можно больше товара, удельная стоимость которого будет второй по величине.
Так продолжается до тех пор, пока вес товара не достигает допустимого максимума. Таким образом, вместе с сортировкой товаров по их удельной стоимости время работы алгоритма равно О (п1кп). Доказательство того, что непрерывная задача о рюкзаке обладает свойством жадного выбора, предлагается провести в упражнении 16.2-1. Чтобы убедиться, что подобная жадная стратегия не работает в целочисленной задаче о рюкзаке, рассмотрим пример, проиллюстрированный на рис. 16.2а.
Имеется 3 предмета и рюкзак, способный выдержать 50 кг. Первый предмет весит 10 кг и стоит 60 грн. Второй предмет весит 20 кг и стоит 100 грн. Третий предмет весит 30 кг и стоит 120 грн. Таким образом, один килограмм первого предмета стоит 6 грн, что превышает аналогичную величину для второго (5 грн/кг) и третьего (4 грнlкг) предметов.
Поэтому жадная стратегия должна состоять в том„чтобы сначала взять первый предмет. Однако, как видно из рис. 16.26, оптимальное решение — взять второй и третий предмет, а первый — оставить. Оба возможных решения, включающих в себя первый предмет, не являются оптимальными. Однако для аналогичной непрерывной задачи жадная стратегия, при которой сначала загружается первый предмет, позволяет получить оптимальное решение, Часть 1Ч. Усовершенствованные методы разработки н анализа 458 как видно из рис. 16.2в. Если же сначала загрузить первый предмет в дискретной задаче, то невозможно будет загрузить рюкзак до отказа и оставшееся пустое место приведет к снижению эффективной стоимости единицы веса при такой загрузке. Принимая в дискретной задаче решение о том, следует ли положить тот или иной предмет в рюкзак, необходимо сравнить решение подзадачи, в которую входит этот предмет, с решением подзадачи, в которой он отсутствует, и только после этого можно делать выбор.
В сформулированной таким образом задаче возникает множество перекрывающихся подзадач, что служит признаком применимости динамического программирования. И в самом деле, целочисленную задачу о рюкзаке можно решить с помощью динамического программирования (см. упражнение 16.2-2). Упражнения 16.2-1. Докажите, что непрерывная задача о рюкзаке обладает свойством жадного выбора. 16.2-2. Приведите решение дискретной задачи о рюкзаке с помощью динамического программирования.
Время работы вашего алгоритма должно быль равно О (пИ'), где и — количество элементов, а И~ — максимальный вес предметов, которые вор может положить в свой рюкзак. 16.2-3. Предположим, что в дискретной задаче о рюкзаке порядок сортировки по увеличению веса совпадает с порядком сортировки по уменьшению стоимости. Сформулируйте эффективный алгоритм для поиска оптимального решения этой разновидности задачи о рюкзаке и обоснуйте его корректность.
16.2-4. Профессор едет из Киева в Москву на автомобиле. У него есть карта, где обозначены все заправки с указанием расстояния между ними. Известно, что если топливный бак заполнен, то автомобиль может проехать и километров. Профессору хочется как можно реже останавливаться на заправках. Сформулируйте эффективный метод, позволяющий профессору определить, на каких заправках следует заливать топливо, чтобы количество остановок оказалось минимальным. Докажите, что разработанная стратегия дает оптимальное решение. 16.2-5. Разработайте эффективный алгоритм, который по заданному множеству тхы хз,..., х„) действительных точек на числовой прямой позволил бы найти минимальное множество закрытых интервалов единичной длины, содержащих все эти точки.
Обоснуйте корректность алгоритма. * 16.2-6. Покажите, как решить непрерывную задачу о рюкзаке за время О (и). !6.2-7. Предположим, что имеется два множества, А и В, каждое из которых состоит из и положительных целых чисел. Порядок элементов каждого Глава 16. Жадные алгоритмы 459 множества можно менять произвольным образом. Пусть а; — г-й элемент множества А, а Ь; — г-й элемент множества В после переупорядочения. Составим величину П," а,'. Сформулируйте алгоритм, который бы максимизировал эту величину. Докажите, что ваш алгоритм действительно максимизирует указанную величину, и определите время его работы.
16.3 Коды Хаффмана Коды Хаффмана (Нцйпап содез) — широко распространенный и очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20'.4 до 90в4 объема. Мы рассматриваем данные, представляющие собой последовательность символов. В жадном алгоритме Хаффмана используется таблица, содержащая частоты появления тех или иных символов.
С помощью этой таблицы определяется оптимальное представление каждого символа в виде бинарной строки. Предположим, что имеется файл данных, состоящий из 100000 символов, который требуется сжать. Символы в этом файле встречаются с частотой, представленной в табл. 16.1. Таким образом, всего файл содержит шесть различных символов, а, например, символ а встречается в нем 45 000 раз. Таблица! 6.1.
Задача о кодировании последовательности символов а Ь с с1 е й Частота (в тысячах) 45 13 12 16 9 5 Кодовое слово фиксированной длины 000 001 010 011 100 101 Кодовое слово переменной длины 0 101 100 111 1101 1100 Существует множество способов представить подобный файл данных. Рассмотрим задачу по разработке бинарного кода символов (Ьшагу сЬагас1ег соде; или для краткости просто кода), в котором каждый символ представляется уникальной бинарной строкой. Если используется код фиксированной длины, или равномерный код (бхед-!ела соде), то для представления шести символов понадобится 3 бита: а = 000, Ь = 001,..., г" = 101. При использовании такого метода для кодирования всего файла понадобится 300000 битов.
Можно ли добиться лучших результатов? С помощью кода леременной длины, или неравномерного кода (чапаЫе- !епягЬ соде), удается получить значительно лучшие результаты, чем с помощью кода фиксированной длины. Это достигается за счет того, что часто встречающимся символам сопоставляются короткие кодовые слова„ а редко встречающимся— длинные. Такой код представлен в последней строке табл.
16.1. В нем символ а Часть!Ч. Усовершенствованные методы разработки и анализа 460 представлен 1-битовой строкой О, а символ Š— 4-битовой строкой 1100. Для представления файла с помощью этого кода потребуется (45 1+ 13 3+ 12. 3+ 16 3+ 9 4+ 5. 4) 1000 = 224000 битов. Благодаря этому дополнительно экономится 25'.4 объема. Кстати, как мы вскоре убедимся, для рассматриваемого файла это оптимальная кодировка символов. Префиксные коды Мы рассматриваем только те коды, в которых никакое кодовое слово не является префиксом какого-то другого кодового слова. Такие коды называются префикс- ными (ргебх содев)~. Можно показать (хотя здесь мы не станем этого делать), что оптимальное сжатие данных, которого можно достичь с помощью кодов, всегда достижимо при использовании префиксного кода, поэтому рассмотрение одних лишь префиксных кодов не приводит к потере общности. Для любого бинарного кода символов кодирование текста — очень простой процесс: надо просто соединить кодовые слова, представляющие каждый символ в файле.
Например, в кодировке с помощью префиксного кода переменной длины, представленного в табл. 16.1, трехсимвольный файл аЬс имеет вид 0 101 100 = = 0101100, где символом "'* обозначена операция конкатенации. Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла.
В рассматриваемом примере строка 001011101 однозначно раскладывается на подстроки 0 0 101 1101, что декодируется как ааЬе. Для упрощения процесса декодирования требуется удобное представление префиксного кода, чтобы кодовое слово можно было легко идентифицировать. Одним из таких представлений является бинарное дерево, листьями которого являются кодируемые символы. Бинарное кодовое слово, представляющее символ, интерпретируется как путь от корня к этому символу.
В такой интерпретации О означает "перейти к левому дочернему узлу", а 1 — "перейти к правому дочернему узлу". На рис. 16.3 показаны такие деревья для двух кодов, взятых из нашего примера. Каждый лист на рисунке помечен соответствующим ему символом и частотой появления, а внутренний узел — суммой частот листьев его поддерева. В части а рисунка приведено дерево, соответствующее коду фиксированной длины, где а = 000, ..., у' = 101. В части 6 показано дерево, соответствующее оптимальному префиксному коду а = О, Ь = 101, ..., г" = 1100. Заметим, Возможно, лучше подошло бы название "беспрефиксные коды", однако "префиксные коды"— стандартный в литературе термин. Глава 16. Жадные алгоритмы 461 600 ))) ! т:5 ) (в:9 ~ б) а) Рис. 16.3. Деревья, соответствующие схемам кодирования, приведенным в табл. 16.1 что изображенные на рисунке деревья не являются бинарными деревьями поиска, поскольку листья в них не обязательно расположены в порядке сортировки, а внутренние узлы не содержат ключей символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
