Определение

Жадный алгоритм - это алгоритм, который на каждом этапе работы выбирает оптимальное решение (локально). Оптимальное решение для каждой задачи индивидуально

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

Случаи, в которых жадный алгоритм оптимален

1. Если выбор локального оптимального решения не отрежет пути к глобальному оптимуму (оптимум - наилучший вариант решения задачи).
2. Подзадача, возникшая после первого выбора, идентична начальной.
3. Если задача имеет структуру матроида.

Матроид

Матроид - это пара $M = (X, S)$, обладающая следующими свойствами:

1. $X$ - непустое конечное множество.
2. $S$ - непустое семейство подмножеств $X$, где $X$ - независимые подмножества.
3. $∅ ∈ S$.
4. Если множество принадлежит $S$, то и все его подмножества принадлежат $S$.
5. Если $А$, $В$ $∈ S$ и $|А| > |В|$, тогда существует элемент $m ∉ A$ и $m ∉ B$, такой, что, если его добавить к $В$, получится множество $С ∈ S$ ($A$, $B$, $C$ - множества).

Матроид называется взвешенным, если на множестве $S$ задана весовая функция, значения которой содержатся во множестве положительных чисел.

Некоторые оптимизационные задачи сводятся к нахождению во взвешенном матроиде $M = (X, S)$ независимого подмножества с оптимальным весом, например, задача о минимальном остовном дереве.