Алгоритм предназначен для достижения оптимального решения данной проблемы. При подходе жадного алгоритма решения принимаются из данной области решения. Будучи жадным, выбрано самое близкое решение, которое, кажется, обеспечивает оптимальное решение.
Жадные алгоритмы пытаются найти локализованное оптимальное решение, которое в конечном итоге может привести к глобально оптимизированным решениям. Однако, как правило, жадные алгоритмы не обеспечивают глобально оптимизированных решений.
Подсчет монет
Эта проблема состоит в том, чтобы подсчитать желаемое значение, выбрав как можно меньше монет, и жадный подход заставляет алгоритм выбирать максимально возможную монету. Если нам будут предоставлены монеты ₹ 1, 2, 5 и 10, и нас попросят сосчитать ₹ 18, тогда жадная процедура будет:
-
1 — Выберите одну монету ₹ 10, оставшееся количество — 8
-
2 — Затем выберите одну монету ₹ 5, оставшееся количество составляет 3
-
3 — Затем выберите одну монету ₹ 2, оставшееся количество — 1
-
4 — И наконец, выбор одной монеты ₹ 1 решает проблему
1 — Выберите одну монету ₹ 10, оставшееся количество — 8
2 — Затем выберите одну монету ₹ 5, оставшееся количество составляет 3
3 — Затем выберите одну монету ₹ 2, оставшееся количество — 1
4 — И наконец, выбор одной монеты ₹ 1 решает проблему
Хотя, похоже, все работает нормально, для этого счета нам нужно выбрать всего 4 монеты. Но если мы немного изменим проблему, то тот же подход не сможет дать такой же оптимальный результат.
Для валютной системы, где у нас есть монеты достоинством 1, 7, 10, подсчет монет для значения 18 будет абсолютно оптимальным, но для подсчета, например, 15, он может использовать больше монет, чем необходимо. Например, жадный подход будет использовать 10 + 1 + 1 + 1 + 1 + 1, всего 6 монет. Тогда как ту же проблему можно решить, используя всего 3 монеты (7 + 7 + 1)
Следовательно, мы можем заключить, что жадный подход выбирает немедленное оптимизированное решение и может потерпеть неудачу, когда глобальная оптимизация является главной задачей.
Примеры
Большинство сетевых алгоритмов используют жадный подход. Вот список немногих из них —
- Задача коммивояжера
- Алгоритм минимального связующего дерева Прима
- Алгоритм минимального связующего дерева Крускала
- Алгоритм минимального связующего дерева Дейкстры
- График — раскраска карты
- Graph — Vertex Cover
- Рюкзак Проблема
- Проблема планирования работы
Есть много подобных проблем, которые используют жадный подход, чтобы найти оптимальное решение.