Pull to refresh

Жадные алгоритмы

Reading time 4 min
Views 183K
ДеньгиДоброго времени суток, хабр! Сегодня я бы хотел рассказать про жадные алгоритмы.

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

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

Жадность не порок


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

К слову, алгоритм Флойда, который тоже ищет кратчайшие пути в графе (правда, между всеми вершинами), не является примером жадного алгоритма. Флойд демонстрирует другой метод — метод динамического программирования.

Использование жадного алгоритма довольно стандартное. Рассмотрим его на примере следующей задачи:

Задача о расписании


Пусть программисту-фрилансеру Васе Пупкину дано n заданий. У каждого задания известен свой дедлайн, а также его стоимость(то есть если он не выполняет это задание, то он теряет столько-то денег). Вася настолько крут, что за один день может сделать одно задание. Выполнение задания можно начать с момента 0. Нужно максимизировать прибыль.

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

Получается следующий код:

//tasks - массив заданий
Arrays.sort(tasks); //сортируем по убыванию стоимости
TreeSet<Integer> time = new TreeSet<Integer>();
for (int i = 1; i <= n; ++i) {
  time.add(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
  Integer tmp = time.floor(tasks[i].time);
  if (tmp == null) { // если нет свободного места в расписании, то в конец
  time.remove(time.last());
  } else { //иначе можно выполнить задание, добавляем в расписание
    time.remove(tmp);
    ans += tasks[i].cost;
  }
}




Когда можно быть жадным?


Всегда Иногда может возникнуть искушение использовать жадину везде, где только это возможно, но на некоторых задачах это неприемлимо. К примеру, задача о рюкзаке: вор пробрался на склад, в котором хранятся три вещи весом 10 кг, 20 кг и 30 кг и стоимостью 60, 100 и 120 деревянных вечнозеленых нанорублей соответственно. Вор максимум может унести 50 кг. Нужно максимизировать прибыль вора. Если поступать здесь жадно и выбирать самую ценную вещь(то есть, 6 нанорублей за кг первой штуки, 5 нанорублей за кг второй и 4 нанорубля за кг третьей), то вор по-любому должен взять первую вещь, потом останется место для второй вещи, однако оптимальное решение составляет вторая и третья вещь.

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

Жизнь не матроид, жизнь — конечный автомат!


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


  1. Множество I непусто. Даже если исходное множество X было пусто — X = Ø, то I будет состоять из одного элемента — множества, содержащего пустое. I = {{Ø}}

  2. Любое подмножество любого элемента множества I также будет элементом этого множества.

  3. Если множества A и B принадлежат множеству I, а также известно, что размер А меньше B, то существует какой-нибудь элемент x из B, не принадлежащий А, такое что объединение x и A будет принадлежать множеству I. Это свойство является не совсем тривиальным, но чаще всего наиважшейшим из всех остальных.

Матроид называется взвешенным, если на множестве X существует аддитивная весовая функция w. Вес множества будет определяться как сумма весов его элементов.

Вернемся к нашим баранам программисту-фрилансеру с заданиями. Здесь можно разглядеть следующий матроид: пусть носителем будет множество заданий, а независимыми множествами — успешно выполненные задания. Весом каждой заявки пусть будет его стоимость. Проверим, является ли данная пара матроидом:
  1. первое свойство, очевидно, выполняется. Пустое множество выполненных заданий входит в наше множество. Ну и пофиг, что Вася не хочет зарабатывать деньги.
  2. второе множество тоже выполняется. Почему это так: давайте отсортируем успешно выполненные задания в порядке увеличения дедлайна. В таком порядке они все равно будут успешно выполненными. В таком порядке очевидно, что любое подмножество успешно выполненных заданий будет успешно выполнено.
  3. третье свойство, хоть и не очевидно, но выполняется. Пусть у нас есть два множества успешно выполненных заданий A и B, при чем известно, что |A| < |B|. Стандартно отсортируем задания в порядке увеличения дедлайна в обоих множествах. Возьмем задание из B, которого нет в A, и попробуем добавить его к множеству A. Это у нас получится, ведь если бы в А не было пробела, то данное задание должно было присутствовать.


К чему это я? Вся прелесть матроидов заключается в теореме Радо-Эдмондса: если доказать, что объект является матроидом, то жадный алгоритм будет работать корректно и выдавать правильный результат.

Сам по себе жадный алгоритм реализуется примерно вот так:

//отсортируем по весу
//вначале ответом будет пустое множество
for to
   if then //если подходит
       //то включаем в множество

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




PS


Кстати, задачу о расписаниях можно решить и быстрее за O(n). Кому не слабо? (Подсказка: нужно заменить TreeSet на другую структуру).
Tags:
Hubs:
+94
Comments 17
Comments Comments 17

Articles