Структуры данных - жадные алгоритмы
Алгоритм предназначен для достижения оптимального решения данной проблемы. При использовании жадного алгоритма решения принимаются из заданной области решения. Будучи жадным, выбирается ближайшее решение, которое, кажется, обеспечивает оптимальное решение.
Жадные алгоритмы пытаются найти оптимальное локализованное решение, которое в конечном итоге может привести к глобально оптимизированным решениям. Однако обычно жадные алгоритмы не обеспечивают глобально оптимизированных решений.
Подсчет монет
Эта проблема состоит в том, чтобы считать до желаемого значения, выбирая наименьшее количество монет, а жадный подход заставляет алгоритм выбирать наибольшую возможную монету. Если нам предоставят монеты номиналом 1, 2, 5 и 10 фунтов стерлингов, и нас попросят сосчитать 18 фунтов стерлингов, то жадная процедура будет -
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).
Следовательно, мы можем сделать вывод, что жадный подход выбирает немедленное оптимизированное решение и может потерпеть неудачу там, где глобальная оптимизация является серьезной проблемой.
Примеры
Большинство сетевых алгоритмов используют жадный подход. Вот список некоторых из них -
- Задача коммивояжера
- Алгоритм минимального связующего дерева Прима
- Минимальный алгоритм связующего дерева Краскала
- Алгоритм минимального остовного дерева Дейкстры
- График - Раскраска карты
- График - вершинное покрытие
- Проблема с рюкзаком
- Проблема с расписанием работы
Есть много подобных проблем, которые используют жадный подход для поиска оптимального решения.