Определение:
Жадными называют алгоритмы, выбирающие только ту информацию, которая удовлетворяет определённым критериям.
Жадный алгоритм содержит пять основных компонентов:
- Набор кандидатов (candidate set), на основе которого создаётся решение.
- Функция выбора, которая решает, какой лучший кандидат будет добавлен в решение.
- Функция обоснования (feasibility function), которая решает, может ли кандидат внести вклад в решение.
- Целевая функция (objective function), которая присваивает значение решению или частичному значению.
- Функция решения (solution function), которая сигнализирует о том, что мы нашли полное решение.
Что вам нужно знать:
- Жадные алгоритмы используются для поиска оптимального решения данной проблемы.
- Обычно они применяются к наборам данных, в которых лишь небольшая порция обработанной информации даёт желаемый результат.
- Часто жадные алгоритмы могут помочь в уменьшении «О» большого другого алгоритма.
Псевдокод жадного алгоритма для поиска самой большой разницы между двумя числами в массиве