Жадный алгоритм

Жадный алгоритм – это метод конструирования решения, при котором на каждом шаге выбирается локально наилучший вариант из допустимых с точки зрения некоторого критерия. Дальнейшее решение строится на основе уже принятого выбора без возврата и пересмотра. Такая стратегия эффективна тогда, когда выполняются строго формализуемые свойства задачи (жадное свойство выбора и оптимальная подструктура). В подготовке к ЕГЭ по информатике это направление важно по трём причинам:

1. многие экзаменационные задачи естественно редуцируются к жадным схемам (интервальное планирование, покрытие, «размен» и т. п.);

2. жадные алгоритмы тренируют доказательные техники (инварианты, аргумент обмена, свойства «сечения» и «цикла»);

3. жадные решения часто дают линейные или квазилинейные оценки сложности и позволяют уверенно оценивать порядок роста.

Формальные основы

Модель задачи

Условия корректности

Для корректности жадной стратегии обычно достаточно (и в ряде классов задач – необходимо) двух свойств:

• Оптимальная подструктура: оптимальное решение задачи содержит оптимальные решения её подзадач (после фиксирования части выбора).

• Жадное свойство выбора: существует оптимальное решение, начинающееся с локально лучшего выбора по фиксированному критерию.

Доказательства строятся через:

• Аргумент обмена (exchange argument): любой оптимум можно постепенно «переисправить», меняя элементы на жадно выбранные, не ухудшая целевую функцию.

• Свойства сечения/цикла (для графов): безопасный выбор ребра, который гарантированно содержится в некотором минимальном остовном дереве и т. п.

• Матроидная теория (достаточное и необходимое условие): на матроидах жадный алгоритм всегда оптимален при любой аддитивной целевой функции.

Инварианты жадного шага

При каждом выборе поддерживается инвариант: «построенная часть решения может быть продолжена до некоторого оптимума». Если после жадного шага инвариант нарушается, критерий выбора некорректен. 

Классические жадные схемы (шаблоны)

1. Интервальное планирование (максимум несовмещающихся отрезков)
   

   Задача: из множества интервалов [si,fi) выбрать максимальное по мощности подмножество, в котором никакие два не пересекаются.
   Жадный критерий: сортировать по возрастанию fi​ (времени окончания) и последовательно брать первый совместимый с уже выбранными интервал.
   Доказательство: аргумент обмена – любой оптимум можно «сместить» к более раннему окончанию без уменьшения мощности.

2. Размен монет (системы с «хорошей» структурой)
   
   

3. Дробный рюкзак (реальная доля предмета разрешена)
   

   Задача: максимизировать суммарную ценность при ограничении по весу W, разрешая дробить предметы.
   Жадный критерий: сортировать по удельной ценности v_i/w_i​ и «заливать» рюкзак сверху вниз.
   Оптимальность: следует из линейности (выпуклости) – это задача линейного программирования с базисным решением жадного вида.

4. Минимальное остовное дерево (МОД): Краскал/Прим
   

   Краскал: сортировка рёбер по весу и добавление «лёгких» рёбер, не образующих цикла (проверка объединением множеств).
   Прим: наращивание дерева из стартовой вершины, каждый раз добавляя минимальное ребро, пересекающее текущий «фронт».
   Доказательство: свойство сечения – минимальное по весу ребро, пересекающее любое сечение, безопасно (содержится в некотором МОД).

5. Кратчайшие пути без отрицательных рёбер: Дейкстра
   

   Критерий: на каждом шаге «фиксировать» вершину с минимальной текущей оценкой расстояния; обновлять её соседей.
   Условие: все веса рёбер неотрицательны; иначе жадная фиксация неверна.

6. Оптимальные префиксные коды: Хаффман
   

   Критерий: многократно сливать две наименее вероятные «листья» с минимальными весами.
   Доказательство: аргумент обмена + «свойство ближайших соседей»: в некотором оптимальном дереве два минимальных веса – соседи.

Правила проектирования жадного алгоритма

1. Выразите цель как аддитивную функцию (сумма выигрышей/стоимостей). Если цель неаддитивна или содержит сильные глобальные зависимости, жадность подозрительна.

2. Сформулируйте жадный критерий естественного смысла (минимум окончания, максимум удельной ценности, минимум веса на сечении).

3. Докажите жадное свойство выбора: через обмен/сечение. Без доказательства – это эвристика, не алгоритм.

4. Проверьте оптимальную подструктуру: после локального выбора задача сужается того же типа.

5. Подберите структуру данных: сортировка (O(n log n)), очередь с приоритетами (O((n+m) log n)), система непересекающихся множеств (DSU/Union-Find) – для Краскала.

6. Оцените границы применимости: зафиксируйте условия (неотрицательные веса для Дейкстры, каноничность монет, ацикличность для топологического порядка и т. п.).

Оценка сложности и инженерные детали

• Шаг сортировки часто доминирует: O(n log n).

• Жадный выбор через структуру приоритетов: O(log n) на извлечение/вставку.

• DSU с ранком и сжатием путей: амортизированно O(α(n)) на операцию (почти константа).

• Память обычно O(n) или O(n+m) для графов.

• Инварианты реализуются через метки «зафиксирован/не зафиксирован», «выбран/не выбран», поддерживаемые структуры (очередь, куча).

Типичные ошибки и анти-паттерны

• Подмена доказательства интуицией («кажется разумным»).

• Игнорирование краевых условий (нулевые веса, равные окончания интервалов, отрицательные рёбра).

• Неверный критерий сортировки (активности по началу вместо окончания).

• Смешивание 0/1-рюкзака (недробимого) с дробным (жадность ломается).

• Путаница минимизации/максимизации: выбор «максимального» вместо «минимального» безопасного элемента.

• Нарушение допустимости при добавлении элемента (пересечение интервалов, образование цикла и т. п.).

Связь с подготовкой к ЕГЭ

В КИМ ЕГЭ регулярно встречаются задачи, решаемые жадно:

• Интервальные задачи (выбор непересекающихся мероприятий, минимальное число аудиторий, покрытие точек отрезками).

• Табличные и файловые задачи (выбор записей по критерию, сортировка, подсчёты при упорядочивании).

• Кодирование/сжатие (понимание Хаффмана и средней длины кода).

• Маршруты без отрицательных весов (идея Дейкстры на уровне рассуждений).

Практический «чек-лист ЕГЭ»:

1. Могу ли я упорядочить объекты по одному числу/отношению?

2. Сохранится ли тип подзадачи после выбора первых объектов?

3. Могу ли я защитить выбор аргументом обмена/сечения?

4. Есть ли контрпример против жадности (быстрый тест корректности)?

Пять упражнений (академический формат «теория + практика»)

Упражнение 1. Интервальное планирование и критерий окончания

Дано nnn интервалов [s_i,f_i).
a) Предложите жадный алгоритм выбора максимального числа непересекающихся интервалов, чётко сформулировав критерий и порядок сортировки.
b) Докажите корректность через аргумент обмена: покажите, как любое оптимальное решение можно преобразовать в решение жадного алгоритма без ухудшения.
c) Оцените временную сложность и укажите структуру данных, необходимую для реализации.

Упражнение 2. Размен монет: каноничность и контрпример

Рассмотрим номиналы {1, 3, 4}.
a) Примените жадный размен для суммы S=6 и покажите получившееся решение.
b) Найдите оптимальное решение и сравните с жадным (количество монет).
c) Сформулируйте общее условие, при котором система номиналов является «канонической» для жадного размена (не требуется строгое доказательство, дайте корректную формулировку и примеры).

Упражнение 3. Дробный рюкзак и удельная ценность

Есть предметы (w_i,v_i) и вместимость W.
a) Опишите жадный алгоритм с сортировкой по vi/wiv_i/w_ivi​/wi​ и аккуратно запишите инвариант.
b) Докажите оптимальность через рассуждение о линейной структуре задачи (или через контрпозицию к 0/1-рюкзаку).
c) Оцените сложность и укажите, как изменится реализация при замене сортировки на «онлайновое» поддержание кучи.

Упражнение 4. МОД: Краскал, Прим и свойства сечения/цикла

Дан связный взвешенный неориентированный граф G=(V, E).
a) Сформулируйте свойство сечения и докажите, что минимальное ребро, пересекающее любое фиксированное сечение, безопасно для МОДа.
b) Запишите псевдокод алгоритма Краскала, указав использование DSU (Union–Find) и оценив сложность.
c) Сравните Краскала и Прима по применимости (плотные/разреженные графы, выбор структур данных).

Упражнение 5. Дейкстра и ограничение на веса

Рассмотрим ориентированный граф с неотрицательными весами.
a) Обоснуйте жадную фиксацию ближайшей непосещённой вершины через инвариант расстояний.
b) Приведите небольшой пример, где единственное отрицательное ребро разрушает корректность Дейкстры (укажите порядок шагов и неверную фиксацию).
c) Сравните с алгоритмом Беллмана–Форда: когда следует выбирать его вместо жадного подхода?

Заключение

Жадные алгоритмы – это не «угадывание», а строго доказуемая стратегия, работающая при наличии жадного свойства выбора и оптимальной подструктуры. Они предоставляют мощные решения с простыми реализациями и хорошими асимптотиками: от интервалов и размена до остовных деревьев, кратчайших путей (без отрицательных весов) и оптимальных префиксных кодов. Освоение шаблонов, инвариантов и аргумента обмена превращает многие задачи ЕГЭ в последовательность формальных шагов: выбрать критерий → доказать безопасность шага → реализовать и оценить сложность. Это обеспечивает точность, скорость и стабильный высокий результат на экзамене.