Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Коли жадібний алгоритм неефективний?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

## Коротка відповідь

Жадібний алгоритм неефективний, коли локально оптимальний вибір не гарантує глобально оптимального рішення. Це трапляється за відсутності greedy-choice property та/або оптимальної підструктури: є залежності між рішеннями, обмеження цілісності (0/1), від'ємні/взаємозалежні ваги, неоднорідні метрики або ціль не є субмодулярною/монотонною.

- Немає властивості «жадібного вибору»: раннє рішення може заважати кращому глобальному.
- Немає оптимальної підструктури: найкраща стратегія на суфіксі залежить від контексту префікса.
- Обмеження цілісності (наприклад, 0/1 замість дробового вибору), залежності або конфлікти між елементами.
- Від'ємні ваги/ребра: локально мінімальні кроки нестійкі (приклад: найкоротші шляхи).
- Цільова функція не субмодулярна/немонотонна або є кілька конфліктуючих метрик.

## Детальна відповідь

### Коли жадібність працює

- Greedy-choice property: існує оптимальне рішення, чия перша «жадібна» частина збігається з локально найкращим вибором. Це дозволяє фіксувати локальний вибір без втрати оптимальності.
- Оптимальна підструктура: після локального вибору задача, що залишилася, має ту саму форму і може бути розв'язана оптимально тим самим методом.
- Структури на кшталт матроїдів/властивості розрізів (MST у Краскала/Прима) і задачі з субмодулярною монотонною ціллю (жадібність дає оптимум або гарантії наближення).

### Коли жадібність неефективна: типові патерни й контрприклади

1. Невідповідність структурам, де жадібність оптимальна (немає матроїдної структури).
Приклад: Set Cover. Класичний жадібний алгоритм «брати множину, що покриває максимум непокритих елементів» не оптимальний; лише дає наближення. Локально «найкорисніша» множина може заблокувати вигідніші комбінації.
2. Обмеження цілісності (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.
3. Від'ємні ваги або залежні вартості.
Найкоротші шляхи: Дейкстра жадібно фіксує вершини з мінімальною оцінкою. За від'ємних ребер оцінка може покращитися пізніше - жадібний вибір стає невірним. Потрібні алгоритми, що враховують «перегляди» (наприклад, Беллмана-Форда).
4. Потрібен погляд наперед (lookahead) через конфлікти/перетини.
Зважене планування інтервалів, що не перетинаються: стратегія «найраніше закінчення» оптимальна для незваженого випадку, але за наявності ваг потрібна динаміка (DP), жадібність програє.
5. Невдалий вибір локальної метрики.
Здача монет: для номіналів {1,3,4} сума 6. Жадібний вибір «брати найбільшу монету ≤ залишку» дає 4+1+1 (3 монети), оптимум - 3+3 (2 монети). Для стандартних номіналів (наприклад, 1,5,10,25) жадібність працює, але це особливість системи монет.
6. Несубмодулярні/немонотонні цілі або багатокритеріальність.
Якщо гранична вигода від додавання елемента зростає (немає спадної віддачі) або цілі конфліктують (наприклад, одночасно мінімізувати час і вартість без явної шкали), жадібність може бути скільки завгодно поганою.

### Код: швидкі контрприклади жадібності

```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, пошук або алгоритми з гарантіями наближення.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати736 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.