Решения проблем с использованием динамического программирования или жадных методов?
Какие свойства должна иметь проблема, чтобы я мог решить, какой метод использовать динамическое программирование или жадный метод?
4 ответа
Задачи динамического программирования имеют оптимальную структуру. Это означает, что решение проблемы может быть выражено как функция решений подзадач, которые строго меньше.
Одним из примеров такой проблемы является умножение цепочки матриц.
Жадные алгоритмы могут использоваться только тогда, когда локально оптимальный выбор приводит к полностью оптимальному решению. Это может быть сложнее сразу увидеть, но, как правило, легче реализовать, потому что у вас есть только одна вещь (жадный выбор), а не несколько (решения для всех небольших подзадач).
Один известный жадный алгоритм - алгоритм Крускала для нахождения минимального остовного дерева.
Во втором издании книги Алгоритмов Кормена, Лизерсона, Ривеста и Штейна есть раздел (16.4) под названием "Теоретические основы жадных методов", в котором обсуждается, когда жадные методы дают оптимальное решение. Он охватывает много случаев, представляющих практический интерес, но не все жадные алгоритмы, дающие оптимальные результаты, могут быть поняты с точки зрения этой теории.
Я также натолкнулся на статью под названием "От динамического программирования к жадным алгоритмам", в которой говорится, что некоторые жадные алгоритмы можно рассматривать как усовершенствования динамического программирования. Из быстрого сканирования это может вас заинтересовать.
Там действительно строгое правило знать это. Как кто-то уже сказал, есть некоторые вещи, которые должны включить красный свет, но в конце концов, только опыт сможет сказать вам.
Мы применяем жадный метод, когда можно принять решение по локальной информации, доступной на каждом этапе. Мы уверены, что, следуя набору решений на каждом этапе, мы найдем оптимальное решение. Тем не менее, в динамическом подходе мы не можем быть уверены в принятии решения на одном этапе, поэтому мы несем набор вероятных решений, один из вероятных элементов может принять решение.