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

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

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

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

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

Цель этой задачи  —  досчитать до нужного значения, выбрав наименьшее количество монет. Согласно жадному подходу, в алгоритме выбирается наибольшая монета. Чтобы досчитать до 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).

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

Примеры

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

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

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

Читайте также:

Читайте нас в TelegramVK и Яндекс.Дзен

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