Чи варто бути жадібним? «Жадібні алгоритми» у задачах

Алгоритми мають велике як теоретичне, так і практичне значення: допомагаючи нам знайти рішення для будь-якої конкретної задачі й отримати бажаний результат. У природничих науках, зокрема програмуванні, актуальними  є завдання оптимізації. У таких завданнях може бути безліч різних рішень; їхню «якість» визначають значенням параметра, і потрібно вибрати оптимальне рішення, за якого значення параметра буде мінімальним або максимальним (залежно від постановки задачі). Багато таких задач порівняно швидко і просто вирішують за допомогою «жадібних алгоритмів». Розглянемо деякі з них.

Поняття алгоритму є одним з основних понять в математиці і програмуванні. Ще на ранніх щаблях розвитку математики як науки (у Стародавньому Єгипті, Вавилоні, Греції) люди стали стикатися з різними обчислювальними процесами суто механічного характеру, у результаті яких шукані величини деяких завдань обчислювалися з вихідних величин через послідовне виконання дій за певними правилами. Саме такі завдання поклали початок сучасному поняттю алгоритму.

Кого ми називаємо жадібним? У загальному розумінні це людина, яка не бажає щось віддавати, навіть якщо цим вона завдає собі шкоди. Приблизно так само можна означити жадібні алгоритми — вони на кожному кроці вибирають хід, який є локально оптимальний, але може призвести до рішення, що не є оптимальним глобально.

У жадібному алгоритмі (greedy algorithm) завжди робиться вибір, який здається наразі найкращим, тобто виробляється локально оптимальний вибір в надії, що він приведе до оптимального рішення глобального завдання. Динамічне програмування і жадібні алгоритми тісно пов’язані між собою. Зв’язок їх обумовлений наявністю оптимальної підструктури завдання, тобто в оптимальному вирішенні завдання знаходяться оптимальні рішення підзадач. Жадібний підхід будує рішення
за допомогою послідовності кроків, на кожному з яких виходить часткове вирішення поставленого завдання, поки не буде отримано повне рішення. При цьому на кожному кроці — і це є головним у цьому методі — вибір повинен бути:

• допустимим, тобто задовольняти обмеження умови;
• локально оптимальним, тобто найкращим локальним вибором серед всіх допустимих варіантів, доступних на кожному кроці;
• остаточним, тобто, будучи зробленим, він не може бути змінений подальшими кроками алгоритму.

Зазвичай, жадібний алгоритм базується на п’яти принципах:

1. Набір можливих варіантів, з яких робиться вибір
2. Функція вибору, за допомогою якої знаходиться найкращий варіант
3. Функція, яка визначає придатність отриманого набору
4. Функція цілі, оцінює цінність рішення, не виражена явно
5. Функція розв’язку, яка вказує на те, що знайдено кінцеве рішення

Ці вимоги пояснюють назву методу: на кожному кроці він передбачає «жадібний» вибір найкращої доступної альтернативи в надії, що послідовність локально оптимальних виборів приведе до глобально оптимального рішення всієї задачі. Існують завдання, для яких послідовність локально оптимальних виборів приводить до оптимального рішення для будь-якого примірника конкретної задачі, але є й інші завдання, для яких це не так; для таких завдань жадібний алгоритм може підійти тільки в тому випадку, якщо нас влаштовує наближене рішення.

Розглянемо простий приклад завдання, що розв’язується жадібним алгоритмом:

Приклад 1. Як виплатити суму в 98 копійок монетами номіналом 1, 2, 5, 10 і 25 копійок так, щоб загальна кількість монет було мінімально?

Рішення:

Жадібний алгоритм у цьому випадку полягає в тому, щоб на кожному кроці побудови рішення використовувати монети максимального номіналу, і тим, щоб їх було якомога менше (досягнення локального мінімуму). Спочатку ми беремо три монети по 25 копійок (4 монети дають більшу суму, ніж потрібно). Залишається виплатити 98 – 25 · 3 = 23 копійки.

На другому кроці ми беремо чергові найбільші за номіналом монети, якими можна видати решту суми, — дві монети по 10 копійок.

Два наступні кроки дають нам по одній дво- і однокопієчній монеті, тим самим дозволяючи виплатити всю суму 7 монетами. (Зауважимо, що такий жадібний алгоритм підходить не для будь-якої суми і набору монет — наприклад, суму в 15 копійок монетами 1,5 і 11 копійок можна виплатити трьома монетами по 5 копійок, але застосування жадібного алгоритму дає нам п’ять монет — 11 копійок і чотири монети по 1 копійці)

Приклад 2. Пасажирський ліфт не може підняти більше W кг. У ліфт намагаються влізти H людей, причому для кожної людини відома її вага: W1, W2… WH. Визначити, яка максимальна кількість людей зможе поїхати на ліфті за один раз.

Рішення:

Очевидно, що елементарною підзадачею є врахування об’єму ліфта на одну людину. За наявності кількох кандидатів на цей об’єм, оптимальним вибором буде людина з найменшою вагою, тому що при цьому залишається найбільший запас вантажопідйомності. Тому для рішення задачі  відсортуємо людей за їх вагою і будемо, починаючи з найлегшої, поміщати їх у ліфт, поки це ще можна зробити.

Як правило, жадібні алгоритми інтуїтивно привабливі і прості. Але, незважаючи на очевидну простоту, для кожного завдання потрібно іноді дуже складне доведення застосування алгоритму для його вирішення.

Різницю між динамічним програмуванням і жадібним алгоритмом можна проілюструвати на прикладі задачі про рюкзак, а точніше, на її дискретному і неперервному формулюванні. Неперервне завдання вирішується жадібним методом, дискретне ж вимагає більш тонкого, динамічного рішення.

Розглянемо дві класичні задачі про рюкзак

Приклад 3.

Дискретна задача про рюкзак. Злодій пробрався на склад, на якому зберігається n речей. Кожна річ коштує vi доларів і важить wi кілограм. Злодій хоче забрати товару на максимальну суму, проте він не може підняти більш W кілограм (всі числа цілі). Що він повинен покласти в рюкзак?

Неперервна задача про рюкзак. Тепер злодій уміє дробити товари і укладати в рюкзак тільки їх частини, і не обов’язково цілком.

Зазвичай, у дискретній задачі йдеться про золоті злитки різної проби, а в неперервній — про золотий пісок.

Рішення:

Маючи порожній рюкзак вантажопідйомністю 50 кг (рис. а), у випадку неперервної задачі розраховуємо питому вартість речей, потім беремо по максимуму найдорожчі речі, потім наступні за вартістю, і т. д. — доти, поки останню річ не доведеться розділити. Маємо результат $240 (рис. 1).

У випадку ж дискретної задачі, користуючись тими ж міркуваннями, ми покладемо спочатку першу річ, проте тепер нам набагато вигідніше укласти рюкзак «під зав’язку» не найдорожчими (у розрахунку на кілограм) предметами, як показано на малюнку. Так ми заробимо $220 замість одержуваних за алгоритмом $160.

Розглянемо ще один жадібний алгоритм — алгоритм Хаффмена. Його широко використовують для стиснення інформації.

Алгоритм Хаффмана (англ. Huffman’s algorithm) — алгоритм оптимального префіксного кодування алфавіту, що належить до жадібних алгоритмів. Був розроблений в 1952 році аспірантом Массачусетського технологічного інституту Девідом Хаффманом при написанні ним курсової роботи. Використовується у багатьох програмах стиснення даних, наприклад, PKZIP 2, LZH та ін.

Коди Хаффмана (Huffman codes) — широко поширений і дуже ефективний метод стиснення даних, який, залежно від характеристик цих даних, зазвичай дозволяє заощадити від 20% до 90% обсягу. Ми розглядаємо дані, що являють собою послідовність символів. У жадібному алгоритмі Хаффмана використовується таблиця, яка містить частоти появи тих чи інших символів.

Побудова коду Хаффмана зводиться до побудови відповідного бінарного дерева за наступним алгоритмом:

1. Складемо список кодованих символів, при цьому будемо розглядати один символ як дерево, що складається з одного елемента з вагою, рівною частоті появи символа в рядку.
2. Зі списку виберемо два вузли з найменшою вагою.
3. Сформуємо новий вузол із вагою, рівним сумі ваг обраних вузлів, і приєднаємо до нього два обраних вузли в якості дітей.
4. Додамо до списку щойно сформований вузол замість двох об’єднаних вузлів.
5. Якщо в списку більше одного вузла, то повторимо пункти з другого по п’ятий.

Приклад 4.

Закодуємо слово abracadabra. Тоді алфавіт буде A={a,b,r,c,d}, а набір ваги (частота появи символів алфавіту у слові) W={5,2,2,1,1}

Рішення:

У дереві Хаффмана будет 5 вузлів:

За алгоритмом візьмемо два символи з найменшою частотою появи — це c та d. Формуємо з них новий вузол cd вагою 2 та додамо до списку вузлів:

Потім знову об’єднаємо у один вузол два мінімальних за вагою вузли — r та cd:

Ще раз повторимо цю ж операцію, але для вузлів rcd та b:

На останньому кроці об’єднаємо два вузли — brcd та a:

Залишився один вузол, значить, ми прийшли до кореню дерева Хаффмана (дивись рис. 2). Тепер для кожного символу виберемо кодове слово (бінарна послідовність, що позначає шлях по дереву до цього символу від кореня):

Так закодований запис слова abracadabra буде мати вигляд: 01110101000010010111010. Довжина закодованого слова — 23 біти. Важливо зауважити, що якби ми використовували алгоритм кодування з однаковою довжиною всіх кодових слів, то закодоване слово зайняло б 33 біти, що істотно більше.

До інших жадібних алгоритмів зараховують:

• Алгоритм Краскала (пошук остовного лісу мінімальної ваги в графі).
• Алгоритм Прима (пошук остовного дерева мінімальної ваги в зв’язному графі).
• Алгоритм Лін-Керніга (кластеризація графа).
• Алгоритм Радо — Едмондс (узагальнений жадібний алгоритм).

Пропонуємо для самостійного розбору декілька завдань, що використовують жадібні алгоритми як спосіб вирішення. Систему тестів також пропонуємо розробити самостійно.

1. На конференції, щоб виділити більше часу на неформальне спілкування, різні секції рознесли по різних аудиторіях. Учений із надзвичайно широкими інтересами хоче відвідати кілька доповідей, які проходять в різних секціях. Відомо початок Si та кінець fi кожної доповіді. Визначити, яку максимальну кількість доповідей можна відвідати.
2. Теплого весняного дня група з N школярів-програмістів гуляла в околицях міста Києва. На жаль, вони натрапили на велику і досить глибоку яму. Як це сталося — незрозуміло, але вся компанія опинилася в цій ямі.

Глибина ями дорівнює H. Кожен школяр знає свій зріст по плечі hi і довжину своїх рук li. Так якщо він, стоячи на дні ями, підніме руки, то його долоні виявляться на висоті hi + li від рівня днища ями. Школярі можуть, стаючи один одному на плечі, утворювати вертикальну колону. При цьому будь-який школяр може стати на плечі будь-якого іншого школяра. Якщо під школярем i стоять школярі j1, j2,…, jk, то він може дотягнутися до рівня hj1 + hj2 + … + hjk + hi + li.

Якщо школяр може дотягнутися до краю ями (тобто hj1 + hj2 + … + hjk + hi + li ≥ H), то він може вибратися з неї. Школярі, які вибралися з ями, не можуть допомогти тим, що в ній залишилися.

Знайдіть найбільшу кількість школярів, які зможуть вибратися з ями до прибуття допомоги, і перерахуйте їхні номери.

Вхідні дані:

N (1 ≤ N ≤ 2000) — кількість школярів,що потрапили до ями.

Далі в N рядках містяться по два числа: зріст i-го школяра по плечі hi (1 ≤ hi ≤ 105) та довжина його рук li (1 ≤ li ≤ 105).

Глибина ями H (1 ≤ H ≤ 105).

Результат: вивести максимальну кількість школярів К, що можуть вибратися з ями. Якщо К відмінне від 0, то виведіть і номери учнів.

3. Команда з плавання складається з N гравців, відома базова швидкість кожного гравця Vi. У шафці знаходиться K магічних плавальних костюмів, про які тренер пустив чутку, що вони дають бонус до швидкості. Костюми бувають двох типів — «спецназівські» костюми з шипами дають процентний бонус, а звичайні плавки дають кількісний бонус. Потужність впливу костюма описується цілим числом від 1 до 300. Для «спецназівских» костюмів воно показує, на скільки відсотків збільшиться базова швидкість, а для плавок — на яку величину.

Потрібно роздати плавальні костюми так, щоб сумарна швидкість команди була максимальна. Ясно, що кожен гравець отримує не більше одного костюма, якщо йому не дістається костюма, то він йде в шапочці.

Вхідні дані:

N (0 <= N <= 400) — число спортсменів,

N чисел, які описують їх базові швидкості (ціле число від 1 до 10000),

K (0 <= K <= 800) — кількість костюмів,

K пар цілих чисел, що описують костюми (тип і потужність).

Тип пари описується або одиницею («спецназівські» костюми), або двійкою(плавки).

Результат: максимальна швидкість команди

4. Системний адміністратор згадав, що давно не робив архіву призначених для користувача файлів. Однак, обсяг диска, куди він може помістити архів, може бути меншим, ніж сумарний обсяг архівних файлів.

Відомо, який обсяг займають файли кожного користувача.

Напишіть програму, яка за заданою інформацією про користувачів і вільний обсяг на архівному диску визначить максимальну кількість користувачів, чиї дані можна помістити в архів, при цьому використовуючи вільне місце якомога повніше.

Вхідні дані:

S — розмір вільного місця на диску (натуральне, не перевищує 10000),

N — кількість користувачів (натуральне, не перевищує 100),

N чисел — обсяг даних кожного користувача (натуральне, не перевищує 1000).

Результат: найбільша кількість користувачів, чиї дані можуть бути розміщені в архів.

Використані джерела

• Алгоритм Хаффмана URL: http://qoo.by/40t0
• Задачі на використання жадібних алгоритмів. URL: http://informatics.mccme.ru/py-source/source/dir/240-427?cnt=100
• Кормен Т., Лейзерсон Ч., Риверст Р., Штайн К. Алгоритмы: построение и анализ. М.Вильямс, 2005.
• Новіков Ф., Поздняков С. Жадные алгоритмы. Компьютерные инструменты в образовании. 2005. №2.

Підготувала Оксана ЖУРИБЕДА

газета “Інформатика”, №4 квітень 2018