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

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

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

Проблем

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

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

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

def book(requests, rule):
    taken = []
    for start, end in sorted(requests, key=rule):
        if all(end <= s or e <= start for s, e in taken):
            taken.append((start, end))
    return taken




def show(rule, taken):
    slots = ", ".join(f"{s}–{e}" for s, e in taken)
    print(f"{rule}: {slots} ({len(taken)})")
show("По началото", book(requests, lambda r: r[0]))
show("По дължината", book(requests, lambda r: r[1] - r[0]))
show("По края", book(requests, lambda 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, пази този момент, затова не трябва да сравняваш с всички вече приети.

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

Виж го

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

def max_meetings(requests):
    taken = []
    free_from = 0
    for start, end in sorted(requests, key=lambda r: r[1]):
        if start >= free_from:
            taken.append((start, end))
            free_from = end
    return taken
sorted(..., key=lambda r: r[1]) дава нов списък, подреден по края, а start, end разопакова всяка двойка.
requests = [
    (8, 16), (12, 15), (9, 12), (15, 18),
    (11, 13), (17, 20), (14, 16), (18, 20),
]
taken = max_meetings(requests)
for start, end in taken:
    print(f"{start}–{end}")
print(f"Срещи: {len(taken)}")
Изход
9–12
12–15
15–18
18–20
Срещи: 4

def max_meetings(requests):
    taken = []
    free_from = 0
    for start, end in sorted(requests, key=lambda r: r[1]):
        if start >= free_from:
            taken.append((start, end))
            free_from = end
    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. Всяка приета свършва най-рано от останалите, затова оставя най-много от деня за другите.

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

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

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

sorted и list.sort са Timsort и винаги са стабилни.

Пробвай

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

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

def max_meetings(requests):
    taken = []
    free_from = 0
    for start, end in sorted(requests, key=lambda r: r[1]):
        if start > free_from:
            taken.append((start, end))
            free_from = end
    return taken
requests = [
    (8, 16), (12, 15), (9, 12), (15, 18),
    (11, 13), (17, 20), (14, 16), (18, 20),
]
taken = max_meetings(requests)
for start, end in taken:
    print(f"{start}–{end}")
print(f"Срещи: {len(taken)}")
Изход
9–12
14–16
17–20
Срещи: 3

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

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

Идеята

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

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

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

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

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

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

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

Пробвай

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

def max_meetings(requests):
    taken = []
    free_from = 0
    for start, end in sorted(requests, key=lambda r: r[1]):
        if :
            taken.append((start, end))
            free_from = end
    return taken

Идеята

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

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

COINS = [200, 100, 50, 20, 10, 5, 2, 1]




def change(cents):
    given = []
    for coin in COINS:
        while cents >= coin:
            given.append(coin)
            cents -= coin
    return given




def pay(cents):
    given = change(cents)
    print(f"{cents} цента: {' '.join(map(str, given))} ({len(given)} монети)")
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. Как се търсят такива случаи е в следващия урок.

Пробвай

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

COINS = [200, 100, 50, 20, 10, 5, 2, 1]




def change(cents):
    given = []
    for coin in COINS:
        while cents >= coin:
            given.append(coin)
            cents -= coin
    return given




def pay(cents):
    given = change(cents)
    print(f"{cents} цента: {' '.join(map(str, given))} ({len(given)} монети)")




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 не пускаме, за да не замръзне страницата.
def max_meetings(requests):
    taken = []
    free_from = 0
    for start, end in sorted(requests, key=lambda r: r[1]):
        if start >= free_from:
            taken.append((start, end))
            free_from = end
    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 за достъпно обучение по програмиране ·