Решения проблем с использованием динамического программирования или жадных методов?

Question

Какими свойствами должна обладать проблема, чтобы я мог решить, какой метод использовать для динамического программирования или жадный метод?

Answer 1

Задачи динамического программирования демонстрируют оптимальную подструктуру.Это означает, что решение проблемы может быть выражено как функция от решений подзадач, которые строго меньше.

Одним из примеров такой проблемы является умножение цепочки матриц .

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

Один известный жадный алгоритм - это Алгоритм Крускала для нахождения минимального остовного дерева.

Answer 2

Во втором издании книги Алгоритмов Кормена, Лизерсона, Ривеста и Штейна есть раздел (16.4) под названием «Теоретические основы жадных методов», в котором обсуждается, когда жадные методы дают оптимальное решение.Он охватывает много случаев, представляющих практический интерес, но не все жадные алгоритмы, дающие оптимальные результаты, могут быть поняты с точки зрения этой теории.

Я также натолкнулся на статью «От динамического программирования к жадным алгоритмам», связанную здесь , который говорит об определенных жадных алгоритмах, может рассматриваться как усовершенствование динамического программирования.Из быстрого сканирования это может вас заинтересовать.

Answer 3

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

Answer 4

Есть действительно строгое правило знать это. Как кто-то уже сказал, есть некоторые вещи, которые должны включить красный свет, но в конце концов, только опыт сможет сказать вам.