Учебники

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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