Алгоритмы - построение и анализ (1021735), страница 92
Текст из файла (страница 92)
Не исключена также возможность ошибочного вывода о применимости жадного решения в той ситуации, когда необходимо решать задачу методом динамического программирования. Чтобы проиллюстрировать тонкие различия между этими двумя методами, рассмотрим две разновидности классической задачи оптимизации. Дискретнал задача о рюкзаке (0-1 кпарзаск ргоЫеш) формулируется следующим образом.
Вор во время ограбления магазина обнаружил и предметов. Предмет под номером г имеет стоимость пг грн. и вес иг кг, где и оо и иг — целые числа. Нужно унести вещи, суммарная стоимость которых была бы как можно большей, однако грузоподъемность рюкзака ограничивается И' килограммами, где И' — целая величина. Какие предметы следует взять с собой? Ситуация в непрерывной задаче о рюкзаке (1гасг1опа1 кпарзаск ргоЫегп) та же, но теперь тот или иной товар вор может брать с собой частично, а не делать каждый раз бинарный выбор — брать или не брать (0-1).
В дискретной задаче о рюкзаке в роли предметов могут выступать, например, слитки золота, а для непрерывной задачи больше подходят такие товары, как золотой песок. В обеих разновидностях задачи о рюкзаке проявляется свойство оптимальной подструктуры. Рассмотрим в целочисленной задаче наиболее ценную загрузку, вес которой не превышает И' кг. Если вынуть из рюкзака предмет под номером у', то остальные предметы должны быть наиболее ценными, вес которых не превышает Иг — ш и которые можно составить из п — 1 исходных предметов, из множества Глава 16. Жадные алгоритмы 457 11реене~ О ~ 20 е1п 11релнее 2 Г '1 11рен ~ее! 1 ~ 130 В Е3 'ы !2000 ЮО еен 100 е1нн 00 21ен — 100:рн -.
100нен. ы -- 220 ~ рн -.е0 00 ~рн 100 ~рн 120 ~рю Ркекеек н1 Рнс. 16.2. Жадная стратегия не работает лля дискретной задачи о рюкзаке которых исключен предмет под номером 5'. Для аналогичной непрерывной задачи можно привести такие же рассуждения. Если удалить из оптимально загруженного рюкзака товар с индексом 2, который весит еее кг, остальное содержимое рюкзака будет наиболее ценным, состоящим из и — 1 исходных товаров, вес которых не превышает величину И~ — и плюс и — и кг товара с индексом у. Несмотря на сходство сформулированных выше задач, непрерывная задача о рюкзаке допускает решение на основе жадной стратегии, а дискретная — нет.
Чтобы решить непрерывную задачу, вычислим сначала стоимость единицы веса 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 объема. Кстати, как мы вскоре убедимся, для рассматриваемого файла это оптимальная кодировка символов. Префиксные коды Мы рассматриваем только те коды, в которых никакое кодовое слово не является префиксом какого-то другого кодового слова. Такие коды называются префикс- ными (ргебх содев)~. Можно показать (хотя здесь мы не станем этого делать), что оптимальное сжатие данных, которого можно достичь с помощью кодов, всегда достижимо при использовании префиксного кода, поэтому рассмотрение одних лишь префиксных кодов не приводит к потере общности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
