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

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

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

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

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

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

A candidate set - Из этого набора создается решение.
A selection function - Используется для выбора лучшего кандидата для добавления в решение.
A feasibility function - Используется, чтобы определить, можно ли использовать кандидата для внесения вклада в решение.
An objective function - Используется для присвоения значения решению или частичному решению.
A solution function - Используется, чтобы указать, было ли достигнуто полное решение.

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

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

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

Где жадный подход терпит неудачу

In many problems, Greedy algorithm fails to find an optimal solution, moreover it may produce a worst solution. Problems like Travelling Salesman and Knapsack cannot be solved using this approach.