Среди всех алгоритмических подходов наиболее простым и понятным является метод Жадности. При таком подходе решение принимается на основе текущей доступной информации, не беспокоясь о влиянии текущего решения в будущем.
Жадные алгоритмы строят решение по частям, выбирая следующую часть таким образом, чтобы она сразу приносила пользу. Этот подход никогда не пересматривает выбор, принятый ранее. Этот подход в основном используется для решения задач оптимизации. Жадный метод прост в реализации и достаточно эффективен в большинстве случаев. Следовательно, мы можем сказать, что алгоритм Greedy — это алгоритмическая парадигма, основанная на эвристике, которая следует за локальным оптимальным выбором на каждом шаге в надежде найти глобальное оптимальное решение.
Во многих задачах оно не дает оптимального решения, хотя и дает приблизительное (почти оптимальное) решение за разумное время.
Компоненты жадного алгоритма
Жадные алгоритмы имеют следующие пять компонентов —
-
Набор кандидатов — решение создано из этого набора.
-
Функция выбора — используется для выбора лучшего кандидата для добавления в решение.
-
ТЭО — используется для определения того, можно ли использовать кандидата для внесения вклада в решение.
-
Целевая функция — используется для присвоения значения решению или частичному решению.
-
Функция решения — используется, чтобы указать, было ли достигнуто полное решение.
Набор кандидатов — решение создано из этого набора.
Функция выбора — используется для выбора лучшего кандидата для добавления в решение.
ТЭО — используется для определения того, можно ли использовать кандидата для внесения вклада в решение.
Целевая функция — используется для присвоения значения решению или частичному решению.
Функция решения — используется, чтобы указать, было ли достигнуто полное решение.
Области применения
Жадный подход используется для решения многих проблем, таких как
-
Нахождение кратчайшего пути между двумя вершинами с использованием алгоритма Дейкстры.
-
Нахождение минимального остовного дерева в графе с использованием алгоритма Прима / Крускала и т. Д.
Нахождение кратчайшего пути между двумя вершинами с использованием алгоритма Дейкстры.
Нахождение минимального остовного дерева в графе с использованием алгоритма Прима / Крускала и т. Д.
Там, где терпит неудачу жадный подход
Во многих задачах алгоритм Жадного не может найти оптимальное решение, более того, он может привести к худшему решению. Такие проблемы, как Traveling Salesman и Knapsack, не могут быть решены с помощью этого подхода.