Коли жадібний алгоритм неефективний?
Коротка відповідь
Жадібний алгоритм неефективний, коли локально оптимальний вибір не гарантує глобально оптимального рішення. Це трапляється за відсутності greedy-choice property та/або оптимальної підструктури: є залежності між рішеннями, обмеження цілісності (0/1), від'ємні/взаємозалежні ваги, неоднорідні метрики або ціль не є субмодулярною/монотонною.
- Немає властивості «жадібного вибору»: раннє рішення може заважати кращому глобальному.
- Немає оптимальної підструктури: найкраща стратегія на суфіксі залежить від контексту префікса.
- Обмеження цілісності (наприклад, 0/1 замість дробового вибору), залежності або конфлікти між елементами.
- Від'ємні ваги/ребра: локально мінімальні кроки нестійкі (приклад: найкоротші шляхи).
- Цільова функція не субмодулярна/немонотонна або є кілька конфліктуючих метрик.
Детальна відповідь
Коли жадібність працює
- Greedy-choice property: існує оптимальне рішення, чия перша «жадібна» частина збігається з локально найкращим вибором. Це дозволяє фіксувати локальний вибір без втрати оптимальності.
- Оптимальна підструктура: після локального вибору задача, що залишилася, має ту саму форму і може бути розв'язана оптимально тим самим методом.
- Структури на кшталт матроїдів/властивості розрізів (MST у Краскала/Прима) і задачі з субмодулярною монотонною ціллю (жадібність дає оптимум або гарантії наближення).
Коли жадібність неефективна: типові патерни й контрприклади
- Невідповідність структурам, де жадібність оптимальна (немає матроїдної структури). Приклад: Set Cover. Класичний жадібний алгоритм «брати множину, що покриває максимум непокритих елементів» не оптимальний; лише дає наближення. Локально «найкорисніша» множина може заблокувати вигідніші комбінації.
- Обмеження цілісності (0/1) замість дробових рішень. 0/1 рюкзак: жадібність за питомою цінністю v/w не гарантує оптимуму, на відміну від дробового рюкзака. Контрприклад: місткість 50, предмети A(60,10), B(100,20), C(120,30). Жадібно за v/w: A(6), B(5), C(4) -> беремо A+B=160. Оптимум: B+C=220.
- Від'ємні ваги або залежні вартості. Найкоротші шляхи: Дейкстра жадібно фіксує вершини з мінімальною оцінкою. За від'ємних ребер оцінка може покращитися пізніше - жадібний вибір стає невірним. Потрібні алгоритми, що враховують «перегляди» (наприклад, Беллмана-Форда).
- Потрібен погляд наперед (lookahead) через конфлікти/перетини. Зважене планування інтервалів, що не перетинаються: стратегія «найраніше закінчення» оптимальна для незваженого випадку, але за наявності ваг потрібна динаміка (DP), жадібність програє.
- Невдалий вибір локальної метрики. Здача монет: для номіналів {1,3,4} сума 6. Жадібний вибір «брати найбільшу монету ≤ залишку» дає 4+1+1 (3 монети), оптимум - 3+3 (2 монети). Для стандартних номіналів (наприклад, 1,5,10,25) жадібність працює, але це особливість системи монет.
- Несубмодулярні/немонотонні цілі або багатокритеріальність. Якщо гранична вигода від додавання елемента зростає (немає спадної віддачі) або цілі конфліктують (наприклад, одночасно мінімізувати час і вартість без явної шкали), жадібність може бути скільки завгодно поганою.
Код: швидкі контрприклади жадібності
python
# 1) Здача монет: жадібний проти оптимального (DP)
def greedy_change(amount, coins):
coins = sorted(coins, reverse=True)
res = []
for c in coins:
while amount >= c:
amount -= c
res.append(c)
return res
def optimal_change(amount, coins):
INF = 10**9
dp = [0] + [INF] * amount
prev = [-1] * (amount + 1)
for a in range(1, amount + 1):
for c in coins:
if a >= c and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
prev[a] = c
if dp[amount] >= INF:
return None
res = []
a = amount
while a > 0:
res.append(prev[a])
a -= prev[a]
return res
coins = [1, 3, 4]
amount = 6
print("Greedy:", greedy_change(amount, coins), "count=", len(greedy_change(amount, coins)))
opt = optimal_change(amount, coins)
print("Optimal:", opt, "count=", len(opt))
# 2) 0/1 рюкзак: жадібність за v/w
def greedy_knapsack(capacity, items):
# items: list of (value, weight, name)
items_sorted = sorted(items, key=lambda x: x[0] / x[1], reverse=True)
value = 0
weight = 0
chosen = []
for v, w, name in items_sorted:
if weight + w <= capacity:
weight += w
value += v
chosen.append(name)
return value, chosen
items = [(60, 10, 'A'), (100, 20, 'B'), (120, 30, 'C')]
print("Greedy knapsack:", greedy_knapsack(50, items)) # -> (160, ['A', 'B'])
print("Optimal value should be 220 with ['B','C']")Як швидко зрозуміти, що жадібність не підійде
- Перевірте greedy-choice property: чи можна довести, що перший жадібний крок присутній у якомусь оптимумі? Якщо ні - привід сумніватися.
- Спробуйте обмінний аргумент: чи можна «обміняти» нежадібне оптимальне рішення на жадібне без погіршення? Якщо обмін не проходить - жадібність під питанням.
- Пошукайте невеликий контрприклад (3-6 елементів). Якщо швидко знаходиться - жадібність навряд чи оптимальна.
- Чи є від'ємні ваги/штрафи, вибори 0/1, перетини/конфлікти, багатокритеріальність? Часто саме це ламає жадібність.
Резюме
Жадібні алгоритми ефективні й прості там, де підтверджені властивості жадібного вибору і оптимальної підструктури (часто через матроїд/властивість розрізу/субмодулярність). В іншому випадку - особливо за 0/1-обмежень, від'ємних ваг, залежностей і конфліктуючих метрик - жадібність або не оптимальна, або може давати вкрай погані рішення; використовуйте DP, пошук або алгоритми з гарантіями наближення.
Коротка відповідь
Для співбесідиPremium
Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.