21. Что такое жадные алгоритмы? Приведите пример.

Жадные алгоритмы являются одной из 3х техник создания алгоритмов, вместе с принципом Разделяй и властвуй и динамическим программированием.

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

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

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

Предыдущий вопрос: 20. Что такое рекурсия? Сравните преимущества и недостатки итеративных и рекурсивных алгоритмов. С примерами.

Следующий вопрос: 22. Расскажите про пузырьковую сортировку.

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку: напишите мне