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

Жадный алгоритм - алгоритм, на каждом этапе выполнения которого принимаются локально наилучшие решения.

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

Применимость

Известно, что достаточным условием корректности применения жадного алгоритма является условие, что структура задачи является матроидом.

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

  1. $\varnothing \in I$.
  2. Если $A\in I$ и $B\subset A$, то $B\in I$.
  3. Если $A,B\in I$ и мощность A больше мощности B, то существует $x\in A\setminus B$ такой, что $B\cup \{x\}\in I$.

Базами матроида называются максимальные по включению независимые множества. Подмножества $X$, не принадлежащие $I$, называются зависимыми множествами. Минимальные по включению зависимые множества называются циклами матроида.

Тем не менее, общего критерия применимости жадного алгоритма для решения конкретной задачи не существует, однако для задач, решаемых жадными алгоритмами, характерны две особенности:

  1. к ним применим Принцип жадного выбора
  2. они обладают свойством Оптимальности для подзадач

Принцип жадного выбора

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

  1. Доказывается, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не хуже первого.
  2. Показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной.
  3. Рассуждение завершается по индукции.

Оптимальность для подзадач

Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач.

Примеры классических жадных алгоритмов

  1. Алгоритм Дейкстры - находит кратчайшие пути от одной из вершин графа до всех остальных.
  2. Алгоритм Хаффмана - алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.
  3. Алгоритм Крускала - алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.
  4. Алгоритм Прима - алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.

Примеры задач

Размен монет

Монетная система некоторого государства состоит из монет достоинством $a_{1}=1<a_{2}<...<a_{n}$. Требуется выдать сумму $S$ наименьшим возможным количеством монет.

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства $a_{n}: x_{n}=\lfloor \frac{S}{a_{n}}\rfloor$ . Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение, а только для некоторых, называемых каноническими, монетных систем, вроде используемых в США (1, 5, 10, 25 центов). Неканонические системы таким свойством не обладают. Так, например, сумму в 24 копейки монетами в 1, 5 и 7 коп. жадный алгоритм разменивает так: 7 коп. — 3 шт., 1 коп. — 3 шт., в то время как правильное решение — 7 коп. — 2 шт., 5 коп. — 2 шт.

In [1]:
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;
In [2]:
std::map<int, int> greed_money(std::vector<int> a, int S) {
    map<int, int> res;
    for (int i = a.size() - 1; i >= 0; --i) {
        if (S >= a[i]) {
            res[a[i]] = S / a[i];
            S = S%a[i];
        }
    }
    return res;
}
In [3]:
void print_map(std::map<int,int> m){
    for (auto i : m) {
        cout << i.first << ':' << i.second << endl;
    }
}
In [4]:
{
    int S;
    std::vector<int> a = { 1, 2, 5, 10, 25};
    cin >> S;
    auto m=greed_money(a, S);
    print_map(m);
}
24
2:2
10:2
In [5]:
{
    int S;
    std::vector<int> a = { 1, 5, 7};
    cin >> S;
    auto m=greed_money(a, S);
    print_map(m);
}
24
1:3
7:3

Выбор заявок

Даны $n$ заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия ($s_{i}$ и $f_{i}$ для $i$-й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами $i$ и $j$ совместны, если интервалы $[s_{i},f_{i})$ и $[s_{j},f_{j})$ не пересекаются (то есть $f_{i}\leq s_{j}$ или $f_{j}\leq s_{i}$).

Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

Приведём жадный алгоритм, решающий данную задачу. При этом полагаем, что заявки упорядочены в порядке возрастания времени окончания. Если это не так, то можно отсортировать их за время $O(n \log n)$; заявки с одинаковым временем конца располагаем в произвольном порядке.

In [6]:
typedef struct {int s; int f;} interval;
In [7]:
bool intersects(interval a, interval b){
    return a.f<=b.s || a.s<=b.f;
}
In [8]:
bool cmp_interval(interval a,interval b){
    return a.f<b.f;
}
In [9]:
void ActivitySelector(std::vector<interval> sf){
    std::sort(sf.begin(), sf.end(), cmp_interval);    
    std::set<int> A = {0};
    int j = 0;
    for(int i = 1; i < sf.size(); i++){
        if(sf[i].s >= sf[j].f){
            A.insert(i);
            j = i;
        }
    }
    for(auto i : A){
        cout << "[" << sf[i].s << "-" << sf[i].f << ")" << endl;
    }
}
In [10]:
{
    vector<interval> a={{1,3},{3,6},{3,5},{5,6},{1,2},{2,3}};
    ActivitySelector(a);
}
[1-2)
[2-3)
[3-5)
[5-6)

На вход данному алгоритму подаются массивы начала и окончания занятий. Множество $A$ состоит из номеров выбранных заявок, а $j$ — номер последней заявки. Жадный алгоритм ищет заявку, начинающуюся не ранее окончания $j$-той, затем найденную заявку включает в $A$, а $j$ присваивает её номер. Таким образом, каждый раз мы выбираем то (ещё не начавшееся) занятие, до конца которого осталось меньше всего времени.

Алгоритм работает за $O(n\log n+n)$, то есть сортировка плюс выборка. На каждом шаге выбирается наилучшее решение. Покажем, что в итоге получится оптимум.

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

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

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

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

In [11]:
typedef struct{int end; int cost;} task;
In [12]:
bool cmp_task(task a, task b){
    return a.cost>b.cost;
}
In [13]:
void TaskSelector(std::vector<task> tasks){
    std::sort(tasks.begin(),tasks.end(),cmp_task);
    
    //for(auto i=tasks.begin();i<tasks.end();i++)
    //    cout << i->end <<" "<<i->cost <<endl;
    
    std::map<int,int> time;
    for(int i=0;i<tasks.size();i++)
        time[i]=-1;
    
    for(int i=0;i<tasks.size();i++){
        bool f=true;        
        for(int j=tasks[i].end;j>=0 && f;j--)
            if(time[j]==-1){
                time[j]=i;
                f=false;
            }
        if(f){
            for(int j=tasks.size()-1;f;j--){
                if(time[j]==-1){
                    f=false;
                    time[j]=i;
                }
            }
        }
    }
    
    cout <<"?t:e-c"<<endl;
    for(auto [t, i] : time){
        if(tasks[i].end>=t)
            cout <<"+"<< t<<":"<< tasks[i].end << "-" << tasks[i].cost << endl;
        else
            cout <<"-"<< t<<":"<< tasks[i].end << "-" << tasks[i].cost << endl;
    }
}
In [14]:
{
    std::vector<task> ts={{1,2},{0,3},{2,3},{2,1},{2,4},{4,3},{4,2},{4,1}};
    TaskSelector(ts);
}
?t:e-c
+0:0-3
+1:2-3
+2:2-4
+3:4-2
+4:4-3
-5:4-1
-6:2-1
-7:1-2
In [ ]: