Конспект: жадный выбор и доказательство обменом

Понятия

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

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

Оптимальность подзадачи - после шага остаётся задача того же вида.

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

Формула Хорна - правила «все посылки ⇒ вывод» и запреты «не все сразу». Жадность ставит истину только вынужденно; каждая такая истина обязательна в любом решении: нарушенный запрет - решений нет, целые запреты - наименьшее решение. Линейное время со счётчиками посылок.

Что унести

СХЕМА АЛГОРИТМА                        ЧТО ДОКАЗАТЬ
1. выбрать критерий                    1. безопасность шага (обменом)
2. отсортировать      Θ(n·log n)       2. оптимальность подзадачи
3. пройти и брать совместимое  Θ(n)    → по индукции весь ответ оптимален
4. не пересматривать

ОБМЕННЫЙ АРГУМЕНТ
    O - произвольный оптимум; g - наш жадный выбор
    если g ∈ O - готово
    иначе найти o ∈ O, мешающий g, и взять O' = O − o + g
    проверить: (а) O' допустим   (б) O' не хуже O
    ⇒ существует оптимум с g

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

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

Выбор занятий - эталонный пример: три правдоподобных критерия, верен один.

Полный перебор на том же наборе подтверждает 10.

Где жадность ломается: когда взятый элемент меняет не только ЗАПАС ресурса, но и ПРАВИЛА для остальных.

Порядок работы: сначала контрпример (перебор ВСЕХ входов до пяти-шести элементов против точного алгоритма, потом минимизировать руками), и только если его нет - доказательство. Доказывать ложное утверждение можно бесконечно.

Если точной жадности нет - она годится как приближённый алгоритм с ДОКАЗАННОЙ гарантией: покрытие множеств ln n (неулучшаемо при P ≠ NP), вершинное покрытие 2 (брать оба конца ребра, а не вершину максимальной степени). «Гарантия 2» - граница худшего случая, а не типичная ошибка.

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

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

Следующая глава - три классические задачи, где обмен работает по-разному: расписания (обмен соседних), код Хаффмана (обмен листьев дерева) и покрытие множеств (жадность без точности, но с оценкой).