Использование жадных алгоритмов на примере задачи о воре

Тема: Использование жадных алгоритмов на примере задачи о воре.

 

Содержание

 

 

Введение

 

Постоянный рост сложности  решаемых задач в программировании и увеличивающегося объема обрабатываемой информации приводит к необходимости упрощения используемых алгоритмов программы. Поэтому существуют класс задач, для которых разработаны стандартные методы построения и требования к их использованию. Одним из таких классов задач являются задачи об оптимизации. Алгоритмы, предназначенные для решения задач оптимизации, обычно представляют собой последовательность шагов, на каждом из которых предоставляется некоторое множество выборов. Так, например, определение наилучшего решения, руководствуясь принципами динамического программирования, во многих задачах оптимизации слишком затратно - для этих задач лучше подходят более простые и эффективные алгоритмы.

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

 

1. Описание жадных алгоритмов

 

Жадный метод обладает достаточной мощью и хорошо подходит для довольно широкого класса задач. Он реализуется посредством множества алгоритмов, среди которых алгоритмы поиска минимальных остовных деревьев, алгоритм Дейкстры для определения кратчайших путей из одного источника и эвристический жадный подход Чватала к задаче о покрытии множества. Алгоритмы поиска минимальных остовных деревьев являются классическим примером применения жадного метода.

Жадный алгоритм позволяет получить оптимальное решение задачи путем осуществления ряда выборов. В каждой точке принятия решения в алгоритме делается выбор, который в данный момент выглядит самым лучшим. Эта эвристическая стратегия не всегда дает оптимальное решение, но все же решение может оказаться и оптимальным. Процесс разработки жадных алгоритмов можно представить в виде последовательности этапов:

1) привести задачу оптимизации к виду, когда после сделанного выбора остается решить только одну подзадачу;

2) доказать, что всегда существует такое оптимальное решение исходной задачи, которое можно получить путем жадного выбора, так что такой выбор всегда допустим;

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

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

Первый из названных выше основных составляющих жадного алгоритма свойство жадного выбора: глобальное оптимальное решение можно получить, делая локальный оптимальный (жадный) выбор. Другими словами, рассуждая по поводу того, какой выбор следует сделать, мы делаем выбор, который кажется самым лучшим в текущей задаче; результаты возникающих подзадач при этом не рассматриваются.

Оптимальная подструктура проявляется в задаче, если в ее оптимальном решении содержатся оптимальные решения подзадач. Это свойство является основным признаком применимости, как динамического программирования, так и жадных алгоритмов. В качестве примера приведем оптимальную подструктуру выбора процесса. Если оптимальное решение подзадачи S_ij содержит процесс a_k, то оно также содержит оптимальные решение подзадач S_ik и S_kj. После выявления этой оптимальной подструктуры было показано, что если известно, какой процесс используется в качестве процесса a_k, то оптимальное решение задачи S_ij можно построить путем выбора процесса a_k и объединения его со всеми процессами в оптимальных решениях подзадач S_ik и S_kj. На основе этого наблюдения удается получить рекуррентное соотношение, описывающее оптимальное решение. Обычно при работе с жадными алгоритмами применяется более простой подход. Как уже упоминалось, мы воспользовались предположением, что подзадача получилась в результате жадного выбора в исходной задаче. Все, что осталось сделать, - это обосновать, что оптимальное решение подзадачи в сочетании с ранее сделанным жадным выбором приводит к оптимальному решению исходной задачи. В этой схеме для доказательства того, что жадный выбор на каждом шаге приводит к оптимальному решению, неявно используется индукция по вспомогательным задачам.

Рассмотрим отличие  жадных алгоритмов от динамического программирования. В динамическом программировании на каждом этапе делается выбор, однако обычно этот выбор зависит от решений подзадач. Следовательно, методом динамического программирования задачи обычно решаются в восходящем направлении, т.е. сначала обрабатываются более простые подзадачи, а затем - более сложные. В жадном алгоритме делается выбор, который выглядит в данный момент наилучшим, после чего решается подзадача, возникающая в результате этого выбора. Выбор, сделанный в жадном алгоритме, может зависеть от сделанных ранее выборов, но он не может зависеть от каких бы то ни было выборов или решений последующих подзадач. Таким образом, в отличие от динамического программирования, где подзадачи решаются в восходящем порядке, жадная стратегия обычно разворачивается в нисходящем порядке, когда жадный выбор делается один за другим, в результате чего каждый экземпляр текущей задачи сводится к более простому.

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

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

Свойство жадного выбора часто дает определенное преимущество, позволяющее повысить эффективность выбора в подзадаче. Зачастую оказывается, что благодаря предварительной обработке входных данных или применению подходящей структуры данных (нередко это очередь с приоритетами) можно ускорить процесс жадного выбора, что приведет к повышению эффективности алгоритма.

 

2. Алгоритм жадного метода  на примере задаче о воре

 

Задача: вор, пробравшись в хранилище банка, обнаружил N мешков золотого песка, но стоимость мешков была разной из-за проб золота в них (C[i]). Вес мешков тоже различался (M[i]). Поднять вор может только X кг (перед операцией его от волнения стукнул радикулит). Помогите бедному вору выбрать наиболее драгоценный груз.

 

Решение: В задаче о воре проявляется свойство оптимальной подструктуры. Рассмотрим в задаче наиболее ценную загрузку, вес которой не превышает X кг. Если удалить из оптимально загруженного рюкзака товар с индексом j, который весит m кг, остальное содержимое рюкзака будет наиболее ценным, состоящим из N − 1 исходных товаров, вес которых не превышает величину X − m плюс M[j] − m кг товара с индексом j.

Чтобы решить задачу, вычислим сначала стоимость единицы веса C[i]/M[i] каждого товара. Придерживаясь жадной стратегии, вор сначала загружает как можно больше товара с максимальной удельной стоимостью (за единицу веса). Если запас этого товара исчерпается, а грузоподъемность - нет, он загружает как можно больше товара, удельная стоимость которого будет второй по величине. Так продолжается до тех пор, пока вес товара не достигает допустимого максимума. Таким образом, вместе с сортировкой товаров по их удельной стоимости время работы алгоритма равно O (n lg n).

 

Алгоритм:

1) Расчет для каждого  мешка удельной стоимости Cm[i] = С[i]/M[i];

2) Сортировка удельных стоимостей по убыванию в массиве CmSort;

3) Выбор очередного мешка из отсортированного массива CmSort;

4) Если максимальный  груз не превышен, и если есть еще мешки, переход к шагу 3;

5) Если максимальный груз превышен, из последнего мешка отсыпается максимально возможное количество золота;

Рисунок 1. Схема алгоритма  задачи о воре

3. Программная реализация жадного алгоритма

 

Программа расчета начинается с предложения ввода количества мешков. Как только вводится количество мешков, генерируются значения веса и пробы для каждого мешка. Далее список сгенерированных значений выводится на экран. После этого по имеющимся данным производится жадный выбор, и выводятся значения итоговой стоимости мешков и массы, которую удается унести вору (в программе установлена переменная, которая определяет допустимый вес, это значение равно 10 кг). Результат работы программы представлен на рисунке 2.

 

Рисунок 2. Результат работы программы

 

Исходный код  программы:

 

program GreedyAlgorytm;

 

uses

  Classes, math;

 

{$R *.res}

 

type

  TGoldBag = record

    KgCost: Double;

    Mass: Double;

  end;

 

var

  I, J: Integer;

  N, X: Integer;

  McTemp: TGoldBag;

  M, C: array of Double;

  McSort: array of TGoldBag;

  GatheringCost, GatheringMass: Double;

begin

  Randomize;

  // ввод количества  мешков от 3 до 100

  WriteLn('Input N (gold count)');

  Readln(N);

  N := Max(N, 3);

  N := Min(N, 100);

 

  // создание массивов весов и проб мешков

  SetLength(McSort, N);

  SetLength(M, N);

  SetLength(C, N);

 

  // генерация данных о мешках

  X := 10;

  for I := 0 to N - 1 do

  begin

    M[I] := 0.5 + Random * 3;

    C[I] := 100 + Random(1000);

  end;

 

  // расчет удельной  стоимости

  for I := 0 to N - 1 do

  begin

    McSort[I].KgCost := C[I]/M[I];

    McSort[I].Mass := M[I];

  end;

 

  // простая сортировка  списка по удельной стоимости

  for I := 0 to N - 2 do

    for J := I + 1 to N - 1 do

      if McSort[I].KgCost < McSort[J].KgCost then

      begin

        McTemp := McSort[I];

        McSort[I] := McSort[J];

        McSort[J] := McTemp;

      end;

 

  // вывод удельной  стоимости и массы мешков

  WriteLn;

  WriteLn('Kg cost ($/kg) - Mass (kg)');

  for I := 0 to N - 1 do

  begin

    Write(McSort[I].KgCost:14:2);

    Write(' - ');

    WriteLn(McSort[I].Mass:5:2);

  end;

 

  // набираем золото  по жадному алгоритму

  GatheringMass := 0;

  GatheringCost := 0;;

  for I := 0 to N - 1 do

  begin

    if GatheringMass + McSort[I].Mass < X then

    begin

      // если  лезет - берем весь мешок

      GatheringCost := GatheringCost + McSort[I].KgCost * McSort[I].Mass;

      GatheringMass := GatheringMass + McSort[I].Mass;

    end else

    begin

      // если не лезет - отсыпаем максимум возможного

      // и считаем стоимость отсыпанного

      GatheringCost := GatheringCost + (X - GatheringMass) * McSort[I].KgCost;

      GatheringMass := X;

    end;

  end;

 

  // вывод результата

  WriteLn;

  Write('Result cost($) = ');

  WriteLn(GatheringCost:7:2);

  Write('Result mass(kg) = ');

  WriteLn(GatheringMass:7:2);

  Readln();

end.

 

Выводы

 

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

 

Список литературы

 

1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова — 2-е изд. — М.: Вильямс, 2005. — 1296 с.

2. Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2000

3. Д. Сэломон. Сжатие данных, изображения и звука. - М.: Техносфера, 2004. - 368 с.

4. Ананий В. Левитин. Алгоритмы: введение в разработку и анализ - М.: "Вильямс", 2006. 416 с.

5. Асанов М.О. и др. Дискретная математика: графы, матроиды, алгоритмы. - Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. 288 с.

6. Моисеев Н.Н. Методы оптимизации: Моисеев Н.Н., Иванилова Ю.П., Столярова Е.М.-М., 1978, 352 с

7. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. : Уч. пос. – М.: Издательский дом «Вильямс», 2000. – 384с.

8. Бобровский С.И. Delphi 7. Учебный курс. – С-Пб.: «Питер»., 2004. – 736 с.