Алчният алгоритъм и кога работи
Накратко: Алчният алгоритъм взима на всяка стъпка най-добрия избор в момента и не се връща; той дава оптималния отговор само в задачи, в които този избор е безопасен, а това се доказва, например с довода с размяната.
Проблем
Залата за срещи
Коуъркингът има една зала за срещи. За утре са дошли осем заявки, всяка с начален и краен час. Две срещи, които се застъпват, не могат да са в залата едновременно. Искаш да приемеш колкото се може повече екипи: всеки отказан отива при конкуренцията.
Първите идеи са прости правила: най-ранната заявка първо, или най-кратката първо (по-кратките заемат по-малко време). Подреждаш по правилото и приемаш всяка заявка, която не се застъпва с вече приетите:
function book(requests, rule) { const taken = []; for (const [start, end] of [...requests].sort(rule)) { if (taken.every(([s, e]) => end <= s || e <= start)) { taken.push([start, end]); } } return taken;}
function show(rule, taken) { const slots = taken.map(([s, e]) => `${s}–${e}`).join(", "); console.log(`${rule}: ${slots} (${taken.length})`);}show("По началото", book(requests, (a, b) => a[0] - b[0]));show("По дължината", book(requests, (a, b) => (a[1] - a[0]) - (b[1] - b[0])));show("По края", book(requests, (a, b) => a[1] - b[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, пази този момент, затова не трябва да сравняваш с всички вече приети.
Трите правила от задачата са все алчни. Разликата е какво смятат за „най-добро сега“, и само едно от тях е вярно. Алчното е бързо и просто, но идва без гаранция: всяко алчно правило иска довод, че изборът в момента не разваля бъдещето.
Виж го
Алчното по края
function maxMeetings(requests) { const byEnd = [...requests].sort((a, b) => a[1] - b[1]); const taken = []; let freeFrom = 0; for (const [start, end] of byEnd) { if (start >= freeFrom) { taken.push([start, end]); freeFrom = end; } } return taken;}[...requests].sort(...) подрежда копие, а const [start, end] разопакова всяка двойка.const requests = [ [8, 16], [12, 15], [9, 12], [15, 18], [11, 13], [17, 20], [14, 16], [18, 20],];const taken = maxMeetings(requests);for (const [start, end] of taken) console.log(`${start}–${end}`);console.log(`Срещи: ${taken.length}`);9–1212–1515–1818–20Срещи: 4function maxMeetings(requests) { const byEnd = [...requests].sort((a, b) => a[1] - b[1]); const taken = []; let freeFrom = 0; for (const [start, end] of byEnd) { if (start >= freeFrom) { taken.push([start, end]); freeFrom = end; } } return taken;}Стъпка по стъпка, с думи
- Осем заявки за една зала, в реда, в който са дошли. Подреди ги по края: първа е тази, която свършва най-рано.
- Оранжевата черта е откъде залата е свободна. Отначало нищо не е заето: свободна от 0.
- Заявка 1 (9–12) почва в 9, залата е свободна от 0: приеми я. Сега залата е заета до 12.
- Заявка 2 (11–13) почва в 11, преди 12: застъпва се с вече приета среща, откажи я.
- Заявка 3 (12–15) почва в 12, залата е свободна от 12: приеми я. Сега залата е заета до 15.
- Заявка 4 (8–16) почва в 8, преди 15: застъпва се с вече приета среща, откажи я.
- Заявка 5 (14–16) почва в 14, преди 15: застъпва се с вече приета среща, откажи я.
- Заявка 6 (15–18) почва в 15, залата е свободна от 15: приеми я. Сега залата е заета до 18.
- Заявка 7 (17–20) почва в 17, преди 18: застъпва се с вече приета среща, откажи я.
- Заявка 8 (18–20) почва в 18, залата е свободна от 18: приеми я. Сега залата е заета до 20.
- 4 срещи: 9–12, 12–15, 15–18, 18–20. Всяка приета свършва най-рано от останалите, затова оставя най-много от деня за другите.
Всяка приета среща оставя залата свободна възможно най-рано. Отказаните не са загуба: всяка от тях се застъпва със среща, която свършва не по-късно от нея.
По-точно, за любопитните
Ако две заявки свършват в един и същ час, редът между тях не променя броя: щом първата е приета, втората почва преди нейния край. Вграденото сортиране и на четирите езика е стабилно (равните остават в реда на идване), затова изходът е един и същ навсякъде.
Array.prototype.sort е стабилен от ES2019 насам. Без функция за сравнение подрежда като текст: [9, 12].sort() дава [12, 9].Пробвай
Намери грешката
Колега преписа алчното и получи само три срещи:
function maxMeetings(requests) { const byEnd = [...requests].sort((a, b) => a[1] - b[1]); const taken = []; let freeFrom = 0; for (const [start, end] of byEnd) { if (start > freeFrom) { taken.push([start, end]); freeFrom = end; } } return taken;}const requests = [ [8, 16], [12, 15], [9, 12], [15, 18], [11, 13], [17, 20], [14, 16], [18, 20],];const taken = maxMeetings(requests);for (const [start, end] of taken) console.log(`${start}–${end}`);console.log(`Срещи: ${taken.length}`);9–1214–1617–20Срещи: 3На кой ред е грешката?
Избери реда с грешката.
Срещата 9–12 освобождава залата в 12, и 12–15 може да почне точно тогава. Със строгото > поредните срещи се отказват. Правилно е if (start >= freeFrom) {.
Идеята
Защо по края е вярно: доводът с размяната
Вземи което и да е най-добро разписание, например някое с 4 срещи. Подреди срещите му по време. Алчното първо взима заявката, която свършва най-рано от всички, да кажем 9–12.
- Първата среща на най-доброто разписание свършва не по-рано от 12, защото 12 е най-ранният край изобщо.
- Смени я с 9–12. Останалите срещи на разписанието почват след края на старата първа, значи и след 12: нищо не се застъпва, а броят е същият.
- Сега двете разписания започват еднакво. Махни 9–12 и заявките, които се застъпват с нея, и повтори същото за останалите.
Стъпка по стъпка превръщаш най-доброто разписание в алчното, без да губиш нито една среща. Значи алчното е поне толкова добро, колкото най-доброто: то е най-доброто.
Същият довод се проваля за другите две правила. По началото първа е 8–16: ако я сложиш на мястото на първата среща, тя затваря залата до 16, и останалите срещи вече не се побират.
По-точно, за любопитните
Формално доводът е индукция по броя приети срещи: след k стъпки има най-добро разписание, което започва с първите k алчни избора. Това е стандартният начин да се докаже алчен алгоритъм: „алчният избор е безопасен“ (има най-добро решение, което го съдържа) плюс „оптимална подструктура“ (останалото е същата задача, само по-малка). Второто свойство е общо с динамичното програмиране. Първото е това, което липсва, когато алчното лъже.
Пробвай
Попълни условието
function maxMeetings(requests) {
const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
const taken = [];
let freeFrom = 0;
for (const [start, end] of byEnd) {
if () {
taken.push([start, end]);
freeFrom = end;
}
}
return taken;
}Заявката се приема, ако почва не по-рано от момента, в който залата се освобождава: start >= freeFrom.
Идеята
Втори пример: рестото в евро
Касата на магазина връща ресто с колкото се може по-малко монети. Монетите на еврото са 2 €, 1 €, 50, 20, 10, 5, 2 и 1 цент. Алчното: давай най-голямата монета, която още се побира в остатъка.
const COINS = [200, 100, 50, 20, 10, 5, 2, 1];
function change(cents) { const given = []; for (const coin of COINS) { while (cents >= coin) { given.push(coin); cents -= coin; } } return given;}
function pay(cents) { const given = change(cents); console.log(`${cents} цента: ${given.join(" ")} (${given.length} монети)`);}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. Как се търсят такива случаи е в следващия урок.
Пробвай
Предвиди изхода
const COINS = [200, 100, 50, 20, 10, 5, 2, 1];
function change(cents) { const given = []; for (const coin of COINS) { while (cents >= coin) { given.push(coin); cents -= coin; } } return given;}
function pay(cents) { const given = change(cents); console.log(`${cents} цента: ${given.join(" ")} (${given.length} монети)`);}
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 = 10 | n = 20 | n = 1000 | n = 100 000 | n = 1 000 000 |
|---|---|---|---|---|---|
| Всички подмножества | 1024 | 1 048 576 | ≈ 10³⁰¹ | ≈ 10³⁰¹⁰² | ≈ 10³⁰¹⁰²⁹ |
| Алчното по края | 33 | 85 | 9691 | 1 636 658 | ≈ 19 639 896 |
function maxMeetings(requests) { const byEnd = [...requests].sort((a, b) => a[1] - b[1]); const taken = []; let freeFrom = 0; for (const [start, end] of byEnd) { if (start >= freeFrom) { taken.push([start, end]); freeFrom = end; } } return taken;}Упражнение
Куриерът
Реши задачата в редактора си.
Куриерът. Куриер разнася пратки в бизнес парк. Всеки клиент е казал в кой прозорец е на адреса: 9–11, 10–12, 11–14, 13–15, 14–17, 16–18 и 17–19 ч. При всяко минаване куриерът оставя пратките на всички, които са на адреса точно тогава. Колко най-малко пъти трябва да мине, и в колко часа? Напиши алчното и изведи:
Минавания в: 11, 15, 18 (3)Подсказка: подреди прозорците по края. Първото минаване е в края на най-ранно свършващия прозорец: по-късно губиш този клиент, а по-рано не обслужваш повече. После прескачаш всички прозорци, които вече съдържат този час.
Още задачи
- Довод. Напиши довода с размяната за куриера: защо първото минаване в края на най-ранния прозорец не е по-лошо от минаването в най-доброто решение?
- Втора зала. Ако коуъркингът има две зали, работи ли „по края“, като даваш всяка заявка на залата, която се е освободила най-късно, но навреме?
- Цени. Ако заявките плащат различно и искаш най-много пари, а не най-много срещи, алчното по края вече не е вярно. Намери три заявки, при които не е, и реши задачата с рецептата на динамичното програмиране.
Тест