Відкрити головне меню

Жа́дібний алгори́тм — простий і прямолінійний евристичний алгоритм, який приймає найкраще рішення, виходячи з наявних на поточному етапі даних, не турбуючись про можливі наслідки, сподіваючись врешті-решт отримати оптимальне рішення. Легкий в реалізації і часто дуже ефективний за часом виконання. Багато задач не можуть бути розв'язані з його допомогою.

Наприклад, використання жадібної стратегії для задачі комівояжера породжує наступний алгоритм: «На кожному етапі вибирати найближче з невідвіданих міст».

Зміст

СпецифікаРедагувати

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

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

Визначання придатностіРедагувати

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

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

Критерії застосуванняРедагувати

Жадібний алгоритм добре розв'язує деякі задачі, а інші — ні. Більшість задач, для яких він спрацьовує добре, мають дві властивості: по-перше, до них можливо застосувати Принцип жадібного вибору, по-друге, вони мають властивість Оптимальної підструктури.

Принцип жадібного виборуРедагувати

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

Властивість оптимальної підструктуриРедагувати

«Задача має оптимальну підструктуру, якщо оптимальне рішення задачі містить оптимальне рішення для підзадач»[1]. Інакше кажучи, задача має оптимальну підструктуру, якщо кожен наступний крок веде до оптимального розв'язку. Прикладом 'неоптимальної підструктури' може бути ситуація в шахах, коли взяття ферзя (хороший наступний крок) веде до програшу партії в цілому.

Коли алгоритми жадібного типу зазнають невдачіРедагувати

Жадібні алгоритми можна характеризувати як 'короткозорі' і 'невідновлювані'. Вони ідеальні лише для задач з 'оптимальною підструктурою'. Попри це, жадібні алгоритми найкраще підходять для простих задач. Для багатьох інших задач жадібні алгоритми зазнають невдачі у продукуванні оптимального розв'язку, і можуть навіть видати найгірший з можливих розв'язків. Один з прикладів — алгоритм найближчого сусіднього міста, описаний вище.

Також у задачі розміну монет, якщо є тільки 25, 10 і 4-центові монети, жадібний алгоритм не зможе зробити розмін 41 цента.

ПрикладиРедагувати

Розмін монетРедагувати

Задача. Монетна система деякої держави складається з монет вартістю  . Вимагається видати суму S найменшою можливою кількістю монет.

Жадібний алгоритм розв'язання цієї задачі такий. Беремо найбільшу можливу кількість монет вартості  :  . Так само знаходимо скільки потрібно монет меншого номіналу, і т. д.

Для цієї задачі жадібний алгоритм не завжди дає правильне рішення. Наприклад, суму в 10 копійок монетами в 1, 5 і 6 коп. жадібний алгоритм розміняє так: 6 коп. — 1 шт., 1 коп. — 4 шт., в той час як правильне рішення 2 монети по 5 копійок. Тим не менш, на всіх реальних монетних системах жадібний алгоритм видає правильну відповідь.

Вибір заявокРедагувати

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

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

Activity-Selector(s,f)

  1.   length[s]
  2.  
  3.  
  4. for   to n
    • do if  
      • then   ∪ {i}
        •  
  5. return A

На вхід алгоритму подаються масиви початку і закінчення доповідей. Множина А складається з номерів вибраних заявок, а j — номер наступної заявки. Жадібний алгоритм шукає заявку, що починається не раніше закінчення j-ї, потім знайдену заявку включає в А, а j присвоює її номер.

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

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

ПриміткиРедагувати

  1. Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 16 «Greedy Algorithms».

Див. такожРедагувати

ЛітератураРедагувати

ПосиланняРедагувати

  • Greedy algorithm visualization Візуалізація задачі N ферзів (розташувати на дошці N*N, так щоб жоден з них не атакував іншого).