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

Ричард Беллман был первым, кто придумал это имя. Он хотел изучить такого рода проблемы еще в 1950-х годах, когда служил в ВВС США. Проблема в том, что в то время ВВС не хотели тратить деньги на математические исследования. Чтобы обойти это, Беллман придумал бессмысленное название (Динамическое программирование), чтобы он мог продолжать работать над ним тайно, поскольку, по-видимому, никто не стал бы подвергать сомнению или пытаться действительно понять, что это за новый термин. Более подробную информацию об этой истории можно найти в этом отличном уроке MIT ¹.

В этом посте показана общая стратегия решения задач DP с помощью математической индукции. Все сводится к этим трем шагам:

  1. Напишите формулу, описывающую решение проблемы как «смесь» подзадач одного типа. Под «смешиванием» я подразумеваю использование какой-то логики. Иногда достаточно простого сложения / вычитания / умножения. В других случаях вам может потребоваться определить отдельную функцию. В терминах индукции это называется гипотезой.
  2. Вычислите все начальные счастливые случаи, то есть случаи, которые не требуют знания подзадач, которые нужно решить. В терминах индукции это называется базовым случаем.
  3. Примените формулу, найденную на шаге 1, к остальным случаям, которых не было в шаге 2.

Сказанное лучше проиллюстрируем на примере. Давайте решим классическую задачу DP: найти кратчайший путь в сетке.

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

Разрешены только движения сверху вниз и слева направо.

Каждый раз, когда вы посещаете ячейку, вы увеличиваете свой номер пути на сумму в этой ячейке. Например, если вы решите перейти в красную ячейку, сначала пройдя первую строку, а затем опустившись в последний столбец, ваши затраты будут 5 + 3 + 2 + 1 + (- 2) + 7 + 4 + (- 3) + 2 + 7 + 2 = 28. Задача просит вас определить минимальную стоимость проезда к красной ячейке с учетом указанных выше ограничений на перемещение.

У нас есть несколько стратегий, чтобы решить эту проблему:

  1. Грубая сила

Этот подход просто проверяет ВСЕ возможные пути. Когда алгоритм достигает красной ячейки, он проверяет, является ли это кратчайшим из найденных до сих пор путей. Сложность этого алгоритма O (n + m)! где «n» - количество строк, а «m» - количество или столбцов сетки².

2. Возврат

Это немного лучше, чем Грубая сила. В режиме грубой силы алгоритм останавливается только тогда, когда достигает нижнего правого угла сетки. Отслеживание с возвратом немного умнее. Нет необходимости продолжать путь, если текущая сумма уже больше, чем наименьший путь, известный в настоящее время. Сложность этого алгоритма тоже O (n + m)! так как в худшем случае возврат с возвратом не выполняется, и алгоритм должен проверять каждый путь до конца, как и грубая сила.

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

Чтобы найти алгоритм DP, который решает эту проблему, давайте воспользуемся нашим рецептом. Во-первых, давайте определим решение как «смесь» подзадач. Предположим, что у нас есть решение для некоторой подсетки 2x2 (это наши индукционные гипнозы):

На изображении выше мы знаем, что кратчайший путь от верхнего левого угла (синяя ячейка) до ячейки [u, v] равен 100. Точно так же кратчайший путь от верхнего левого угла до ячейки [u + 1, v] равно 120, а один в [u, v + 1] - 115. Вам, вероятно, интересно, КАК мы получили эти числа. А пока просто предположим, что они у нас есть волшебным образом (то есть, это наша гипотеза индукции). Итак, чтобы найти кратчайший путь к ячейке [u + 1, v + 1], у нас есть только 2 варианта: либо путь идет сверху (т.е. из ячейки [u, v + 1]), либо из left (т.е. из ячейки [u + 1, v]), потому что мы разрешаем перемещение только слева направо и сверху вниз. Мы знаем как кратчайшие пути из ячейки выше, так и из ячейки слева (115 и 120). Следовательно, нам просто нужно выбрать тот, у которого пока самый короткий путь (115), и просуммировать значение самой ячейки [u + 1, v + 1]. Это дает нам, что кратчайший путь от верхнего левого угла до ячейки [u + 1, v + 1] равен 115 + grid [u + 1, v + 1]. Мы можем математически приравнять вышеуказанное:

shortestPath[u+1][v+1] = min(shortestPath[u][v+1],
                             shortestPath[u+1][v]) + grid[u+1][v+1]

У нас есть рекурсивная формула, которую требует шаг 1. Теперь перейдем к шагу 2, т. Е. Найдем счастливые случаи.

Обратите внимание, что shorttestPath [0, 0] = grid [0, 0] (вы начали в верхнем левом углу и пришли в верхний левый угол. Следовательно, стоимость - это только значение «сетки» в этой координате).

shortestPath[0][0] = grid[0][0];

Теперь мы можем вычислить значение shorttestPath [0, 1]. Поскольку мы находимся в верхней части сетки, единственный способ попасть в ячейку [0, 1] - из ячейки [0, 0]. Следовательно, shortPath [0, 1] = ShortPath [0, 0] + grid [0, 1] = 5 + 3 = 8. Затем мы можем перейти к следующей ячейке, [0, 2]. Применяется та же идея, т.е. / em> сетки:

//'m': The number of columns in the grid
for(int k=2; k<=m; k++){
   shortestPath[1][k] = shortestPath[1][k-1] + grid[1][k];
}

И мы можем использовать ту же идею для заполнения первого столбца сетки:

//'n': The number of rows in the grid
for(int k=2; k<=n; k++){
   shortestPath[k][1] = shortestPath[k-1][1] + grid[k][1];
}

После того, как мы сделали все вышеизложенное, у нас есть счастливые случаи (то есть базовый случай индукции):

Вот картина того, что у нас есть на данный момент:

Теперь мы можем перейти к шагу 3, т.е. применить общую формулу, пока не получим ответ:

for(int i=2; i<=n; i++){
   for(int j=2; j<=m; j++){
      shortestPath[i][j] = min(shortestPath[i-1][j],
                               shortestPath[i][j-1]) + grid[i][j];
   }
}

В конце концов, ваш ответ будет в формате shortPath [n] [m], где ’n’ - количество строк в вашей сетке, а ‘m’ - количество столбцов.

Обратите внимание, что сложность этого алгоритма всего O (n * m). Алгоритмы динамического программирования обычно приводят к полиномиальным временным сложностям.

В следующей статье мы решим более интересную задачу. Будьте на связи!

Источники:

  1. Проблемы оптимизации от MIT OpenCourseware: https://www.youtube.com/watch?v=uK5yvoXnkSk (24:11)
  2. Подсчет путей на сетке от Art of Problem Solving: https://www.youtube.com/watch?v=M8BYckxI8_U