Алгоритм динамического программирования — это алгоритм разрешения больших задач путем подразделения их на набор мелких подзадач.
Введение
В теории управления применяется термин динамическое программирование, обозначающий методику разрешения глобальных задач за счёт разделения их на ряд простых подзадач. Динамическое программирование может применяться для задач, имеющих оптимальную структуру, которая представляет собой комплекс взаимосвязанных подзадач со сложностью немного меньше сложности общей поставленной задачи. При такой организации значительно уменьшается суммарное время вычислений, если сравнивать с обычной методикой решения. Основная суть динамического программирования не отличается сложностью. Обычно, для решения поставленной задачи, необходимо начать с решения отдельных её составных частей (подзадач), а затем сформировать из набора решений подзадач одно итоговое решение. Нередко какое-то число подзадач может оказаться одинаковыми по своей сути.
Оптимальная концепция динамического программирования предполагает однократное решение каждой подзадачи, что существенно сокращает число вычислительных операций. Это очень важно при огромном количестве повторяющихся подзадач.
Способ динамического программирования сверху подразумевает обычную память итогов решения повторяющихся подзадач и использование этих итогов при повторной встрече с подзадачей. Динамическое программирование снизу подразумевает изменение формулировки большой задачи, с целью преобразовать её в рекурсивную очерёдность лёгких подзадач.
История динамического программирования
Термин «динамическое программирование» был введён в сороковых годах прошлого века Ричардом Беллманом, чтобы описать процедуру разрешения задачи, в которой итоговый результат получается лишь после решения предыдущей задачи. Позднее он развил определение этого термина до современного уровня. Изначально эта сфера начиналась как системный анализ и инжиниринг, и её признал IEEE (институт инженеров электротехники и электроники). Имя Беллмана и его вклад в динамическое программирование увековечено в термине «уравнение Беллмана», которое стало базой теории динамического программирования. Это уравнение даёт формулировку оптимизационной задачи в рекурсивной форме.
Следует, однако заметить, что термин «программирование» в сочетании слов «динамическое программирование» на самом деле к программированию, как написанию кодов программы, почти не относится, а обладает смысловым значением словосочетания «математическое программирование», являющееся аналогом оптимизации. Поэтому термин «программа» в этом смысле больше подразумевает оптимальную очерёдность операций для нахождения решения задачи. Например, конкретное распределение очерёдности событий на выставке часто называется программой. То есть программа в контексте динамического программирования должна восприниматься в формате допустимой очерёдности событий.
Алгоритм динамического программирования
Наличие оптимальной подструктуры в динамическом программировании значит, что оптимизированное разрешение более мелких подзадач возможно использовать для решения общей глобальной задачи. Например, самый короткий маршрут в графе из вершины, которую обозначим s, к другой вершине, которую обозначим t, возможно определить следующим образом. В начале, вычисляется самый короткий маршрут из всех вершин, которые являются смежными с вершиной s, до вершины t. А далее, принимая во внимание веса рёбер, которые соединяют s со смежными вершинами, выбирается наилучший маршрут до вершины t, то есть через какие вершины следует пройти. Для решения задачи, где есть оптимальная подструктура, в обобщённом виде необходимо выполнить такие действия:
- Разделить общую задачу на набор подзадач уменьшенного объёма.
- Выполнить в рекурсивном режиме вычисление оптимального решения подзадач по этому-же алгоритму.
- Применить найденные решения подзадач для формирования решения поставленной начальной задачи.
Сами подзадачи возможно решить также с помощью дальнейшего подразделения их на ещё более мелкие подзадачи и так далее до тех пор, пока решение не опустится до уровня тривиальной задачи, которая решается практически сразу. Например, если необходимо определить n!, то уровнем тривиальности станет 1! =1.
Подзадачами с перекрытием в динамическом программировании являются такие подзадачи, которые применяются для разрешения некоторого числа задач, больших по размерам (то есть фактически необходимо какое-то число раз делать одни и те же операции). Самым хорошим примером таких действий можно считать определение последовательности Фибоначчи:
Рисунок 1. Последовательности Фибоначчи. Автор24 — интернет-биржа студенческих работ
F3 = F2 + F1 и F4 = F3 + F2.
Здесь даже на самом тривиальном уровне для определения только двух чисел Фибоначчи уже дважды выполнен подсчёт F2. Если вести вычисления в таком же духе и дальше и найти F5, то F2 нужно будет считать ещё пару раз, поскольку, чтобы вычислить F5, потребуются снова F3 и F4. Вывод следующий: если использовать упрощённый рекурсивный способ, то будет тратиться время на повторное решение уже однажды разрешённых задач. Чтобы этого не происходило, следует запоминать итоги решения подзадач, которые уже решены, и, если вновь возникнет необходимость решать такую подзадачу, нужно вместо её повторного решения просто извлечь это решение из памяти. Такой метод принято называть мемоизацией.
Существуют ещё пути для более глубокой оптимизации. К примеру, если существует уверенность, что итоговые решения подзадачи больше не будут нужны, то их можно просто удалить, очистив память для новых задач. Или, например, если процессор не загружен, а точно известно, что есть нерешённые подзадачи, которые могут понадобиться в будущем, то возможно осуществить их решение заранее.
Если подвести итоги всему, изложенному выше, то следует заметить, что динамическое программирование использует такие свойства задач:
- Свойство перекрытия подзадач.
- Свойство оптимальности подструктуры.
- Память компьютера позволяет запомнить решение наиболее распространённых подзадач.
