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

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

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

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

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


    Итак, жадный алгоритм (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 на другую структуру).
    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 17
    • +8
      день алгоритмов на хабре, спасибо за статью
      • +13
        студенты готовятся к экзаменам
      • +1
        У роботов-продавцов точно будет устанавливаться такой алгоритм :) Спасибо вам за полезную информацию.
        • +3
          Неплохо было бы еще привести пример, в котором очевидная жадность не является правильным решением (к примеру, задача о рюкзаке).
          В целом — отличная статья, спасибо.
          • 0
            Для рюкзака есть эвристика, дающая доказанную эффективность максимум 11/9 от оптимального результата, только вот является ли она жадным алгоритмом?
          • –1
            Торт!
            • +2
              Помню в свое время на российской олимпиаде по информатике было задание запрограммировать игру Filler. Среди тестов были тесты на жадность, поэтому жадные программы (т.е. на каждом ходу «присоединяющие» максимальное количество квадратов) получали только половину баллов. Максимальное количество баллов получали те программы, которые учитывали поведение соперника и избирали ту или иную стратегию: если не успевают добраться до «куша» раньше соперника, то начинают есть жадно все, что вокруг.
              • +1
                Вот пример задачи, где не срабатывает жадность и даже рекурсивный перебор.
              • +3
                «Если множества A и B принадлежат множеству I, а также известно, что размер А меньше B, то существует какой-нибудь элемент из B, не принадлежащий А, который будет принадлежать множеству I.» — меня как-то смутила эта фраза. Всё-таки принадлежать множеству I будет не сам элемент (назовём x), а Union[A,{x}]. В формуле всё верно, а вот расшифрофку стоит подправить на мой взгляд.
                А статья классная, да.
                • 0
                  О да, это точно. В противном случае каждая вторая NP-полная задача решалась бы перебором.

                  Спасибо, исправил!
                • +1
                  Сам по себе жадный алгоритм имплементится примерно вот так

                  имплементится

                  Я, конечно, не то чтобы борец за чистоту русского языка, но ЭТО…
                  • +4
                    Ой, да ладно вам, мы тут суржик читаем и не ругаемся, а вы к слэнгу прицепились =)
                    • +1
                      буквально вчера я сдавал перевод по английскому языку и препод удивлялась, почему я никак не хочу переводить слово «Random».

                      За сленг извините, исправил.
                    • 0
                      Странно, что вы отнесли алгоритм Дейкстры к жадным. Это тоже пример реализации метода динамического программирования и практически прямого использования уравнения Беллмана.
                      • 0
                        ну то есть жадным его конечно тоже вполне можно назвать, но все же не такой яркий пример. Наверно лучше бы вспомнить задачу о ранце или типа того.
                      • 0
                        Спасибо за статью :) Вспомнились мои олимпиады по программированию, когда судорожно решал — писать за 10 минут жадное решение и приступать к другим задачам, либо додумывать правильное решение и писать его непонятно сколько времени =)
                        • 0
                          Жизнь, матроиды, конечные автоматы… ИТМО какое-то.

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.