Жадібні алгоритми, пояснені на прикладах

Що таке жадібний алгоритм?

Можливо, ви чули про багато алгоритмічних прийомів проектування, переглядаючи деякі статті тут. Деякі з них:

  • Груба сила
  • Розділяй і володарюй
  • Жадібне програмування
  • Динамічне програмування, щоб назвати декілька. У цій статті ви дізнаєтесь про те, що таке жадібний алгоритм, і як за допомогою цієї техніки можна вирішити багато проблем із програмуванням, які інакше не здаються дріб’язковими.

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

Після того, як подорож закінчилася і ваше тіло болить і втомлюється, ви вперше дивитесь на туристичну карту. Боже мій! Там каламутна річка, яку я повинен був перетнути, замість того, щоб продовжувати йти вгору. Це означає, що жадібний алгоритм вибирає найкращий негайний вибір і ніколи не переглядає свій вибір. Що стосується оптимізації рішення, це просто означає, що ненажерливе рішення спробує знайти оптимальні місцеві рішення - яких може бути багато - і може пропустити загальне оптимальне рішення.

Формальне визначення

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

Жадібні алгоритми мають деякі переваги та недоліки:

  • Досить просто придумати жадібний алгоритм (або навіть кілька жадібних алгоритмів) для вирішення проблеми. Аналіз часу роботи для жадібних алгоритмів, як правило, буде набагато простішим, ніж для інших методів (наприклад, „Діли і володарюй”). Що стосується техніки "Розділи і підкори", незрозуміло, швидка чи повільна. Це тому, що на кожному рівні рекурсії розмір зменшується, а кількість підзадач збільшується.
  • Складність полягає в тому, що для жадібних алгоритмів доводиться працювати набагато більше, щоб зрозуміти питання коректності. Навіть маючи правильний алгоритм, важко довести, чому він правильний. Доводити правильність жадібного алгоритму - це скоріше мистецтво, ніж наука. Це передбачає багато творчості. Зазвичай придумати алгоритм може здатися тривіальним, але довести, що він насправді правильний, - це зовсім інша проблема.

Проблема планування інтервалів

Давайте зануримось у цікаву проблему, з якою ви можете зіткнутися практично в будь-якій галузі або на будь-якому рівні життя. Деякі випадки проблеми такі:

  • Вам дається набір N розкладів лекцій на один день в університеті. Графік для конкретної лекції має форму (s time, f time), де s time являє собою час початку цієї лекції, а також f time представляє час закінчення. Враховуючи список N розкладів лекцій, нам потрібно вибрати максимальний набір лекцій, які будуть проводитись протягом дня, щоб   жодна з лекцій не перекривалась між собою, тобто якщо лекції Li та Lj включені в наш вибір, то час початку j > = час закінчення i або навпаки .
  • Ваш друг працює радником табору і відповідає за організацію заходів для декількох кемпінгів. Одним із його планів є наступна вправа з міні-триатлону: кожен учасник повинен проплисти 20 кіл басейну, потім проїхати на велосипеді 10 миль, а потім пробігти 3 милі.
  • План полягає у відправленні учасників у поетапному режимі за наступним правилом: учасники повинні користуватися пулом по одному. Іншими словами, спочатку один учасник пропливає 20 кіл, вийде і почне їздити на велосипеді.
  • Як тільки ця перша людина виходить з басейну, другий учасник починає плавати 20 кіл; як тільки він виходить і починає їздити на велосипеді, третій учасник починає плавати тощо.
  • Кожен учасник має прогнозований час плавання, прогнозований час їзди на велосипеді та прогнозований час бігу. Ваш друг хоче визначитися з розкладом триборства: порядок, за яким слід розподіляти старти учасників.
  • Скажімо, час завершення розкладу - це найраніший час, коли всі учасники будуть фінішувати з усіма трьома етапами триборства, за умови, що прогнози часу точні. Яке найкраще замовлення для відправлення людей, якщо хтось хоче, щоб весь конкурс якнайшвидше закінчився? Точніше, дайте ефективний алгоритм, який формує графік, час завершення якого є якомога меншим

Проблема планування лекцій

Давайте розглянемо різні підходи до вирішення цієї проблеми.

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

Перший час початку

Спочатку найменший інтервал,  тобто ви закінчуєте вибирати лекції в порядку їх загального інтервалу, який є нічим іншим, як їх   finish time - start time. Знову ж таки, це рішення є неправильним. Подивіться на наступний випадок.

Спочатку найкоротший інтервал

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

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

Спочатку найменший конфліктний інтервал

Діаграма показує нам, що найменш суперечливим інтервалом є інтервал посередині, який містить лише 2 конфлікти. Після цього ми можемо вибрати лише два інтервали в самих кінцях із конфліктами по 3 кожного. Але оптимальним рішенням є вибір 4 інтервалів на найвищому рівні.

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

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

Коли ми використовуємо Жадібні алгоритми

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

Жадібні алгоритми допомагають нам вирішити безліч різних видів проблем, таких як:

Проблема з найкоротшим шляхом:

Мінімальна проблема обширного дерева у графіку

Проблема кодування Хаффмана

Проблема центрів K