Когда применим жадный алгоритм. Как узнать, даст ли жадный алгоритм оптимум применительно к данной задаче Общих рецептов тут нет, но существует две особенности, характерные для задач, решаемых жадными алгоритмами.
Это принцип жадного выбора и свойство оптимальности для подзадач. 4. Принцип жадного выбора Говорят, что к оптимизационной задаче применим принцип жадного выбора greedy-choice property, если последовательность локально оптимальных жадных выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так на каждом шаге жадный алгоритм берет самый жирный кусок, а потом уже пытается сделать наилучший выбор среди оставшихся, каковы бы они ни были алгоритм динамического программирования принимает решение, просчитав заранее последствия для всех вариантов.
Как доказать, что жадный алгоритм дает оптимальное решение Это не всегда тривиально, но в типичном случае такое доказательство следует схеме, использованной в доказательстве теоремы 1. Сначала мы доказываем, что жадный выбор на первом шаге не закрывает пути к оптимальному решению для всякого решения есть другое, согласованное с жадным выбором и не худшее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции. 5.