Разделяй и властвуй, динамическое программирование и жадные алгоритмы!

Question

Если у меня есть проблема с оптимальной подструктурой и нет подзадачи, которая разделяет подзадачи, тогда я могу использовать алгоритм «разделяй и властвуй» для ее решения?

Но когда подзадача разделяет подзадачи (перекрывающиеся подзадачи), тогда я могу использовать динамическое программирование для решения проблемы?

Это правильно?

А чем жадные алгоритмы похожи на динамическое программирование?

Answer 1

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

Да, если вы можете найтиоптимальный алгоритм для каждого вида подзадачи.

Но когда подзадача разделяет подзадачи (перекрывающиеся подзадачи), тогда я могу использовать динамическое программирование для решения проблемы?

Это правильно?

Да.Динамическое программирование в основном является частным случаем семейства алгоритмов «разделяй и властвуй», где все подзадачи одинаковы.

А чем жадные алгоритмы похожи на динамическое программирование?

Они разные.
Динамическое программирование дает вам оптимальное решение.
Алгоритм Greedy обычно дает хорошее / справедливое решение за небольшое время, но не гарантирует достижения оптимального.

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

РЕДАКТИРОВАТЬ:

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

Answer 2

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

Answer 3

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

см. Ссылку http://en.wikipedia.org/wiki/File:Greedy-search-path-example.gif