Жадный алгоритм: материал из Википедии — свободной энциклопедии

Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдает глобальный оптимум. Если глобальная оптимальность алгоритма имеет место практически всегда, его обычно предпочитают другим методам оптимизации, таким как динамическое программирование.

Условия применимости

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

Принцип жадного выбора

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

• Доказывается, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не хуже первого.
• Показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной.
• Рассуждение завершается по индукции.

Пример. Размен монет.

Задача. Монетная система некоторого государства состоит из купюр достоинством {\displaystyle a_{1}=1<a_{2}<...<a_{n}}a_{1}=1<a_{2}<...<a_{n}. Требуется выдать сумму {\displaystyle S}S наименьшим возможным количеством купюр.

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество купюр достоинства {\displaystyle a_{n}}a_n: {\displaystyle x_{n}=\lfloor S/a_{n}\rfloor }x_{n}=\lfloor S/a_{n}\rfloor . Таким же образом получаем, сколько нужно купюр меньшего номинала, и т. д.

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение, а только для некоторых, называемых каноническими, монетных систем, вроде используемых в США (1, 5, 10, 25 центов). Неканонические системы таким свойством не обладают. Так, например, сумму в $24 купюрами  в 1, 5 и 7 $. жадный алгоритм разменивает так: $7 — 3 шт., $1 — 3 шт., в то время как правильное решение — $7 — 2 шт., $5 — 2 шт.

Типы жадных алгоритмов

• Алгоритм Хаффмана (адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью).
• Алгоритм Крускала (поиск остовного дерева минимального веса в графе).
• Алгоритм Прима (поиск остовного дерева минимального веса в связном графе).
• Обобщением жадных алгоритмов является алгоритм Радо — Эдмондса.

Задачи, в которых жадные алгоритмы не дают оптимального решения

Для ряда задач, относящихся к классу NP, жадные алгоритмы не дают оптимального решения. К ним относятся:

• задача коммивояжера;
• задача минимальной раскраски графа;
• задача разбиения графа на подграфы;
• задача выделения максимальной клики;
• задачи, связанные с составлением расписаний.

Википедии — свободной энциклопедии