Структуры данных: «жадные» алгоритмы

Предыдущая часть: “Структуры данных: асимптотический анализ”

Алгоритм предназначен для достижения оптимального решения задачи. В подходе с жадным алгоритмом оно выбирается из заданной предметной области решений. Причём берутся ближайшие, кажущиеся оптимальными решения — отсюда и название «жадный».

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

Подсчет монет

Цель этой задачи — досчитать до нужного значения, выбрав наименьшее количество монет. Согласно жадному подходу, в алгоритме выбирается наибольшая монета. Чтобы досчитать до 18 йен, имея монеты достоинством 1, 2, 5 и 10 йен, в жадном алгоритме проходится следующая последовательность шагов:

• 1. Выбирается одна монета 10 йен (остается 8).
• 2. Выбирается монета 5 йен (остается 3).
• 3. Выбирается монета 2 йены (остается 1).
• 4. Выбирается монета 1 йена (задача решается).

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

В другой денежной системе — с монетами 1, 7 и 10 — подсчет до 18 будет абсолютно оптимальным (3 монеты). Но для подсчета до 15 может потребоваться больше монет: согласно «жадному» подходу, здесь выбирается 10 + 1 + 1 + 1 + 1 + 1 (всего 6 монет). Но та же задача решается выбором всего 3 монет (7 + 7 + 1).

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

Примеры

Жадный подход используется в большинстве сетевых алгоритмов. Вот некоторые из них:

• задача коммивояжера;
• алгоритм Прима (поиск остовного дерева минимального веса в связном графе);
• алгоритм Крускала (поиск остовного дерева минимального веса в графе);
• алгоритм Дейкстры (поиск остовного дерева минимального веса в графе);
• раскраска графов/карт;
• графовое/вершинное покрытие;
• задача о ранце;
• задача о календарном планировании работ.

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