DAA - динамическое программирование

Динамическое программирование также используется в задачах оптимизации. Как и метод «разделяй и властвуй», динамическое программирование решает проблемы путем объединения решений подзадач. Более того, алгоритм динамического программирования решает каждую подзадачу всего один раз, а затем сохраняет свой ответ в таблице, тем самым избегая повторного вычисления ответа каждый раз.

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

Перекрывающиеся подзадачи

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

Например, бинарный поиск не имеет перекрывающейся подзадачи. В то время как рекурсивная программа чисел Фибоначчи имеет много пересекающихся подзадач.

Оптимальная подструктура

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

Например, задача кратчайшего пути имеет следующее оптимальное свойство подструктуры -

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

Стандартные алгоритмы All Pair Shortest Path, такие как Floyd-Warshall и Bellman-Ford, являются типичными примерами динамического программирования.

Шаги подхода динамического программирования

Алгоритм динамического программирования разработан с использованием следующих четырех шагов -

  • Охарактеризуйте структуру оптимального решения.
  • Рекурсивно определить значение оптимального решения.
  • Вычислить значение оптимального решения, как правило, восходящим способом.
  • Построить оптимальное решение из вычисленной информации.

Применение подхода динамического программирования

  • Матричное умножение
  • Самая длинная общая подпоследовательность
  • Задача коммивояжера