7.Динамическое программирование
 

Многие прикладные задачи сводятся к отысканию минимума (максимума) некоторой функции на некотором множестве. Очень, часто это множество представляет собой последовательность элементов а₁, a₂,...,a_n. Тогда получаем задачу поиска минимума в множестве последовательностей. Искомый минимум может быть получен путем полного перебора всех последовательностей. Meтод динамического программирования позволяет сократить перебор.

Пусть определена функция F, которая сопоставляет некоторое число каждой последовательности из некоторого допустимого множества допустимых последовательностей. Требуется найти такую последовательность а₁, a₂,...,a_n, которая минимизирует функцию F(a₁,...,a_n). Метод динамического программирования применим только тогда, когда функция F удовлетворяет принципу оптимальности Беллмана. Этот принцип требует, чтобы всякий отрезок a_i, a_i+1,…,a_m оптимальной последовательности а₁, a₂,...,a_n (1 ≤ i≤m≤n) был бы сам оптимальным среди всех отрезков совпадающих с ним по числу элементов и в крайних элементах. Это свойство позволяет найти оптимальную последовательно, постепенно удлиняя уже найденные от начала (конца) последовательности отрезки. Важным классом функций, удовлетворяющих принципу оптимальности Беллмана, являются аддитивные функции, равные сумме некоторых функций, зависящих только от соседних элементов последовательности: F(a₁...,a_n) =∑G(a_i,a_i+1)

Динамическим программированием называют процесс пошагового решения задач, когда на каждом шаге выбирается одно решение из множества допустимых на этом шаге решений, причём такое, которое оптимизирует заданную функцию.

В качестве примера можно привести задачу поиска кратчайшего, пути на графе. Будем считать, что элементами последовательности являются n вершин графа. Всей последовательности соответствует путь по графу, проходящий по перечисленным в ней вершинам. Функция G сопоставляет каждой дуге графа ее длину: G(i,j) — длина дуги от вершины i к вершине j, а ∑G(i,j) суммарная длина пути, задаваемого последовательностью. Задача поиска оптимальной последовательности здесь и является задачей поиска кратчайшего пути на графе между начальной и конечной вершинами или кратчайших путей, между заданной вершиной и всеми остальными. Метод динамического программирования сводит перебор всех путей к перебору вершин графа, которых обычно меньше, чем путей.