Зміст:
Визначення - Що означає жадібний алгоритм?
Жадібний алгоритм - це алгоритмічна стратегія, яка робить найкращий оптимальний вибір на кожному невеликому етапі, мета якого в кінцевому підсумку призводить до глобально оптимального рішення. Це означає, що алгоритм вибирає найкраще рішення на даний момент, не враховуючи наслідків. Він підбирає найкращий негайний результат, але не враховує великої картини, тому вважається жадібним.
Техопедія пояснює жадібний алгоритм
Жадібний алгоритм працює, вибираючи найкращу можливу відповідь на кожному кроці, а потім переходить до наступного кроку, поки не досягне кінця, не враховуючи загального рішення. Лише сподіваємось, що шлях, який він проходить, є оптимальним у всьому світі, але, як це не раз підтверджено, цей метод часто не придумує глобально оптимального рішення. Насправді цілком можливо, що найбільш оптимальні короткострокові рішення призводять до найгіршого можливого глобального результату.
Подумайте про це як зайняття великою кількістю ярликів у виробничому бізнесі: за короткий термін великі суми економляться на виробничих витратах, але це врешті-решт призводить до падіння, оскільки якість порушена, що призводить до повернення продукції та низьких продажів, оскільки клієнти знайомляться «Дешевий» товар. Але це не завжди так, існує багато застосунків, де жадібний алгоритм найкраще працює для пошуку або наближення глобально оптимального рішення, такого як побудова дерева Хаффмана або дерева навчання.
Наприклад: Візьміть шлях із найбільшою сумою в цілому. Жадібний алгоритм брав би блакитний шлях в результаті короткозорості, а не помаранчевий шлях, який дає найбільшу суму.
Компоненти:
- Кандидатський набір даних, який потребує рішення
- Функція відбору, яка вибирає найкращого учасника остаточного рішення
- Функція техніко-економічного обґрунтування, яка допомагає функції відбору, визначаючи, чи може кандидат може бути учасником рішення
- Об'єктивна функція, яка присвоює значення частковому розв’язанню
- Функція рішення, яка вказує на виявлення оптимального рішення
