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

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

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

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

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

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

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

Из профиля 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].

См. также

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

Ссылки

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