В чем основное различие между динамическим программированием и жадным подходом с точки зрения использования?
Я заметил, что в некоторых проблемах жадный подход дает оптимальное решение, в какой-то момент времени динамический программный подход дает оптимальное решение. Существуют ли какие-либо особые условия (правила) для конкретного подхода?
Я столкнулся с таким количеством примеров, но не смог сделать стандартный вывод.
Основываясь на статьях Википедии.
Жадный алгоритм - это алгоритм, который следует за решением проблемы эвристики решения локально оптимальный выбор на каждом этапе [1] с надеждой найти глобальный оптимум. В многие проблемы, жадная стратегия вообще не дает оптимального решения, но тем не менее жадная эвристика может дать локально оптимальные решения, которые приближают глобальное оптимальное решение в разумные сроки.
Мы можем сделать любой выбор лучше всего на данный момент, а затем решить подзадачи, которые возникнут позже. Выбор, сделанный жадным алгоритмом, может зависеть от выбора, сделанного до сих пор , но не от будущих выборов или всех решений подзадачи. Он итеративно делает один жадный выбор за другим, уменьшая каждую заданную проблему до меньшей.
Идея динамического программирования довольно проста. В общем, для решения данной проблемы нам необходимо решить разные части задачи (подзадачи), , затем объединить решения подзадач для достижения общего решения. Часто при использовании более наивного метода многие подзадачи генерируются и решаются много раз. Метод динамического программирования направлен на решение каждой подзадачи только один раз, что уменьшает количество вычислений: после того как решение по заданной подзадаче было вычислено, оно сохраняется или "запоминается": в следующий раз то же самое решение необходимо, оно просто просматривается. Этот подход особенно полезен, когда количество повторяющихся подзадач растет экспоненциально в зависимости от размера ввода.
Мы можем сделать любой выбор лучше всего на данный момент, а затем решить подзадачи, которые возникнут позже. Выбор, сделанный жадным алгоритмом, может зависеть от выбора, сделанного до сих пор, но не от будущих выборов или всех решений подзадачи. Он итеративно делает один жадный выбор за другим, уменьшая каждую заданную проблему до меньшей. Другими словами, жадный алгоритм никогда не пересматривает свой выбор.
Это основное отличие от динамического программирования, которое является исчерпывающим и гарантированно найдет решение. После каждого этапа динамическое программирование принимает решения на основе всех решений, принятых на предыдущем этапе, и может пересмотреть алгоритмический путь предыдущего этапа к решению
Например, скажем, что вам нужно как можно быстрее добраться из пункта A в пункт B в конкретный город в час пик. Алгоритм динамического программирования рассмотрит весь отчет о трафике, изучит все возможные комбинации дорог, которые вы можете предпринять, и только потом скажет вам, какой путь является самым быстрым. Конечно, вам придется подождать некоторое время, пока алгоритм не закончится, и только тогда вы сможете начать движение. Путь, который вы предпримете, будет самым быстрым (при условии, что во внешней среде ничего не изменилось).
С другой стороны, жадный алгоритм сразу начнет вас водить и выберет дорогу, которая будет выглядеть быстрее всего на каждом перекрестке. Как вы можете себе представить, эта стратегия может не привести к быстрому времени прибытия, поскольку вы можете занять несколько "простых" улиц, а затем оказаться безнадежно застрявшими в пробке.
В математической оптимизации жадные алгоритмы решают комбинаторные задачи, обладающие свойствами matroids.
Динамическое программирование применимо к задачам, демонстрирующим свойства перекрывающихся подзадач и оптимальной субструктуры.
Я хотел бы привести абзац, в котором говорится о существенном различии между жадными алгоритмами и алгоритмами динамического программирования, изложенными в книге Введение в алгоритмы (3-е издание) by Cormen, глава 15.3, стр. 381:
Одним из основных различий между жадными алгоритмами и динамическим программированием является то, что вместо того, чтобы сначала находить оптимальные решения подзадач, а затем делать осознанный выбор, жадные алгоритмы сначала делают жадный выбор, выбор, который лучше всего выглядит в то время, а затем в результате подзадача, без необходимости решать все возможные связанные с этим небольшие подзадачи.
В простых словах мы можем сказать, что в Dynamic Programming (проблема с отправкой сообщения по сети) сначала можно проверить путь, который занимает кратчайшее время, а затем начать путешествие,
С другой стороны Greedy algorithm возьмите optimal decision на месте, не думая о следующем шаге, и на следующем шаге снова измените свое решение и так далее...
Notes: Dynamic Programming является надежным, а Greedy Algorithms не всегда надежным.