Жадібний алгоритм

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Специфіка[ред.ред. код]

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

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

Визначання придатності[ред.ред. код]

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

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

Критерії застосування[ред.ред. код]

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

Принцип жадібного вибору[ред.ред. код]

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

Властивість оптимальної підструктури[ред.ред. код]

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

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

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

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

Приклади[ред.ред. код]

Розмін монет[ред.ред. код]

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

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

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

Вибір заявок[ред.ред. код]

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

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

Activity-Selector(s,f)

  1. n \leftarrow length[s]
  2. A \leftarrow  \left\{1\right\}
  3. j \leftarrow 1
  4. for i \leftarrow 2 to n
    • do if s_i \ge f_j
      • then A \leftarrow A ∪ {i}
        • j \leftarrow i
  5. return A

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

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

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

Примітки[ред.ред. код]

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

Дивіться також[ред.ред. код]

Література[ред.ред. код]

Посилання[ред.ред. код]

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