#algorithm
#алгоритм
Вопрос:
Когда у меня возникает проблема с оптимальной подструктурой и ни одна подзадача не разделяет подзадачи, я могу использовать алгоритм «разделяй и властвуй» для ее решения?
Но когда подзадача разделяет подзадачи (перекрывающиеся подзадачи), тогда я могу использовать динамическое программирование для решения проблемы?
Это правильно?
И чем жадные алгоритмы похожи на динамическое программирование?
Ответ №1:
Когда у меня возникает проблема с оптимальной подструктурой и ни одна подзадача не разделяет подзадачи, я могу использовать алгоритм «разделяй и властвуй» для ее решения?
Да, если вы можете найти оптимальный алгоритм для каждого вида подзадач.
Но когда подзадача разделяет подзадачи (перекрывающиеся подзадачи), тогда я могу использовать динамическое программирование для решения проблемы?
Это правильно?
ДА. Динамическое программирование — это, по сути, частный случай семейства алгоритмов «Разделяй и властвуй», где все подзадачи одинаковы.
И чем жадные алгоритмы похожи на динамическое программирование?
Они разные.
Динамическое программирование дает вам оптимальное решение.
Жадный алгоритм обычно дает хорошее / справедливое решение за небольшой промежуток времени, но это не гарантирует достижения оптимального.
Это, скажем, похоже, потому что обычно делит построение решения на несколько этапов, на которых выбираются локально оптимальные варианты. Но если этапы не являются оптимальными подструктурами исходной задачи, то обычно это не приводит к лучшему решению.
Редактировать:
Как указал @rrenaud, существуют некоторые жадные алгоритмы, которые оказались оптимальными (например, Дейкстра, Крускал, Прим и т.д.).
Итак, если быть более точным, основное различие между жадным и динамическим программированием заключается в том, что первое не является исчерпывающим в пространстве решений, в то время как второе является.
На самом деле жадные алгоритмы недальновидны в этом пространстве, и каждый выбор, сделанный во время построения решения, никогда не пересматривается.
Комментарии:
1. Некоторые жадные алгоритмы являются оптимальными. Рассмотрим алгоритм кратчайших путей Дейкстры или задачу о сумме максимального подмассива. Жадные алгоритмы, как правило, не разветвляются на разные возможности, тогда как алгоритмы динамического программирования имеют тенденцию разветвляться на разные, возможно, оптимальные варианты, а затем определять, какой из вариантов был лучшим.
2. не могли бы вы, пожалуйста, объяснить «Динамическое программирование — это, по сути, частный случай семейства алгоритмов «Разделяй и властвуй», где все подзадачи одинаковы». Я этого не понимаю. подзадачи означают то же самое?
3. @grassPro: я имею в виду, что для динамического программирования требуется задача, разделяемая на подзадачи одного типа, потому что вы всегда используете одну и ту же процедуру, рекурсивно решающую основную проблему и подзадачи.
4. Эмпирическое правило, которое я усвоил, заключается в том, что динамическое программирование идеально подходит для задач, которые можно разложить на «дискретные, перекрывающиеся подмножества». Перекрывающаяся часть — это то, что заставляет динамическое программирование работать.
Ответ №2:
Динамическая программа использует подход «снизу вверх», сохраняет предыдущее решение и ссылается на него, это позволит нам найти оптимальное решение среди всех доступных решений, в то время как жадный подход использует подход «сверху вниз», поэтому он берет оптимальное решение из локально доступного решения, не принимает решения предыдущего уровня, что приводит к менее оптимизированному решению. Динамическое = снизу вверх, оптимальное решение, Жадное = сверху вниз, менее оптимальное, отнимающее меньше времени