У цьому підручнику ви дізнаєтесь, що таке жадібний алгоритм. Крім того, ви знайдете приклад жадібного підходу.
Жадібний алгоритм - це підхід до вирішення проблеми шляхом вибору найкращого варіанту, доступного на даний момент, не турбуючись про майбутній результат, який він принесе. Іншими словами, найкращий вибір на місцях спрямований на досягнення найкращих у світі результатів.
Цей алгоритм може бути не найкращим варіантом для всіх проблем. У деяких випадках це може привести до неправильних результатів.
Цей алгоритм ніколи не повертається назад до прийнятого рішення. Цей алгоритм працює у підході зверху вниз.
Головною перевагою цього алгоритму є:
- Алгоритм простіше описати .
- Цей алгоритм може працювати ефективніше, ніж інші алгоритми (але, не у всіх випадках).
Доступне рішення
Доцільним рішенням є рішення, яке забезпечує оптимальне вирішення проблеми.
Жадібний алгоритм
- Для початку набір рішень (що містить відповіді) порожній.
- На кожному кроці елемент додається до набору рішень.
- Якщо набір рішень здійсненний, поточний елемент зберігається.
- В іншому випадку пункт відхиляється і більше ніколи не розглядається.
Приклад - Жадібний підхід
Проблема: Ви повинні змінити суму, використовуючи якнайменшу кількість монет. Сума: $ 28 Доступні монети: монета $ 5 монета $ 2 монета $ 1 монета
Рішення:
- Створіть порожній набір рішень = ().
- монети = (5, 2, 1)
- сума = 0
- Поки сума ≠ 28, зробіть наступне.
- Виберіть монету C з таких монет, яка має суму + C <28.
- Якщо С + сума> 28, рішення не повертається.
- В іншому випадку сума = сума + C.
- Додайте C до набору рішень.
До перших 5 ітерацій набір рішень містить 5 монет на 5 доларів. Після цього ми отримуємо монету в 1 долар і, нарешті, 1 монету в 1 долар.
Програми жадібного алгоритму
- Сортування вибору
- Проблема рюкзака
- Мінімальне дерево, що охоплює
- Проблема коротшого шляху з одним джерелом
- Проблема планування роботи
- Алгоритм мінімального розмаху дерева Прима
- Алгоритм мінімального обширного дерева Крускала
- Алгоритм мінімального розмаху дерева Дейкстри
- Кодування Хаффмана
- Алгоритм Форда-Фулькерсона
