Предыдущая часть: “Структуры данных: асимптотический анализ”
Алгоритм предназначен для достижения оптимального решения задачи. В подходе с жадным алгоритмом оно выбирается из заданной предметной области решений. Причём берутся ближайшие, кажущиеся оптимальными решения — отсюда и название «жадный».
В «жадных» алгоритмах ведётся поиск локально оптимального решения, которое в итоге может привести к нахождению глобально оптимальных решений, но обычно глобально оптимальными они не оказываются.
Подсчет монет
Цель этой задачи — досчитать до нужного значения, выбрав наименьшее количество монет. Согласно жадному подходу, в алгоритме выбирается наибольшая монета. Чтобы досчитать до 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).
Следовательно, можно сделать вывод: при «жадном» подходе выбирается ближайшее оптимальное решение, но этот подход может оказаться неэффективным там, где главная задача — нахождение глобально оптимального решения.
Примеры
Жадный подход используется в большинстве сетевых алгоритмов. Вот некоторые из них:
- задача коммивояжера;
- алгоритм Прима (поиск остовного дерева минимального веса в связном графе);
- алгоритм Крускала (поиск остовного дерева минимального веса в графе);
- алгоритм Дейкстры (поиск остовного дерева минимального веса в графе);
- раскраска графов/карт;
- графовое/вершинное покрытие;
- задача о ранце;
- задача о календарном планировании работ.
И подобных задач, в которых для поиска оптимального решения используется жадный подход, много.
Читайте также:
- Как освоить алгоритмы?
- 8 базовых алгоритмических задач на собеседованиях
- 9 навыков, которые нужно освоить в самом начале карьеры программиста
Читайте нас в Telegram, VK и Яндекс.Дзен
