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

У жадібних алгоритмах на кожному етапі з множини можливих варіантів вибирається той, який є найкращим у даний момент, із надією, що саме він забезпечить оптимальне розв’язання всієї задачі. Вибір варіанта на кожному етапі повинен відповідати таким вимогам: бути допустимим (відповідати обмеженням задачі); бути оптимальним (найкращим із усіх можливих на даному етапі); бути остаточним (не можна змінити цей вибір на наступних етапах).

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

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

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

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