Конспект раздела: жадные алгоритмы

Понятия

Жадный алгоритм - строит ответ по шагам, берёт локально лучшее по критерию, никогда не пересматривает выбор.

Безопасность жадного шага - существует оптимум, СОДЕРЖАЩИЙ наш выбор (не «наш выбор лучший»).

Обменный аргумент - доказательство безопасности заменой одного элемента оптимума на наш.

Матроид - структура, на которой жадность верна при любых весах.

c-приближённый алгоритм - для любого входа ответ не хуже оптимума в c раз.

Что унести

Весь раздел отвечает на один вопрос: можно ли здесь жадничать - и даёт три разных ответа.

ЧЕК-ЛИСТ

1. НАЗВАТЬ ЦЕЛЬ. Без цели «оптимальный» - не формулировка.
2. ОПИСАТЬ ДОПУСТИМЫЕ НАБОРЫ.
3. ПРОВЕРИТЬ НАСЛЕДСТВЕННОСТЬ (часть допустимого допустима)
   И ОБМЕН (аксиома 3):
   |A| < |B| ⇒ найдётся ли элемент B, добавляемый к A?
4. НЕТ  → перебрать все маленькие веса: контрпример ГАРАНТИРОВАН теоремой.
         Дальше смотреть ступени отступления.
5. ДА   → сортировка по убыванию веса + проверка независимости;
         элементы с весом ≤ 0 пропускать.
         Доказательство уже есть, писать его не нужно.
6. ПРОВЕРИТЬ ЦЕЛЬ: теорема про максимум СУММЫ. Цель неаддитивна -
   теорема не применима, даже если структура идеальна.

ТРИ ТЕХНИКИ ДОКАЗАТЕЛЬСТВА

ОБМЕН ЭЛЕМЕНТА     взять оптимум O, построить O' = O − o + g,
                   проверить допустимость и что не хуже
                   (занятия: обменивать ПЕРВОЕ по времени занятие O)

ОБМЕН СОСЕДНИХ     показать, что в оптимуме нет «плохой пары соседей»
                   (расписания: перестановка меняет цель на t_i − t_j)

ЖАДНЫЙ НЕ ОТСТАЁТ  выбрать меру частичного ответа и индукцией показать,
                   что жадный по ней не хуже любого другого

Главные числа раздела. Хаффман на частотах 45, 16, 13, 12, 9, 5: 224 бита против 300 у трёхбитного кода (энтропия 2.22, Хаффман 2.24 бита на символ). Расписание 8, 1, 3, 2: сумма завершений 24 по возрастанию против 46 по убыванию. Целый рюкзак на классическом наборе: жадность 160 против оптимума 220 (дробный - 240). Рюкзак 3, 3, 4 при C = 6 и исходном порядке при равных ценностях: жадность ошибается на 13% перебранных наборов; в остальных 87% этого перебора ответ верен. Вершинное покрытие на звезде с отростками: алгоритм с гарантией 2 дал 6, жадность по степени (её гарантия хуже - ln n) - 4, оптимум - 3.

Как проверять возможность жадности. Сначала проверь наследственность и обмен. Квоты и ацикличность дают разобранные примеры матроидов; одного слова «количество» или «структура» недостаточно. Лимит суммы ресурса тоже не исключает матроид: при одинаковом расходе это ограничение числа элементов, при разных расходах может получиться рюкзак с нарушенным обменом. Теорема относится к сумме весов; для неаддитивной цели её гарантия не применяется автоматически.

Тихие ошибки раздела: доказывать «наш выбор лучший» вместо «существует оптимум с нашим выбором»; обменивать не тот элемент; остановиться на безопасности шага, не проверив подзадачу; искать контрпример случайными данными вместо полного перебора маленьких; выбрать критерий, не назвав цель; читать «гарантия 2» как «ошибается вдвое»; выбирать алгоритм по наличию гарантии, не замерив на своих данных.

Куда это ведёт

Дальше - динамическое программирование. Там отменяется главное ограничение жадности: решение МОЖНО пересматривать, потому что ответы подзадач запоминаются. Все задачи из этого раздела, помеченные «нужна динамика», решаются именно там - целый рюкзак, взвешенный выбор занятий, сдача произвольными монетами. А связь двух приёмов проще, чем кажется: жадность - это динамика, в которой на каждом шаге достаточно одного варианта, и матроидность - в точности условие, когда это так.