Към съдържанието
wannacode

Алчният алгоритъм и кога работи

Накратко: Алчният алгоритъм взима на всяка стъпка най-добрия избор в момента и не се връща; той дава оптималния отговор само в задачи, в които този избор е безопасен, а това се доказва, например с довода с размяната.

Проблем

Залата за срещи

Коуъркингът има една зала за срещи. За утре са дошли осем заявки, всяка с начален и краен час. Две срещи, които се застъпват, не могат да са в залата едновременно. Искаш да приемеш колкото се може повече екипи: всеки отказан отива при конкуренцията.

Първите идеи са прости правила: най-ранната заявка първо, или най-кратката първо (по-кратките заемат по-малко време). Подреждаш по правилото и приемаш всяка заявка, която не се застъпва с вече приетите:

static List<int[]> book(int[][] requests, Comparator<int[]> rule) {
    int[][] queue = requests.clone();
    Arrays.sort(queue, rule);
    List<int[]> taken = new ArrayList<>();
    for (int[] r : queue) {
        boolean free = true;
        for (int[] t : taken) {
            if (r[0] < t[1] && t[0] < r[1]) free = false;
        }
        if (free) taken.add(r);
    }
    return taken;
}


static void show(String rule, List<int[]> taken) {
    List<String> slots = new ArrayList<>();
    for (int[] t : taken) slots.add(t[0] + "–" + t[1]);
    System.out.println(rule + ": " + String.join(", ", slots) + " (" + taken.size() + ")");
}
show("По началото", book(requests, Comparator.comparingInt(r -> r[0])));
show("По дължината", book(requests, Comparator.comparingInt(r -> r[1] - r[0])));
show("По края", book(requests, Comparator.comparingInt(r -> r[1])));
Изход
По началото: 8–16, 17–20 (2)
По дължината: 11–13, 14–16, 18–20 (3)
По края: 9–12, 12–15, 15–18, 18–20 (4)

По началото излизат 2 срещи, по дължината 3, а по края 4. Дали 4 е най-многото? Пробвай всичките 2⁸ = 256 подмножества: да, 5 не се побират. Но защо точно правилото „по края“, и как да си сигурен, без да пробваш всичко?

Идеята

Алчен алгоритъм

Алчният алгоритъм прави избора, който изглежда най-добър сега, и никога не се връща да го преразгледа. Няма таблица като при динамичното програмиране и няма пробване на всички възможности: обикновено една подредба и един проход.

За залата алчното е: подреди заявките по края и приемай всяка, която почва не по-рано от момента, в който залата се освобождава. Една променлива, freeFrom, пази този момент, затова не трябва да сравняваш с всички вече приети.

Трите правила от задачата са все алчни. Разликата е какво смятат за „най-добро сега“, и само едно от тях е вярно. Алчното е бързо и просто, но идва без гаранция: всяко алчно правило иска довод, че изборът в момента не разваля бъдещето.

Виж го

Алчното по края

static List<int[]> maxMeetings(int[][] requests) {
    int[][] byEnd = requests.clone();
    Arrays.sort(byEnd, Comparator.comparingInt(r -> r[1]));
    List<int[]> taken = new ArrayList<>();
    int freeFrom = 0;
    for (int[] r : byEnd) {
        if (r[0] >= freeFrom) {
            taken.add(r);
            freeFrom = r[1];
        }
    }
    return taken;
}
Arrays.sort с Comparator подрежда копието byEnd, а requests остава в реда на идване.
int[][] requests = {
    {8, 16}, {12, 15}, {9, 12}, {15, 18},
    {11, 13}, {17, 20}, {14, 16}, {18, 20},
};
List<int[]> taken = maxMeetings(requests);
for (int[] t : taken) System.out.println(t[0] + "–" + t[1]);
System.out.println("Срещи: " + taken.size());
Изход
9–12
12–15
15–18
18–20
Срещи: 4

static List<int[]> maxMeetings(int[][] requests) {
    int[][] byEnd = requests.clone();
    Arrays.sort(byEnd, Comparator.comparingInt(r -> r[1]));
    List<int[]> taken = new ArrayList<>();
    int freeFrom = 0;
    for (int[] r : byEnd) {
        if (r[0] >= freeFrom) {
            taken.add(r);
            freeFrom = r[1];
        }
    }
    return taken;
}
Стъпка по стъпка, с думи
  1. Осем заявки за една зала, в реда, в който са дошли. Подреди ги по края: първа е тази, която свършва най-рано.
  2. Оранжевата черта е откъде залата е свободна. Отначало нищо не е заето: свободна от 0.
  3. Заявка 1 (9–12) почва в 9, залата е свободна от 0: приеми я. Сега залата е заета до 12.
  4. Заявка 2 (11–13) почва в 11, преди 12: застъпва се с вече приета среща, откажи я.
  5. Заявка 3 (12–15) почва в 12, залата е свободна от 12: приеми я. Сега залата е заета до 15.
  6. Заявка 4 (8–16) почва в 8, преди 15: застъпва се с вече приета среща, откажи я.
  7. Заявка 5 (14–16) почва в 14, преди 15: застъпва се с вече приета среща, откажи я.
  8. Заявка 6 (15–18) почва в 15, залата е свободна от 15: приеми я. Сега залата е заета до 18.
  9. Заявка 7 (17–20) почва в 17, преди 18: застъпва се с вече приета среща, откажи я.
  10. Заявка 8 (18–20) почва в 18, залата е свободна от 18: приеми я. Сега залата е заета до 20.
  11. 4 срещи: 9–12, 12–15, 15–18, 18–20. Всяка приета свършва най-рано от останалите, затова оставя най-много от деня за другите.

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

По-точно, за любопитните

Ако две заявки свършват в един и същ час, редът между тях не променя броя: щом първата е приета, втората почва преди нейния край. Вграденото сортиране и на четирите езика е стабилно (равните остават в реда на идване), затова изходът е един и същ навсякъде.

За масиви от обекти (тук int[]) Arrays.sort е TimSort и е стабилен. За масиви от int е quick sort с два пивота и не е, но там равните числа са неразличими.

Пробвай

Намери грешката

Колега преписа алчното и получи само три срещи:

static List<int[]> maxMeetings(int[][] requests) {
    int[][] byEnd = requests.clone();
    Arrays.sort(byEnd, Comparator.comparingInt(r -> r[1]));
    List<int[]> taken = new ArrayList<>();
    int freeFrom = 0;
    for (int[] r : byEnd) {
        if (r[0] > freeFrom) {
            taken.add(r);
            freeFrom = r[1];
        }
    }
    return taken;
}
int[][] requests = {
    {8, 16}, {12, 15}, {9, 12}, {15, 18},
    {11, 13}, {17, 20}, {14, 16}, {18, 20},
};
List<int[]> taken = maxMeetings(requests);
for (int[] t : taken) System.out.println(t[0] + "–" + t[1]);
System.out.println("Срещи: " + taken.size());
Изход
9–12
14–16
17–20
Срещи: 3

На кой ред е грешката?

Избери реда с грешката.

Идеята

Защо по края е вярно: доводът с размяната

Вземи което и да е най-добро разписание, например някое с 4 срещи. Подреди срещите му по време. Алчното първо взима заявката, която свършва най-рано от всички, да кажем 9–12.

  • Първата среща на най-доброто разписание свършва не по-рано от 12, защото 12 е най-ранният край изобщо.
  • Смени я с 9–12. Останалите срещи на разписанието почват след края на старата първа, значи и след 12: нищо не се застъпва, а броят е същият.
  • Сега двете разписания започват еднакво. Махни 9–12 и заявките, които се застъпват с нея, и повтори същото за останалите.

Стъпка по стъпка превръщаш най-доброто разписание в алчното, без да губиш нито една среща. Значи алчното е поне толкова добро, колкото най-доброто: то е най-доброто.

Същият довод се проваля за другите две правила. По началото първа е 8–16: ако я сложиш на мястото на първата среща, тя затваря залата до 16, и останалите срещи вече не се побират.

По-точно, за любопитните

Формално доводът е индукция по броя приети срещи: след k стъпки има най-добро разписание, което започва с първите k алчни избора. Това е стандартният начин да се докаже алчен алгоритъм: „алчният избор е безопасен“ (има най-добро решение, което го съдържа) плюс „оптимална подструктура“ (останалото е същата задача, само по-малка). Второто свойство е общо с динамичното програмиране. Първото е това, което липсва, когато алчното лъже.

Пробвай

Попълни условието

static List<int[]> maxMeetings(int[][] requests) {
    int[][] byEnd = requests.clone();
    Arrays.sort(byEnd, Comparator.comparingInt(r -> r[1]));
    List<int[]> taken = new ArrayList<>();
    int freeFrom = 0;
    for (int[] r : byEnd) {
        if () {
            taken.add(r);
            freeFrom = r[1];
        }
    }
    return taken;
}

Идеята

Втори пример: рестото в евро

Касата на магазина връща ресто с колкото се може по-малко монети. Монетите на еврото са 2 €, 1 €, 50, 20, 10, 5, 2 и 1 цент. Алчното: давай най-голямата монета, която още се побира в остатъка.

static List<Integer> change(int cents) {
    int[] coins = {200, 100, 50, 20, 10, 5, 2, 1};
    List<Integer> given = new ArrayList<>();
    for (int coin : coins) {
        while (cents >= coin) {
            given.add(coin);
            cents -= coin;
        }
    }
    return given;
}


static void pay(int cents) {
    List<Integer> given = change(cents);
    List<String> parts = new ArrayList<>();
    for (int coin : given) parts.add(String.valueOf(coin));
    System.out.println(cents + " цента: " + String.join(" ", parts) + " (" + given.size() + " монети)");
}
pay(485);
Изход
485 цента: 200 200 50 20 10 5 (6 монети)

За монетите на еврото това дава най-малко монети за всяка сума: сверено е с таблицата на рестото за всяка сума до 5 €. Монетите са подбрани така нарочно.

Правилото „най-голямата първо“ обаче не е вярно за всякакви монети. При монети 1, 3 и 4 цента за 6 цента алчното дава 4 + 1 + 1, три монети, а стигат две: 3 + 3. Признак „на око“ няма: и при монети, всяка поне два пъти по-голяма от следващата, алчното може да лъже. При 1, 4 и 9 цента за 12 цента то дава 9 + 1 + 1 + 1, а стигат 4 + 4 + 4. Как се търсят такива случаи е в следващия урок.

Пробвай

Предвиди изхода

static List<Integer> change(int cents) {
    int[] coins = {200, 100, 50, 20, 10, 5, 2, 1};
    List<Integer> given = new ArrayList<>();
    for (int coin : coins) {
        while (cents >= coin) {
            given.add(coin);
            cents -= coin;
        }
    }
    return given;
}


static void pay(int cents) {
    List<Integer> given = change(cents);
    List<String> parts = new ArrayList<>();
    for (int coin : given) parts.add(String.valueOf(coin));
    System.out.println(cents + " цента: " + String.join(" ", parts) + " (" + given.size() + " монети)");
}


pay(99);
Отговор

Идеята

Трети пример: Kruskal

Доставчик на интернет свързва квартали с оптичен кабел. Всяко полагане има цена, а целта е всички квартали да са свързани, за възможно най-малко пари. Това е минималното покриващо дърво, и Kruskal го строи алчно: подрежда възможните кабели по цена и взима всеки следващ най-евтин, освен ако той затваря кръг (двата квартала вече са свързани). Кой с кого е свързан пази union-find.

И тук доводът е размяна: ако най-доброто дърво не съдържа най-евтиния кабел между две групи, сложи го и махни по-скъпия кабел от кръга, който се затваря. Цената не расте.

По-точно, за любопитните

Алчни са и други познати алгоритми. Dijkstra всеки път взима най-близкия необработен връх и не го преразглежда, а това е вярно, защото пътищата нямат отрицателни дължини. Кодът на Хъфман (зад ZIP и JPEG) всеки път слива двата най-редки символа. Общото е едно: всеки има доказателство, че изборът в момента е безопасен.

Виж го

Колко струва

Алчното е сортиране, O(n log n), и един проход, O(n). Пробването на всички подмножества е O(2ⁿ): при 20 заявки е над милион подмножества, при 60 не свършва никога. Тук Bench подрежда със сливане и брои неговите сравнения. Вграденото сортиране на твоя език прави малко по-друг брой, но расте по същия начин.

  • Всички подмножества O(2ⁿ)
  • Алчното по края O(n log n)
Алгоритъмn = 10n = 20n = 1000n = 100 000n = 1 000 000
Всички подмножества10241 048 576≈ 10³⁰¹≈ 10³⁰¹⁰²≈ 10³⁰¹⁰²⁹
Алчното по края338596911 636 658≈ 19 639 896
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
static List<int[]> maxMeetings(int[][] requests) {
    int[][] byEnd = requests.clone();
    Arrays.sort(byEnd, Comparator.comparingInt(r -> r[1]));
    List<int[]> taken = new ArrayList<>();
    int freeFrom = 0;
    for (int[] r : byEnd) {
        if (r[0] >= freeFrom) {
            taken.add(r);
            freeFrom = r[1];
        }
    }
    return taken;
}

Упражнение

Куриерът

Реши задачата в редактора си.

Куриерът. Куриер разнася пратки в бизнес парк. Всеки клиент е казал в кой прозорец е на адреса: 9–11, 10–12, 11–14, 13–15, 14–17, 16–18 и 17–19 ч. При всяко минаване куриерът оставя пратките на всички, които са на адреса точно тогава. Колко най-малко пъти трябва да мине, и в колко часа? Напиши алчното и изведи:

Изход
Минавания в: 11, 15, 18 (3)

Подсказка: подреди прозорците по края. Първото минаване е в края на най-ранно свършващия прозорец: по-късно губиш този клиент, а по-рано не обслужваш повече. После прескачаш всички прозорци, които вече съдържат този час.

Още задачи

  • Довод. Напиши довода с размяната за куриера: защо първото минаване в края на най-ранния прозорец не е по-лошо от минаването в най-доброто решение?
  • Втора зала. Ако коуъркингът има две зали, работи ли „по края“, като даваш всяка заявка на залата, която се е освободила най-късно, но навреме?
  • Цени. Ако заявките плащат различно и искаш най-много пари, а не най-много срещи, алчното по края вече не е вярно. Намери три заявки, при които не е, и реши задачата с рецептата на динамичното програмиране.

Тест

Провери се

1. Какво прави един алгоритъм „алчен“?
2. Защо за залата се подрежда по края, а не по началото?
3. Заявките 9–12 и 12–15 застъпват ли се?
4. Кое показва доводът с размяната?
5. Рестото с монетите на еврото е алчно. Кога същото правило дава грешно?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·