Что такое динамическое программирование

Время от времени в разных статьях упоминается динамическое программирование, которое начинающий программист может спутать с чем-нибудь вроде объектно-ориентированного программирования. «Типичный программист» попросил ведущего Java-разработчика EPAM, Александра Бармина, простым языком объяснить, что же такое динамическое программирование.

Вычислительная сложность многих задач не зависит от входных параметров, например, получение элемента по индексу в массиве не зависит от длины массива и всегда выполняется за константное время. В то же время есть задачи, для которых время выполнения линейно зависит от значения параметров, например, получение элемента по индексу в связанном списке ― чем больше элементов, тем больше времени потребуется на поиск нужного элемента. Естественно, существуют и задачи, для которых использование полного перебора требует слишком много времени, например, поиск кратчайшего маршрута между двумя городами в случае полного перебора потребует построение n! вариантов, что при больших n неэффективно.

Некоторые подобные задачи можно решить путем разбиения исходной задачи на подзадачи меньшего размера и сложности, решив которые и объединив результаты, можно получить решение исходной задачи. Такой подход называется динамическим программированием и был предложен Ричардом Беллманом в 1940-х годах.

Динамическое программирование придерживается двух подходов к решению задач:

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

Одной из самых известных задач динамического программирования является задача вычисления чисел Фибоначчи, и она эффективно решается методом восходящего динамического программирования. При использовании этого подхода для нахождения N-го элемента в последовательности происходит последовательное нахождение первого, второго и последующих элементов как суммы двух предыдущих. Данный подход имеет сложность O(N), в то время как использование классического рекурсивного подхода имеет приблизительную сложность O(2^N), что существенно больше.

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

Данную задачу можно решить методом полного перебора ― сгенерировать все возможные маршруты (всего их N!) для N адресов, а затем выбрать маршрут минимальной длины. Сложность данного алгоритма O(N! * N) и время вычисления очень быстро растет при росте количества адресов ― если для трех адресов нужно рассмотреть шесть вариантов, то для 10 уже около четырех миллионов!

Использование подходов динамического программирования может не дать наилучшего решения, но, тем не менее, оно будет достаточно хорошим и за приемлемое время. Суть подхода к решению данной задачи заключается в поиске ближайшего адреса на каждом шаге ― из исходной точки, затем следующего ближайшего пункта назначения из первого адреса и так далее. Полученное решение не будет идеальным, но потребует гораздо меньше времени ― O(N^2 * 2^N), что для тех же 10 адресов 1124 вычислений.

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

Комментарии других экспертов читай в статье.