Приведем сначала небольшой пример.
Допустим, что у нас есть денежные купюры достоинством 10, 50, 100 и 500 рублей и нужно вернуть сдачу 860 рублей. Почти не раздумывая, мы преобразуем эту величину в купюру 500 рублей, 3 купюры по 100 рублей, 1 купюру 50 рублей и 1 купюру 10 рублей. Таким образом, нам быстро удалось найти самый короткий список купюр. Данный алгоритм заключался в выборе купюры самого большого достоинства (500 рублей), но не больше 860 рублей, добавлению ее в список сдачи и вычитанию ее стоимости из 860 (получается 360 рублей). Затем снова выбираем купюру самого большого достоинства, но не больше остатка (360 рублей): этой купюрой оказывается сторублевая. Ее мы опять добавляем в сдачу, вычитаем ее стоимость из остатка и т.д.
Такой алгоритма называется «жадным» алгоритмом. На каждом шаге «жадный» алгоритм выбирает локально оптимальное в том или ином смысле решение. Обратите внимание, что алгоритм для определения сдачи обеспечивает в целом оптимальное решение лишь вследствие особых свойств купюр. Подчеркнем, что не все «жадные» алгоритмы позволяет получить оптимальный результат. Нередко бывает, что «жадная стратегия» подчас обеспечивает лишь сиюминутную выгоду, однако в целом результат может оказаться неоптимальным.
Есть задачи, для которых ни один из известных «жадных» алгоритмов не дает получить оптимального решения, однако имеются «жадные» алгоритмы, которые с очень большой вероятностью дают «хорошие» решения. Например, ответ отличается от оптимального лишь на пару процентов и погрешность не существенна. В таких случаях «жадный» алгоритм может оказаться самым быстрым способом получить «хорошее» решение. Если задача такова, что единственным способом получить оптимальное решение является использование метода исчерпывающего перебора, тогда «жадный» алгоритм может оказаться единственным реальным средством быстрого достижения результата.
Можно ли узнать, даст ли жадный алгоритм оптимальное решение в данной задаче? Конкретного ответа тут нет, но существуют две особенности, характерные для задач, решаемых жадными алгоритмами. Это принцип жадного выбора и свойство оптимальности для подзадач.
Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных (жадных) шагов дает глобально оптимальное решение.
Жадный алгоритм можно описать примерно так: на каждом этапе жадный алгоритм берёт «самый большой кусок», а потом уже пытается выбрать самый большой среди оставшихся, каковы бы они ни были.
Доказательство оптимальности жадного алгоритма можно построить по следующей схеме:
- Показываем, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не худшее первого.
- После этого показываем, что оставшаяся подзадача аналогична исходной. Завершаем доказательство по индукции.
Основной областью применения «жадных» алгоритмов являются задачи поиска и оптимизации. Классическим является алгоритм Дейкстры поиска кратчайшего пути между двумя вершинами неориентированного графа с положительными весами. В отдельных случаях «жадная» стратегия используется для получения «хорошего» начального приближения к оптимальному решению.