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

Определение:

Динамическое программирование по профилю (англ. dynamic programming with profile) — способ оптимизации перебора количества вариантов с помощью динамического программирования, когда одно из измерений небольшое.

Определение:

Профиль (англ. profile) — один из столбцов (строк), удовлетворяющий условию задачи. Обычно используется в качестве состояния динамики.

Общие принципы

Обычно дана таблица и надо посчитать количество замощений этой таблицы некоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию. Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо заполнить и для него нам надо $k$ предыдущих линий. Тогда можно перебрать все замощения длиной $k\times n$. В итоге нужно заполнить данную таблицу этими замощениями. Получается, что если перебирать все варианты нам понадобится $O(a^{nm})$ времени, а если перебирать только состояния и переходить по ним нам потребуется $O(a^{kn}m)$ времени (где $a$ — количество способов замощения одной клетки).

Задача о замощении домино

Условие

Найти количество способов замостить таблицу $n\times m$ с помощью доминошек размерами $1\times 2,2\times 1$.

Решение

Переходы (1-правильный переход, 2,3-неправильные)

Для удобства можно хранить профили в виде двоичных масок. В качестве состояния динамики будем использовать профили размерами $n$. В этом профиле $1$ будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе $0$. Таких профилей будет $2^n$. Теперь проверим из какого профиля в какой можно перейти.

Из профиля $i$ в профиль $j$ можно перейти если выполняются условия:

• Можно положить горизонтальные домино. То есть там где в $j$ профиле стоит $1$, в $i$ профиле должен стоять $0$.

• Можно доложить в оставшиеся клетки вертикальные домино. То есть оставшиеся $0$ в $i$ профиле должны образовывать четные подстроки.

Пусть $d[i][j] = 1$ если из профиля $i$ можно перейти в $j$-ый, иначе $0$.

Пусть так же $a[k][i]$ — количество способов замощения первых $k-1$ столбцов и заканчивавшийся на $i$-ом профиле. Тогда $a[k][i]=\displaystyle \sum_{j=0}^{2^n -1} a[k-1][j]\cdot d[j][i]$

Ответом будет $\sum a[m][i]$, где $i$ — профиль, который может быть последним (т.е. все группы из $0$ имеют четные размеры).

Реализация

// n, m — размер таблицы  
  for $\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
    for $\mathtt{j} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
        if можно перейти из $\mathtt{i}$ в $\mathtt{j}$ профиль 
           $\mathtt{d}[\mathtt{i}][\mathtt{j}] = \mathtt{1}$
	else 
	    $\mathtt{d}[\mathtt{i}][\mathtt{j}] = \mathtt{0}$
$\mathtt{a}[\mathtt{0}][\mathtt{0}] = \mathtt{1}$ // Так как мы можем начать только с профиля где все клетки 0  
for $k = \mathtt{1}..\mathtt{m} - \mathtt{1}$
    for $\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
        for $\mathtt{j} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
	    $\mathtt{a}[\mathtt{k}][\mathtt{i}] = \mathtt{a}[\mathtt{k}][\mathtt{i}] + \mathtt{a}[\mathtt{k} - \mathtt{1}][\mathtt{j}]  \cdot  \mathtt{d}[\mathtt{j}][\mathtt{i}]$
$\mathtt{ans} = \mathtt{0}$
for $\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt \ \mathtt{n}) - \mathtt{1}$
    if можно закончить $\mathtt{i}$ профилем
        $\mathtt{ans} = \mathtt{ans} + \mathtt{a}[\mathtt{m} - \mathtt{1}][\mathtt{i}]$
return $\mathtt{ans}$

Оценка сложности: подсчет $d - 2^{2n}$ , и подсчет $a - 2^{2n}m$ в итоге $O(2^{2n}m)$.

Оценка памяти: $O(2^{2n} + 2^{2n}m)$, так же можно заметить что в массиве $a$ для $k$ состояния нам нужно только $k - 1$ состояние, при такой реализации нужно будет $O(2^{2n})$. Еще можно не считать массив $d$, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется $O(2^{n + 1})$ памяти, но нам потребуется больше времени $2^{2n}mf(i,j)$, где $f(i,j)$ время проверки возможности перехода из $i$ в $j$ равно $n$ и тогда время получается $O(2^{2n}mn)$.

Задача о симпатичных узорах

Условие

Дана таблица $n\times m$, каждая клетка которой может быть окрашена в один из двух цветов: белый или черный. Симпатичным узором называется такая раскраска, при которой не существует квадрата $2\times 2$, в котором все клетки одного цвета. Требуется найти количество симпатичных узоров для соответствующей таблицы.

Решение

Для удобства можно хранить профиля в виде двоичных масок. В качестве состояния динамики будем использовать профили размера $n$. В этом профиле $1$ будет означать что клетка закрашена в черный цвет, и $0$ если в белый. Из профиля $i$ в $j$-ый можно перейти если выполнено условие:

• если поставить $i$ и $j$ профиль рядом, то не должно быть квадратов $2\times 2$ одного цвета

Пусть $d[i][j] = 1$ если из профиля $i$ можно перейти в $j$-ый, иначе $0$.

Пусть так же $a[k][i]$ — количество способов раскрашивания первые $k-1$ столбцов и заканчивавшийся на $i$-ом профиле. Тогда $a[k][i]=\displaystyle \sum_{j=0}^{2^n -1} a[k-1][j]\cdot d[j][i]$

Ответом будет $\displaystyle \sum_{i=0}^{2^n -1} a[m][i]$

Реализация

// n, m — размер таблицы   
for $\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
    for $\mathtt{j} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
        if можно перейти из $\mathtt{i}$ в $\mathtt{j}$ профиль 
            $\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{1}$
	else
	    $\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{0}$
for $\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
    $\mathtt{a}[0][\mathtt{i}]\ = \mathtt{1}$ // Так как мы можем начать c любого профиля
for $\mathtt{k} = \mathtt{1}.. \mathtt{m} - \mathtt{1}$
    for  $\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
        for $\mathtt{j} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
	     $\mathtt{a}[\mathtt{k}][\mathtt{i}] = \mathtt{a}[\mathtt{k}][\mathtt{i}] + \mathtt{a}[\mathtt{k} - 1][\mathtt{j}] \cdot \mathtt{d}[\mathtt{j}][\mathtt{i}]$  
$\mathtt{ans} = \mathtt{0}$
for $\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt  \ \mathtt{n}) - \mathtt{1}$
    $\mathtt{ans} = \mathtt{ans} + \mathtt{a}[\mathtt{m} - \mathtt{1}][\mathtt{i}]$ // Так как мы можем закончить любым профилем 
return $\mathtt{ans}$

Оценка сложности: подсчет $d - 2^{2n}$ , и подсчет $a - 2^{2n}m$ в итоге $O(2^{2n}m)$.

Оценка памяти: $O(2^{2n}+2^{2n}m)$, так же можно заметить что в массиве $a$ для $k$ состояния нам нужно только $k-1$ состояние, при такой реализации нужно будет $O(2^{2n})$. Еще можно не считать массив $d$, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется $O(2^{n + 1})$ памяти, но нам потребуется больше времени $2^{2n}mf(i,j)$, где $f(i,j)$ время проверки возможности перехода из $i$ в $j$ равно $n$ и тогда время получается $O(2^{2n}mn)$.

Динамика по изломанному профилю

Определение:

Изломанный профиль (англ. broken profile) — обобщение прямого профиля на случай, когда обработанным является не целое число столбцов, а некоторое количество столбцов и несколько первых клеток следующего столбца.

Это очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому).

Пример

Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через $i$-ю вертикаль сверху вниз, она переходит на предыдущую вертикаль и спускается до низу. Теперь профиль — это не только маска, но ещё и место излома.

Профилем будет пара $(p, i)$, в $p$ будет информация о $n + 1$ маленьком квадратике слева от базовой линии, имеющем с ней общие точки; $i$ обозначает номер горизонтали, на которой произошел излом. Квадратики профиля будут нумероваться сверху вниз, так что угловой будет иметь номер $i + 1$. Горизонтали будем нумеровать с нуля, так что $i$ пробегает значения от $0$ до $n - 1$.

Пусть $d[pr_1][pr_2] = 1$ если из профиля $pr_1$ = $(p_1, i_1)$ можно перейти в $pr_2 = (p_2, i_2)$, иначе $0$.

• Eсли $i \lt n - 1$, то $i_1 + 1 = i_2$, иначе $i_2 = 0$;

• Mожно так положить доминошку, накрывающую квадратик с номером $i + 1$, что после этого в $p_2$ будет храниться в точности информация о соответствующих квадратиках.

Проще говоря, доминошку можно класть только двумя способами — как показано на рисунках (на квадратик с номером $i + 1$ можно положить не более одной вертикальной и горизонтальной доминошки). То, что потом получается после сдвига вниз излома, и будет новым профилем. Заметим, что если клетка $i + 1$ занята, то доминошку уже не надо класть, и $(p, i)$ логично отождествить с $(p, i + 1)$. Условно пишется — "$i + 1$", однако, нужно всегда иметь в виду возможность $i = n - 1$.

Легко заметить, что количество профилей увеличилось в $2n$ раз (добавилось число от $1$ до $n$ и еще один бит). Но зато количество переходов резко сократилось с $2^n$ до $2$.

//Для профиля (p, i) выводятся все переходы из него (нумерация горизонталей начинается с нуля и i = 0..n - 1)
// Функция bit(x,i), возвращающая единицу или ноль или i-й бит в двоичной записи числа x
print_all_links($\mathtt{p}$, $\mathtt{i}$):
    if $\mathtt{bit}(\mathtt{p, \mathtt{i} + \mathtt{1}}) == \mathtt{0}$
        if $\mathtt{i} == \mathtt{n} - \mathtt{1}$
            println$((\mathtt{p} - (\mathtt{2} \lt \lt  \ \mathtt{i})) \lt \lt  \ \mathtt{1}$, " ", $\mathtt{0})$
        else
            println$(\mathtt{p} - (\mathtt{2} \lt \lt  \ \mathtt{i})$, " ", $\mathtt{i} + \mathtt{1})$
    else 
        if $\mathtt{bit}(\mathtt{p}, \mathtt{i}) == \mathtt{0}$
            if $\mathtt{i} == \mathtt{n} - \mathtt{1}$
               println$((\mathtt{p} \lt \lt  \ \mathtt{1})$, " ", $\mathtt{0})$
            else   
               println$(\mathtt{p} + (\mathtt{1} \lt \lt  \ \mathtt{n})$, " ", $(\mathtt{i} + \mathtt{1}) % \mathtt{n})$
    if $\mathtt{i} \lt  \mathtt{n} - \mathtt{1}$ && $\mathtt{bit}(\mathtt{p, \mathtt{i} + \mathtt{2}}) == \mathtt{0}$
            println$(\mathtt{p} + (\mathtt{4} \lt \lt  \ \mathtt{i})$, " ", $\mathtt{i} + \mathtt{1})$

Возможные переходы

При такой реализации существует немало профилей только с одним переходом (например, у которых $(i + 1)$-й бит равен единице). Отождествим все профили с один переходом с теми, кто их них получается. Это будет выглядеть так: пусть $pr_2$ (и только он) получается из $pr_1$, который, в свою очередь, получается из $pr_0$. Тогда имеются такие соотношения: $d[pr_0, pr_1] = 1$, $d[pr_1, pr_2] = 1$. Отождествить $pr_1$ и $pr_2$ — это, по сути, заменить эти два соотношение на одно, то есть теперь $d[pr_0, pr_1] = 0$ и $d[pr_1, pr_2] = 0$, но $d[pr_0, pr_2] = 1$, и так далее.

Таким образом, возможно сокращение профилей не менее чем вдвое. Хотя можно совершить дальнейшие оптимизации.

В итоге асимптотика составляет $O(2^nnm)$. Это доказывает, что данный метод значительно лучше простого способа подсчёта динамики.

См. также

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

Источники информации

• Динамическое программирование по профилю
• Динамическое программирование по изломанному профилю