Вопрос #1615385
Дан псевдокод жадного алгоритма для покрытия множества: докажите или опровергните приближённую оценку качества решения (approx ratio), обсудите случаи, когда жадный подход близок к оптимальному, и примеры, где он даёт плохие результаты.
1) Доказательство оценки \(H_n\) (стандартное «charging»‑доказательство).
- Обозначим универсум \(U\), \(|U|=n\). Пусть OPT — мощность оптимального покрытия.
- Жадный алгоритм в каждом шаге берёт множество, покрывающее максимально возможное число ещё непокрытых элементов. Рассмотрим момент, когда остаётся \(r\) непокрытых элементов; пусть выбранное множество покрывает \(t\) из них. Тогда «стоимость» (вклад) покрытия каждого из этих \(t\) новых элементов можно назначить как \(\frac{1}{t}\) (нормируя, что каждое выбранное множество «стоит» 1).
- Пусть оптимальное покрытие состоит из \(OPT\) множеств; каждая оставшаяся в какой‑то момент непокрытая точка принадлежит хотя бы одному множеству оптимального покрытия, поэтому среди элементов, покрытых в данный шаге, существует набор из не более \(OPT\) «пакетов», которые могли бы покрыть их раньше. Формально можно показать, что при текущем числе непокрытых элементов \(r\) выбранное множество покрывает по крайней мере \(r/OPT\) элементов, иначе объединение \(OPT\) множеств из оптимального покрытия покрывало бы менее чем \(r\) элементов — противоречие.
- Отсюда вклад в «стоимость на элемент» в этот шаг не превышает \(\frac{OPT}{r}\). Суммируя по последовательным значениям \(r=n,n-1,\dots,1\) получаем суммарную стоимость (число выбранных множеств) не более
\[
OPT\cdot\sum_{r=1}^n\frac{1}{r}=OPT\cdot H_n.
\]
- Следовательно, жадный алгоритм даёт приближение с фактором \(H_n\).
(Аналогичное доказательство через «покрытие» элементов ценой до \(\frac{OPT}{\text{число оставшихся}}\) — классическая схема.)
2) Tightness (сутяжимость оценки).
- Оценка \(H_n\) тесная: известны конструкции (так называемая «гармоническая» или «Chvátal/Feige» конструкция), где отношение качества жадного решения к OPT стремится к \(H_n\) (показывая, что верхняя граница не улучшаема в общем случае). Формально: для бесконечной последовательности входов отношение \(\frac{\text{value(greedy)}}{\text{OPT}}\) достигает \(H_n-O(1)\).
- Исторически: Chvátal (1979) анализировал жадный алгоритм и привёл оценку \(H_n\); Feige (1998) дал результаты о жёсткости приближений для Set Cover, показывая, что \( (1-o(1))\ln n\) — «правильный» порог при стандартных сложностных предположениях.
3) Когда жадный близок к оптимальному (практические случаи).
- Множества примерно одинакового размера и малые перекрытия: если множество, оптимально покрывающее много элементов, заметно выделяется, жадный быстро его найдёт.
- Когда элементы нечасто повторяются (ограничение частоты): если каждое элемент входит не более чем в \(f\) множеств, то аналогичным рассуждением даётся оценка \(H_f\) (то есть лучше, если \(f\ll n\)).
- Когда оптимальное покрытие «жирное» и почти разрежено (множества почти непересекаются): жадный часто даёт близкий к оптимальному результат (иногда даже оптимум).
- На практике жадный часто работает очень хорошо на случайных и реальных данных из‑за структуры перекрытий (веб‑индексация, даталогия и т.п.).
4) Примеры плохого поведения (интуитивно и небольшой конкретный пример).
- Плохой (асимптотический) пример: гармоническая конструкция (уровни размеров, дающие покрытие фракциями \(1,1/2,1/3,\dots\)) демонстрирует, что жадный может потребовать \(\approx H_n\) раз больше множеств, чем OPT. (Конкретная формализация требует аккуратной постановки уровней и множеств; это стандартная конструкция в литературе по Set Cover.)
- Небольшой конкретный демонстративный пример (не даёт полного \(\ln n\) фактора, но показывает, как жадный может «ошибиться»):
пусть \(U=\{1,\dots,6\}\),
множества \(A=\{1,2,3\},\; B=\{4,5,6\},\; X_1=\{1,4\},\; X_2=\{2,5\},\; X_3=\{3,6\}\).
Оптимально достаточно двух множеств \(\{A,B\}\) (OPT=2). Жадный, если сначала выберет, скажем, \(X_1\) (покрывает 2 элемента, а \(A\) или \(B\) тоже по 3 — в зависимости от реализации оценки он может выбрать по‑другому), может в худшем случае последовательно взять \(X_1,X_2,X_3\) и ещё одно множество, получив 4 множества. Здесь фактор \(4/2=2\). (Это простой игрушечный пример; асимптотический худший случай требует более хитрой гармонической конструкции.)
Выводы:
- Жадный алгоритм даёт гарантированное приближение \(\displaystyle H_n=\sum_{i=1}^n\frac{1}{i}=O(\ln n)\).
- Эта оценка является общепринятою верхней границей и достижима (есть экземпляры, где жадный близок к \(H_n\) раз хуже, чем OPT).
- На практике жадный часто хорошо работает; он особенно хорош при малой частоте появления элементов или при небольших перекрытиях. Для худших теоретических случаев нужно учитывать логарифмический фактор и, при необходимости, применять более сложные алгоритмы или релаксации (LP‑около).