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

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


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


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

Обычно дана таблица и надо посчитать количество замощений этой таблицы некоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию. Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо заполнить и для него нам надо k предыдущих линий. Тогда можно перебрать все замощения длиной k×n. В итоге нужно заполнить данную таблицу этими замощениями. Получается, что если перебирать все варианты нам понадобиться O(anm) времени, а если перебирать только состояния и переходить по ним нам потребуется O(aknm) времени (где a — количество способов замощения одной клетки).

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

Условие

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

Решение

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

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

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

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

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

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

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

Реализация

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

Оценка сложности: подсчет d−22n , и подсчет a−22nm в итоге O(22nm).

Оценка памяти: O(22n+22nm), так же можно заметить что в массиве a для k состояния нам нужно только k−1 состояние, при такой реализации нужно будет O(22n). Еще можно не считать массив d, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется O(2n+1) памяти, но нам потребуется больше времени 22nmf(i,j), где f(i,j) время проверки возможности перехода из i в j равно n и тогда время получается O(22nmn).

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

Условие

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

Симпатичне узоры.png

Решение

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

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

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

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

Ответом будет 2n−1∑j=0a[m][i]

Реализация

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

Оценка сложности: подсчет d−22n , и подсчет a−22nm в итоге O(22nm)

Оценка памяти: O(22n+22nm), так же можно заметить что в массиве a для k состояния нам нужно только k−1 состояние, при такой реализации нужно будет O(22n). Еще можно не считать массив d, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется O(2n+1) памяти, но нам потребуется больше времени 22nmf(i,j), где f(i,j) время проверки возможности перехода из i в j равно n и тогда время получается O(22nmn).

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

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


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

Пример

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

Img34.gif

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

Пусть d[i][j]=1 если из профиля pr1 = (p1,i1) можно перейти в pr2=(p2,i2), иначе 0.

  • Eсли i<n−1, то i1+1=i2, иначе i2=0;
  • Mожно так положить доминошку, накрывающую квадратик с номером i+1, что после этого в p2 будет храниться в точности информация о соответствующих квадратиках.

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

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

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

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

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

В итоге получаем асимптотику O(2nnm). Она значительно лучше всего, что мы получали до сих пор, и это серьезный повод использовать изломанный профиль вместо обычного.

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование_по_профилю&oldid=44541»