DAA - Жадный метод

Среди всех алгоритмических подходов самым простым и понятным является метод Жадности. При таком подходе решение принимается на основе имеющейся информации, не беспокоясь о влиянии текущего решения в будущем.

Жадные алгоритмы строят решение по частям, выбирая следующую часть таким образом, чтобы она сразу приносила пользу. Этот подход никогда не пересматривает выбор, принятый ранее. Этот подход в основном используется для решения задач оптимизации. Жадный метод прост в реализации и достаточно эффективен в большинстве случаев. Следовательно, мы можем сказать, что алгоритм Greedy - это алгоритмическая парадигма, основанная на эвристике, которая следует за локальным оптимальным выбором на каждом шаге в надежде найти глобальное оптимальное решение.

Во многих задачах оно не дает оптимального решения, хотя и дает приблизительное (почти оптимальное) решение за разумное время.

Компоненты жадного алгоритма

Жадные алгоритмы имеют следующие пять компонентов -

  • Набор кандидатов - решение создано из этого набора.

  • Функция выбора - используется для выбора лучшего кандидата для добавления в решение.

  • ТЭО - используется для определения того, можно ли использовать кандидата для внесения вклада в решение.

  • Целевая функция - используется для присвоения значения решению или частичному решению.

  • Функция решения - используется, чтобы указать, было ли достигнуто полное решение.

Области применения

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

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

  • Нахождение минимального остовного дерева в графе с использованием алгоритма Прима / Крускала и т. Д.

Там, где терпит неудачу жадный подход

Во многих задачах алгоритм Жадного не может найти оптимальное решение, более того, он может привести к худшему решению. Такие проблемы, как Traveling Salesman и Knapsack, не могут быть решены с помощью этого подхода.