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

Все задачи этого раздела будут иметь общее начало.

Дана прямоугольная доска размером n×m (n строк и m столбцов). В левом верхнем углу этой доски находится шахматный король, которого необходимо переместить в правый нижний угол.

 

Количество маршрутов

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

Будем считать, что положение короля задается парой чисел (a, b), где a задает номер строки, а b -- номер столбца. Строки нумеруются сверху вниз от 0 до n - 1, а столбцы -- слева направо от 0 до m - 1. Таким образом, первоначальное положение короля -- клетка (0, 0), а конечное -- клетка (n - 1, m - 1).

Пусть W(a, b) -- количество маршрутов, ведущих в клетку (a, b) из начальной клетки. Запишем рекуррентное соотношение. В клетку (a, b) можно прийти двумя способами: из клетки (a, b - 1), расположенной слева, и из клетки (a - 1, b), расположенной сверху от данной. Поэтому количество маршрутов, ведущих в клетку (a, b), равно сумме количеств маршрутов, ведущих в клетку слева и сверху от нее. Получили рекуррентное соотношение:

 

 

Это соотношение верно при a > 0 и b > 0. Зададим начальные значения: если a = 0, то клетка расположена на верхнем краю доски и прийти в нее можно единственным способом -- двигаясь только влево, поэтому W(0, b) = 1 для всех b. Аналогично, W(a, 0) = 1 для всех a.

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

 

int W[n][m];
int i,j;
for(j=0;j<m;++j)
    W[0][j]=1;        // Первая строка заполнена единицами
for(i=1;i<n;++i)      // i меняется от 1 до n-1
{                     // Заполняем строку с номером i
    W[i][0]=1;        // Элемент в первом столбце равен 1
    for(j=1;j<m;++j)  // Заполняем остальные элементы строки
        W[i][j]=W[i][j-1]+W[i-1][j];
}

В результате такого заполнения получим следующий массив (пример для n = 4, m = 5):

 

Легко видеть, что в результате получился треугольник Паскаля, записанный в немного другом виде, а именно, значение W[n-1][m-1] равно C_{n + m - 2}^{n - 1}. Ничего удивительного, ведь выписанное нами рекуррентное соотношение для количества маршрутов очень похоже на ранее выписанное соотношение для числа сочетаний.

Действительно, чтобы попасть из клетки (0, 0) в клетку (n - 1, m - 1) король должен сделать n + m - 2 хода, из которых n - 1 ход вниз и m - 1 ход вправо. Поэтому количество различных маршрутов, ведущих из начальной клетки в конечную равно количеству способов выбрать из общего числа n + m - 2 ходов n - 1 ход вниз, то есть C_{n + m - 2}^{n - 1} (и эта же величина равна C_{n + m - 2}^{m - 1} -- количеству выборок m - 1 хода вправо).

Поскольку для вычисления очередной строки массива W нам необходима только предыдущая строка, более того, для вычисления одного элемента очередной строки нам необходим только один элемент предыдущей строки, стоящий непосредственно над ним, то мы можем обойтись одномерным массивом вместо двумерного, если будем хранить только одну строку двумерного массива, а именно, ту строку, в которой находится рассматриваемый в данный момент элемент. Получим следующую программу:

 

int W[m];            // Массив элементов одной строки
int i,j;
for(j=0;j<m;++j)
  W[j]=1;            // Самая первая строка состоит из единиц
for(i=1;i<n;++i) 
{ // Теперь записываем в массив W содержимое i-й строки
    for(j=1;j<m;++j)      // Заполняем все элементы строки, 
      W[j]=W[j-1]+W[j];   // кроме первого
}

После окончания работы этого алгоритма элемент массива W[m-1] содержит искомое число путей.

Упражнение. Напишите программу, вычисляющую значение C_n^k при помощи динамического программирования и использующую одномерный массив из 1 + min(k, n - k) элементов.

Как решить задачу нахождения количества маршрутов, если король может передвигаться на одну клетку вниз, вправо или по диагонали вправо-вниз? Решение будет полностью аналогичным, только реккурентная формула для количества маршрутов изменится:

 

 

Полученный в результате заполнения по такой формуле массив W будет выглядеть следующим образом:

 

Упражнение. Решите эту задачу с использованием одномерного массива.

 

Количество маршрутов с препятствиями

Пусть некоторые клетки на доске являются «запретными»: король не может ходить на них. Карта запретных клеток задана при помощи массива Map[n][m]: нулевое значение элемента массива означает, что данная клетка запрещена, единичное значение означает, что в клетку можно ходить. Массив Map считывается программой после задания значений n и m. Король может ходить только вниз или вправо.

Для решения этой задачи придется изменить рекуррентное соотношение с учетом наличия запрещенных клеток. Для запрещенной клетки количество ведущих в нее маршрутов будем считать равным 0. Получим:

 

 

Также надо учесть то, что для клеток верхней строки и левого столбца эта формула некорректна, поскольку для них не существует соседней сверху или слева клетки.

Например, если n = 4, m = 5 и массив Map задан следующим образом:

 

то искомый массив W будет таким:

 

Упражнение. Решите эту задачу с использованием одномерного массива. Массив Map при этом считывается построчно и в памяти хранится только последний считанный элемент.

 

Путь максимальной стоимости

Пусть каждой клетке (a, b) доски приписано некоторое число P(a, b) -- стоимость данной клетки. Проходя через клетку, мы получаем сумму, равную ее стоимости. Требуется определить максимально возможную сумму, которую можно собрать по всему маршруту, если разрешается передвигаться только вниз или вправо.

Будем решать данную задачу методом динамического программирования. Пусть S(a, b) -- максимально возможная сумма, которую можно собрать на пути из начальной клетки в клетку (a, b). Поскольку в клетки верхней строки и левого столбца существует единственно возможный маршрут из начальной клетки, то для них величина S(a, b) определяется как сумма стоимостей всех клеток на пути из начальной вершины в данную (а именно, для начальной клетки S(0, 0) = P(0, 0), для клеток левого столбца S(a, 0) = S(a - 1, 0) + P(a, 0), для клеток верхней строки S(0, b) = S(0, b - 1) + P(0, b)). Мы задали граничные значения для функции S(a, b).

Теперь построим рекуррентное соотношение. Пусть (a, b) -- клетка, не лежащая в первой строке или первом столбце, то есть a > 0 и b > 0. Тогда прийти в данную клетку мы можем либо слева, из клетки (a, b - 1), и тогда мы сможем набрать максимальную сумму S(a, b - 1) + P(a, b), либо сверху, из клетки (a - 1, b), тогда мы сможем набрать сумму S(a - 1, b) + P(a, b). Естественно, из этих двух величин необходимо выбрать наибольшую:

 

 

Дальнейшая реализация алгоритма не вызывает затруднений:

 

int i,j;
S[0][0]=P[0][0];
for(j=1;j<m;++j)
    S[0][j]=S[0][j-1]+P[0][j];     // Заполняем первую строку
for(i=1;i<n;++i)           
{                               // Заполняем i-ю строку
  S[i][0]=S[i-1][0]+P[i][0];  // Заполняем 1-й столбец 
  for(j=1;j<m;++j)            // Заполняем остальные столбцы 
    if ( S[i-1][j] > S[i][j-1] ) // Выбираем максимум
      S[i][j]=P[i][j]+S[i-1][j]; // из S[i-1][j] и S[i][j-1]
    else                         // и записываем в S[i][j]
      S[i][j]=P[i][j]+S[i][j-1]; // с добавлением P[i][j]
}

Рассмотрим пример доски при n = 4, m = 5. Для удобства в одной таблице укажем значения обоих массивов: до дробной черты указана стоимость данной клетки, то есть значение P[i][j], после черты -- максимальная стоимость маршрута, ведущего в данную клетку, то есть величина S[i][j]:

 

Итак, максимальная стоимость пути из левого верхнего в правый нижний угол в этом примере равна 25.

Как и все предыдущие, данную задачу можно решить с использованием одномерного массива S.

Как изменить данный алгоритм, чтобы он находил не только максимально возможную стоимость пути, но и сам путь? Заведем массив Prev[n][m], в котором для каждой клетки будем хранить ее предшественника в маршруте максимальной стоимости, ведущем в данную клетку: если мы пришли в клетку слева, то запишем в соответствующий элемент массива Prev значение 1, а если сверху -- значение 2. Чтобы не путаться, обозначим данные значения константами:

const L=1; // Left
const U=2; // Upper

В начальную клетку запишем 0, поскольку у начальной клетки нет предшественника. В остальные клетки первой строки запишем L, а в клетки первого столбца запишем U. Остальные элементы массива Prev будем заполнять одновременно с массивом S:

 

        if ( S[i-1][j] > S[i][j-1] )
        {   // В клетку (i,j) приходим сверху из (i-1,j)
            S[i][j]=P[i][j]+S[i-1][j];
            Prev[i][j]=U;
        }
        else
        {   // В клетку (i,j) приходим слева из (i,j-1)
            S[i][j]=P[i][j]+S[i][j-1];
            Prev[i][j]=L;
        }

В результате, в приведенном выше примере мы получим следующий массив (значения массива Prev мы запишем в той же таблице после второй черты дроби, то есть в каждой клетке теперь записаны значения P[i][j] / S[i][j] / Prev[i][j]). Клетки, через которые проходит маршрут максимальной стоимости, выделены жирным шрифтом:

После заполнения всех массивов мы можем восстановить путь, пройдя по нему с конца при помощи цикла, начав с конечной клетки и передвигаясь влево или вверх в зависимости от значения соответствующего элемента массива Prev:

 

i=n-1;                   // (i,j) - координаты текущей точки
j=m-1;                   // начинаем с конечной клетки
while (Prev[i][j]!=0)    // проверка, не дошли ли до начальной
{
    if(Prev[i][j]==L)
        j=j-1;           // передвигаемся влево
    else
        i=i-1;           // передвигаемся вверх
}

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

Можно обойтись и без дополнительного массива предшественников Prev. Если имеется заполненный массив S, то предшественника каждой клетки мы можем легко определить, сравнив значения элемента массива S для ее левого и правого соседа и выбрав ту клетку, для которой это значение наибольшее.

i=n-1;
j=m-1;
while ( i>0 && j>0 )
{
    if ( S[i][j-1] > S[i-1][j] )
       j=j-1;
    else
       i=i-1;
}

Этот алгоритм заканчивается, когда мы выйдем на левый или верхний край доски (цикл while продолжается, пока i>0 и j>0, то есть клетка не лежит на верхнем или левом краю доски), после чего нужно будет двигаться по краю влево или вверх, пока не дойдем до начальной клетки. Это можно реализовать двумя циклами (при этом из этих двух циклов выполняться будет только один, поскольку после выполнения предыдущего фрагмента программы значение одной из переменных i или j будет равно 0):

 

while(i>0)
{   // Движение вверх, пока возможно
    i=i-1;
}
while(j>0)
{   // Движение влево, пока возможно
    j=j-1;
}

Таким образом, если мы хотим восстановить путь наибольшей стоимости, необходимо либо полностью сохранять в памяти значения всего массива S, либо хранить в памяти предшественника для каждой клетки. Для восстановления пути потребуется память порядка O(nm). Сложность алгоритма нахождения пути максимальной стоимости также имеет порядок O(nm) и, очевидно, не может быть уменьшена, поскольку для решения задачи необходимо использование каждого из nm элементов данного массива P.