Жадный алгоритм (Greedy Algorithm) Скачать в PDF

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

Во многих задачах жадная стратегия не дает оптимального решения, но, тем не менее, может привести к локально-оптимальным решениям, которые аппроксимируют глобально-оптимальное решение за разумное время. Жадный алгоритм содержит 5 компонентов:

1. Набор кандидатов, из которого создается решение.
2. Функция выбора, которая выбирает лучшего кандидата для добавления в решение.
3. Функция технико-экономического обоснования, которая используется для определения, может ли кандидат использоваться для содействия решению.
4. Целевая функция, которая присваивает значение решению или частичному решению.
5. Функция решения, которая укажет, когда будет обнаружено полное решение.

Многие алгоритмы, используемые в Data Mining, являются жадными, например, алгоритм покрытия, алгоритмы построения деревьев решений и др.