Реферат: Методы разработки алгоритмов. Жадные алгоритмы

Жадный алгоритм или динамическое программирование?

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

Дискретная задача о рюкзаке (0-1 knapsackproblem) состоит в следующем. Пусть вор пробрался на склад, на котором хранится n вещей. Вещь номер i стоит v_i долларов и весит w_i килограммов (v_i и w_i - целые числа). Вор хочет украсть товара на максимальную сумму, причем максимальный вес, который он может унести в рюкзаке, равен W ( число W тоже целое). Что он должен положить в рюкзак?

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

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

Хотя две задачи о рюкзаке и похожи, жадный алгоритм дает оптимум в непрерывной задаче о рюкзаке и не дает в дискретной. В самом деле, решение непрерывной задачи о рюкзаке с помощью жадного алгоритма выглядит так. Вычислим цены (в расчете на килограмм) всех товаров (цена товара номер i равна v_i / w_i ). Сначала вор берет по максимуму самого дорогого товара; если весь этот товар кончился, а рюкзак не заполнен, вор берет следующий по цене товар, затес следующий, и так далее, пока не наберет вес W. Поскольку товары надо предварительно отсортировать по ценам, на что уйдет время О(n logn ), время работы описанного алгоритма будет О(n logn ).

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

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

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

Заключение.

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

-Сократить время принятия решения

-Проверять все возможные варианты решения на данный момент времени.

Литература

1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 16. Жадные алгоритмы

2. Кормен Т и др. Алгоритмы: построение и анализ. – М.: МЦНМО, 2000

3. Алфёрова З.В. Теория алгоритмов. – М.: Статистика, 1973