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

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

Динамическое программирование по профилю [math]-[/math] способ оптимизации перебора количества вариантов с помощью динамического программирования, когда одно из измерений не большое.

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

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

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

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

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

Условие

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

Решение

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

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

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

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

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

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

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

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

Реализация

 // n, m размеры таблицы  
for i = 0..(1<<n) - 1
	for j = 0..(1<<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<<n) - 1
		 for j = 0..(1<<n) - 1
			 a[k][i] += a[k-1][j] * d[j][i];
ans = 0;
for i = 0..(1<<n) - 1
	 if можно закончить i профилем
		 ans += a[m-1][i];
return ans;

Оценка сложности: подсчет [math]d - 2^{2n}[/math] , и подсчет [math]a - 2^{2n}\times m[/math] в итоге [math]O(2^{2n}\times m)[/math]

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

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

Условие

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

Решение

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

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

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

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

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

Реализация

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

Оценка сложности: подсчет [math]d - 2^{2n}[/math] , и подсчет [math]a - 2^{2n}\times m[/math] в итоге [math]O(2^{2n}\times m)[/math]

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

См. также

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

Ссылки

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