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

Ответ 1

Динамическое программирование применимо к проблемам, демонстрирующим свойства:

• перекрывающиеся подзадачи и
• оптимальная субструктура.

Оптимальная подструктура означает, что вы можете с жадностью решать подзадачи и объединять решения для решения большей проблемы. Разница между динамическим программированием и жадными алгоритмами заключается в том, что при динамическом программировании существуют перекрывающиеся подзадачи, и эти подзадачи решаются с использованием memoization. "Memoization" - это метод, при котором решения подзадач используются для более быстрого решения других подзадач.

Этот ответ получил некоторое внимание, поэтому приведу несколько примеров.

Рассмотрим проблему "Внесение изменений в доллары, никели и пенни". Это жадная проблема. Он демонстрирует оптимальную подструктуру, потому что вы можете решить за количество долларов. Затем решите количество никеля. Затем количество пенни. Затем вы можете эффективно комбинировать решения с этими подзадачами. На самом деле он не имеет перекрывающихся подзадач, так как решение каждой подзадачи не очень помогает другим (возможно, немного).

Рассмотрим проблему "числа Фибоначчи". Он обладает оптимальной субструктурой, потому что вы можете эффективно решать F (10) из F (9) и F (8) (путем добавления). Эти подзадачи перекрываются, потому что они оба разделяют F (7). Если вы memoize результат F (7), когда вы решаете F (8), вы можете быстрее решить F (9).

В ответ на комментарий о том, что динамическое программирование связано с "переосмыслением решений": это, очевидно, неверно для любого алгоритма линейного динамического программирования, такого как максимальный подмассива проблема или проблема Фибоначчи выше.

По существу, представьте себе задачу, имеющую оптимальную субструктуру как ориентированный ациклический граф, узлы которого представляют подзадачи (где вся проблема представлена ​​ node, у которой неопределенность равна нулю), а направленные ребра представляют зависимости между подзадачами. Тогда жадная проблема - это дерево (все узлы, кроме корня, имеют единицу без ограничений). Проблема динамического программирования имеет некоторые узлы с не зависящими друг от друга. Это иллюстрирует перекрывающиеся подзадачи.

Ответ 2

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

Ответ 3

Ключевое различие заключается в том, что жадные алгоритмы составляют решения "статически" в том смысле, что каждый локальный выбор в решении может быть завершен без необходимости знать что-либо о других локальных вариантах. Однако динамические алгоритмы создают множество возможных решений для подзадач и генерируют единственное решение глобальной проблемы при рассмотрении всех подзадач. страница Википедии по жадным алгоритмам ставит ее хорошо:

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

Ответ 4

В алгоритмах DP используется тот факт, что (для некоторых задач) - оптимальное решение проблемы размера n составлено из оптимального решения проблемы размера n'<n и использует это для построения решения, от наименьшей проблемы до требуемого размера.

Он очень хорошо подходит к тому же принципу рекурсии (уменьшает проблему до меньшей суб-проблемы и вызывает рекурсивно), и действительно - решения DP часто представлены в виде рекурсивной формулы.

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

Хорошим примером различий между этими двумя подходами является проблема кратчайшего пути:

• Алгоритм Dijsktra - это жадный подход (на каждом шаге выбрал node, что путь к нему в настоящее время сведен к минимуму - выбор сделано жадно на основе локального состояния алгоритма).
• Алгоритм Беллмана-Форда - это решение DP ( "расслабление" всех краев, эффективно уменьшающее проблему).

Ответ 5

Жадный метод:

• Жадный метод фокусируется на расширении частично построенных решений.
• Он предоставляет множество результатов, таких как возможное решение.
• Более эффективный

Динамическое программирование:

• Фокусируется на принципе оптимальности.
• Он дает конкретные ответы.
• Менее эффективный

Ответ 6

Разница между DP и жадным DP будет искать глобальный оптимальный по каждой подзадаче, но жадный будет искать только локальный оптимальный. Итак, об этом сценарии:

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

Для жадного алгоритма вы всегда будете выбирать то, что кажется более крутым. Это оптимальное решение local и не гарантируется, что это приведет к лучшему результату

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

Ответ 7

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

Все еще есть примеры жадных алгоритмов, которые не являются DP-s: скажем, восхождение на холм - это жадный алгоритм, который не разбивает проблему на несколько подзадач - он всегда решает ее. Существуют также примеры ДП, которые не являются жадными - например, вычисление n-го числа Фибоначчи с использованием memoization не является жадным.