Динамическое программирование по профилю — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Общие принципы)
(Решение)
Строка 17: Строка 17:
  
 
Для удобства можно хранить профили в виде двоичных масок.
 
Для удобства можно хранить профили в виде двоичных масок.
В качестве состояния динамики будем использовать профили размерами <tex>n</tex>. В этом профиле 1 будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе 0. Таких профилей будет <tex>2^n</tex>.
+
В качестве состояния динамики будем использовать профили размерами <tex>n</tex>. В этом профиле <tex>1</tex> будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе <tex>0</tex>. Таких профилей будет <tex>2^n</tex>.
 
Теперь проверим из какого профиля в какой можно перейти.
 
Теперь проверим из какого профиля в какой можно перейти.
  
Строка 24: Строка 24:
 
Из профиля <tex>i</tex> в профиль <tex>j</tex> можно перейти если выполняются условия:
 
Из профиля <tex>i</tex> в профиль <tex>j</tex> можно перейти если выполняются условия:
  
* Можно положить горизонтальные домино. То есть там где в <tex>j</tex> профиле стоит 1, в <tex>i</tex> профиле должен стоять 0
+
* Можно положить горизонтальные домино. То есть там где в <tex>j</tex> профиле стоит <tex>1</tex>, в <tex>i</tex> профиле должен стоять <tex>0</tex>.
  
* Можно доложить в оставшиеся клетки вертикальные домино. То есть оставшиеся 0 в <tex>i</tex> профиле должны образовывать четные подстроки.
+
* Можно доложить в оставшиеся клетки вертикальные домино. То есть оставшиеся <tex>0</tex> в <tex>i</tex> профиле должны образовывать четные подстроки.
  
Пусть <tex>d[i][j] = 1</tex> если из профиля <tex>i</tex> можно перейти в <tex>j</tex>-ый, иначе 0.
+
Пусть <tex>d[i][j] = 1</tex> если из профиля <tex>i</tex> можно перейти в <tex>j</tex>-ый, иначе <tex>0</tex>.
  
Пусть так же <tex>a[k][i]</tex> - количество способов замощения первых <tex>k-1</tex> столбцов и заканчивавшийся на <tex>i</tex>-ом профиле.
+
Пусть так же <tex>a[k][i]</tex> {{---}} количество способов замощения первых <tex>k-1</tex> столбцов и заканчивавшийся на <tex>i</tex>-ом профиле.
 
Тогда <tex>a[k][i]=\displaystyle \sum_{j=0}^{2^n -1} a[k-1][j]\cdot d[j][i]</tex>
 
Тогда <tex>a[k][i]=\displaystyle \sum_{j=0}^{2^n -1} a[k-1][j]\cdot d[j][i]</tex>
  
Ответом будет <tex> \sum a[m][i]</tex>, где <tex>i</tex> : профиль, который может быть последним (т.е. все группы из 0 имеют четные размеры)
+
Ответом будет <tex> \sum a[m][i]</tex>, где <tex>i</tex> {{---}} профиль, который может быть последним (т.е. все группы из <tex>0</tex> имеют четные размеры)
  
 
==='''Реализация'''===
 
==='''Реализация'''===

Версия 03:54, 9 января 2015

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


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


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

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

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

Условие

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

Решение

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

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

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

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

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

Пусть так же [math]a[k][i][/math] — количество способов замощения первых [math]k-1[/math] столбцов и заканчивавшийся на [math]i[/math]-ом профиле. Тогда [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], где [math]i[/math] — профиль, который может быть последним (т.е. все группы из [math]0[/math] имеют четные размеры)

Реализация

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

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

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

Условие

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

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

Решение

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

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

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

Пусть так же [math]a[k][i][/math] - количество способов раскрашивания первые [math]k-1[/math] столбцов и заканчивавшийся на [math]i[/math]-ом профиле. Тогда [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 [math]i = \mathtt{0}..(\mathtt{1}\lt \lt n) - \mathtt{1}[/math]
    for [math]j = \mathtt{0}..(\mathtt{1}\lt \lt n) - \mathtt{1}[/math]
        if можно перейти из [math]i[/math] в [math]j[/math] профиль 
            [math]\mathtt{d}[i][j]\ =\ \mathtt{1}[/math]
	else
	    [math]\mathtt{d}[i][j]\ =\ \mathtt{0}[/math]
for [math]i = \mathtt{0}..(\mathtt{1}\lt \lt n) - \mathtt{1}[/math]
    [math]\mathtt{a}[i][0]\ = \mathtt{1}[/math] // Так как мы можем начать c любого профиля
for [math]k = \mathtt{1}..m - \mathtt{1} [/math]
    for  [math]i = \mathtt{0}..(\mathtt{1}\lt \lt n) - \mathtt{1}[/math]
        for [math]j = \mathtt{0}..(\mathtt{1}\lt \lt n) - \mathtt{1}[/math]
	     [math]\mathtt{a}[k][i] = \mathtt{a}[k][i] + \mathtt{a}[k - 1][j] \cdot \mathtt{d}[j][i][/math]  
[math]ans = \mathtt{0}[/math]
for [math]i = \mathtt{0}..(\mathtt{1}\lt \lt n) - \mathtt{1}[/math]
    [math]ans = ans + a[m - \mathtt{1}][i][/math] // Так как мы можем закончить любым профилем 
return [math]ans[/math]

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

См. также

Ссылки