Динамическое Программирование Задачи


Май 12, 2016 – 12:20
1 / 11

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

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

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

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

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

Типовой алгоритм решения задач методом динамического программирования:

  1. Описать строение оптимальных решений.
  2. Выписать рекуррентное соотношение, связывающие оптимальные значения параметра для подзадач.
  3. Двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач.
  4. Пользуясь полученной информацией, построить оптимальное решение.
Source: comp-science.narod.ru
Похожие публикации