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

Жадный алгоритм (greedy algorithm) на каждом шаге делает выбор, который выглядит лучшим сейчас, и никогда его не пересматривает.

Зачем нужно

Жадный алгоритм прост и быстр: никакой таблицы, один проход. Когда он верен, это лучшее решение. Беда в том, что верен он не всегда, и это надо доказывать для каждой задачи.

Как работает

Пример с лекции — выдать сумму наименьшим числом монет.

Жадно:

1. сортируем номиналы по убыванию;
2. берём максимальную монету, пока имеет смысл.

Номиналы $\{15;4;3;1\}$, сумма 6:

$6=4+1+1\text{— три монеты.}$

Динамика: $F[0]=0$, $F[N]=1+\min (F[N-c_1],\dots ,F[N-c_k])$ — см. Динамическое программирование.

Не из лекции: где жадность ошибается

Оптимальный ответ — две монеты: $6=3+3$. На доске он не записан, но ради него пример и приводится. Проверено запуском: ДП даёт $F[6]=2$, жадность — 3.

Жадный алгоритм взял четвёрку, потому что она крупнее тройки. А остаток 2 из $\{15,4,3,1\}$ набирается только двумя единицами. Пересмотреть первый выбор жадность не умеет. Динамика перебирает все варианты последней монеты, поэтому находит 3 + 3.

Тонкости

Не из лекции

• Для «обычных» номиналов $\{1,2,5,10,\dots \}$ жадный размен оптимален. Это свойство набора монет, а не алгоритма: добавьте номинал 4 к $\{1,3\}$ — и сумма 6 снова ломает жадность.
• Чтобы доверять жадному алгоритму, нужно доказательство: обычно — что любое оптимальное решение можно перестроить так, чтобы оно начиналось с жадного выбора, не ухудшив его.
• Время жадного размена — $O(k)$ после сортировки номиналов, у ДП — $O(N\cdot k)$. Жадность выигрывает, когда она верна.

Частые ошибки

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