Чем динамическое программирование отличается от грубой силы

Я читал о динамическом программировании, когда наткнулся на следующую цитату

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

Следующий пример был приведен

Например, предположим, что вам нужно как можно быстрее добраться из пункта А в пункт Б в данном городе в час пик. Алгоритм динамического программирования просматривает весь отчет о дорожном движении, просматривая все возможные комбинации дорог, которые вы можете выбрать, и только потом сообщит вам, какой путь является самым быстрым. Конечно, вам, возможно, придется подождать некоторое время, пока алгоритм не завершится, и только тогда вы сможете начать движение. Путь, который вы выберете, будет самым быстрым (при условии, что во внешней среде ничего не изменилось)

Brute Force пробует все возможные решения, прежде чем выбрать лучшее решение.

Чем динамическое программирование отличается от Brute Force, если оно также проходит через все возможные решения, прежде чем выбрать лучшее , единственное различие, которое я вижу, состоит в том, что динамическое программирование учитывает дополнительные факторы (в данном случае условия трафика).

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

Алгоритм динамического программирования рассмотрит все возможные пути решения проблемы и выберет лучшее решение.

Это утверждение просто неправильно.

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

Тот факт, что это дает оптимальное решение исходной задачи, не является тривиальным и фактически имеет место только для некоторых задач. А именно те, которые удовлетворяют принципу оптимальности Беллмана (одно из самых сомнительных, неправильно понимаемых «определений», которые регулярно цитируются). Смотрите здесь, чтобы узнать больше об этом.

В качестве конкретного примера рассмотрим алгоритм Беллмана-Форда на полном графе с единичными весами: он рассматривает только пути длины один и два (т. Е. Θ ( n 2 ) много), потому что те, которые используют одно ребро, являются оптимальными . Но существует бесконечно много решений, если вы не ограничите максимально допустимое количество ребер, и все равно ≫ ( n - 1 ) ! многие, если вы разрешите использовать каждый узел только один раз. Очевидно, что Bellman-Ford - алгоритм динамического программирования - не выполняет поиск методом "грубой силы".$K_n$$\Theta(n^2)$$\gg (n-1)!$

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

Различие, которое может попытаться сделать статья в Википедии, заключается в трех типах алгоритмов:

1. Алгоритмы, которые перебирают все возможные решения, выбирая оптимальный.

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

3. Алгоритмы, которые охватывают подмножество всех возможных решений, без гарантии того, что оптимальное решение принадлежит подмножеству.

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

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

1. Попробуйте все возможные пути. Это известно как грубая сила .

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

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

Эти примеры довольно грубые и, возможно, не дают очень точную картину. Обрезка имеет решающее значение во многих ситуациях, например, в компьютерных шахматах. Если вам интересно, посмотрите алгоритм A ^* , который на самом деле используется для кратчайшего пути.

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

$t$$t$$t+1$$t$

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

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

Это просто. Динамическое программирование - это «стратегия поиска», которая использует дополнительные факторы для сужения поиска. Если нет никакого решения в пространстве поиска, динамическое программирование будет ( как правило) делать поиск через каждый элемент пространства поиска. Но это не значит, что это поиск грубой силы.

Утверждение о том, что динамическое программирование - это интеллектуальная грубая сила, является правильным, но его трудно понять с помощью этой фразы. Смысл динамического программирования, как правило, состоит в том, чтобы разобраться в проблеме и разумным образом разбить ее на более мелкие части. После того, как вы это сделаете, вы будете использовать грубую силу, чтобы решить каждую маленькую фигуру, а затем снова будете использовать грубую силу, чтобы соединить фигуры в окончательное решение. Таким образом, хотя вы можете с уверенностью сказать, что динамическое программирование - это тип решения грубой силы, хитрость заключается в том, как вы используете эту грубую силу.