Изменения

|definition='''ПрофильДинамическое программирование по профилю''' - один из столбов(строкангл. ''dynamic programming with profile''){{---}} способ оптимизации перебора количества вариантов с помощью [[Динамическое программирование|динамического программирования]], удовлетворяющий условию задачи. Обычно используется в качестве состояния динамикикогда одно из измерений небольшое.

'''Решение[[Файл:'''Домино.png|270px|thumb|right|Переходы (1-правильный переход, 2,3-неправильные)]] Для удобства можно хранить профили в виде двоичных масок.В качестве состояния динамики будем использовать профиля профили размерами <tex>n</tex>. В этом профиле <tex>1 </tex> будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе <tex>0</tex>. Таких профилей будет <tex>2^n</tex>.

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

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

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

Пусть <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> \sum a[m][i]</tex>, где <tex>i : </tex> {{---}} профиль, который может быть последним (т.е. все группы из <tex>0 </tex> имеют четные размеры). ==='''Реализация'''=== <font color=green>// n, m {{---}} размер таблицы </font> '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> '''if''' можно перейти из <tex>\mathtt{i}</tex> в <tex>\mathtt{j}</tex> профиль <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}] = \mathtt{1}</tex> '''else''' <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}] = \mathtt{0}</tex> <tex>\mathtt{a}[\mathtt{0}][\mathtt{0}] = \mathtt{1}</tex> <font color=green>// Так как мы можем начать только с профиля где все клетки 0 </font> '''for''' <tex>k = \mathtt{1}..\mathtt{m} - \mathtt{1} </tex> '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> <tex>\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}]</tex> <tex>\mathtt{ans} = \mathtt{0}</tex> '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt \ \mathtt{n}) - \mathtt{1}</tex> '''if''' можно закончить <tex>\mathtt{i}</tex> профилем <tex>\mathtt{ans} = \mathtt{ans} + \mathtt{a}[\mathtt{m} - \mathtt{1}][\mathtt{i}]</tex> '''return''' <tex>\mathtt{ans}</tex> ''' Оценка сложности: '''подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n}m</tex> в итоге <tex>O(2^{2n}m)</tex>. ''' Оценка памяти: '''<tex>O(2^{2n} + 2^{2n}m)</tex>, так же можно заметить что в массиве <tex>a</tex> для <tex>k</tex> состояния нам нужно только <tex>k - 1</tex> состояние, при такой реализации нужно будет <tex>O(2^{2n})</tex>. Еще можно не считать массив <tex>d</tex>, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется <tex>O(2^{n + 1})</tex> памяти, но нам потребуется больше времени <tex>2^{2n}mf(i,j)</tex>, где <tex>f(i,j)</tex> время проверки возможности перехода из <tex>i</tex> в <tex>j</tex> равно <tex>n</tex> и тогда время получается <tex>O(2^{2n}mn)</tex>. == '''Задача о симпатичных узорах''' ====='''Условие'''===Дана таблица <tex>n\times m</tex>, каждая клетка которой может быть окрашена в один из двухцветов: белый или черный. Симпатичным узором называется такая раскраска, прикоторой не существует квадрата <tex>2\times 2</tex>, в котором все клетки одного цвета. Требуется найти количество симпатичных узоров для соответствующей таблицы. [[Файл:Симпатичне узоры.png|240px|thumb|right|]]

==='''Решение'''===Для удобства можно хранить профиля в виде двоичных масок .В качестве состояния динамики будем использовать профили размера <tex>n</tex>. В этом профиле <tex>1</tex> будет означать что клетка закрашена в черный цвет, и <tex>0</tex> если в белый.Из профиля <tex>i</tex> в <tex>j</tex>-ый можно перейти если выполнено условие:* если поставить <tex>i</tex> и <tex>j</tex> профиль рядом, то не должно быть квадратов <tex>2\times 2</tex> одного цвета

//n, m размеры таблицы for i = 0..(1Пусть так же <<n)-1 for j = 0..(1<<n)-1 if можно перейти из i в j профиль dtex>a[i][jk] = 1; else d[i][j] = 0; a[0][0] = 1; <//Так как мы можем начать только с профиля где все клетки 0 for tex> {{---}} количество способов раскрашивания первые <tex>k = 1..m-1 for </tex> столбцов и заканчивавшийся на <tex>i = 0..(1<<n)/tex>-1ом профиле. for j = 0..(1<Тогда <n)-1 tex>a[k][i] += \displaystyle \sum_{j=0}^{2^n -1} a[k-1][j] * \cdot d[j][i]; ans = 0; for i = 0..(1<<n)-1 if можно закончить i профилем ans += a[m-1][i]; return ans;/tex>

''' Оценка сложности : '''подсчет Ответом будет <tex>d - 2^\displaystyle \sum_{2ni=0}</tex> , и подсчет <tex>a - 2^{2n}\times m</tex> в итоге <tex>O(2^{2nn -1}\times a[m)][i]</tex>

===''' Оценка памяти : Реализация'''=== <font color=green>// n, m {{---}} размер таблицы </font> '''for''' <tex>O\mathtt{i} = \mathtt{0}..(2^\mathtt{1} << \ \mathtt{n}) - \mathtt{2n1}+2^</tex> '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{2n1}<< \ \times mmathtt{n})- \mathtt{1}</tex>, так же '''if''' можно заметить что перейти из <tex>\mathtt{i}</tex> в массиве <tex>\mathtt{j}</tex> профиль <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{1}</tex> '''else''' <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{0}</tex> '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> <tex>\mathtt{a}[0][\mathtt{i}]\ = \mathtt{1}</tex> для k состояния нам нужно только <font color=green >// Так как мы можем начать c любого профиля</font> '''for''' <tex>\mathtt{k} = \mathtt{1}.. \mathtt{m} -\mathtt{1 состояние, при такой реализации нужно будет } </tex> '''for''' <tex>O\mathtt{i} = \mathtt{0}..(2^\mathtt{1} << \ \mathtt{2nn})- \mathtt{1}</tex>. Еще можно не считать массив d, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется '''for''' <tex>O\mathtt{j} = \mathtt{0}..(2\times 2^mathtt{1} << \ \mathtt{n})- \mathtt{1}</tex> памяти, но нам потребуется больше времени <tex>2^\mathtt{a}[\mathtt{k}][\mathtt{i}] = \mathtt{2na}[\times mmathtt{k}][\times f(mathtt{i,}] + \mathtt{a}[\mathtt{k} - 1][\mathtt{j}] \cdot \mathtt{d}[\mathtt{j)}][\mathtt{i}]</tex> <tex>\mathtt{ans} = \mathtt{0}</tex>, где '''for''' <tex>f\mathtt{i} = \mathtt{0}..(i,j\mathtt{1} << \ \mathtt{n})- \mathtt{1}</tex> время проверки возможности перехода из i в j, обычно проверка равна n и тогда время получается <tex>O(2^\mathtt{ans} = \mathtt{ans} + \mathtt{2na}[\times mathtt{m} - \mathtt{1}][\mathtt{i}]</tex> <font color=green>// Так как мы можем закончить любым профилем </font> '''return''' <tex>\times n)mathtt{ans}</tex>.

== '''Задача о симпатичных узорах''' Динамика по изломанному профилю ==

Дана таблица <tex>n\times m</tex>, каждая клетка которой может быть окрашена в один из двух{{Определениецветов: белый или черный|definition='''Изломанный профиль''' (англ. Симпатичным узором называется такая раскраска''broken profile'') {{---}} обобщение прямого профиля на случай, прикоторой когда обработанным является не существует квадрата <tex>2\times 2</tex>целое число столбцов, в котором все клетки одного цвета. Требуется найти а некоторое количество симпатичных узоров для соответствующей таблицыстолбцов и несколько первых клеток следующего столбца.}}

[[Файл:Симпатичне узорыЭто очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому).png|240px|thumb|right|'''Примеры узоров''']]

'''Решение:'''=== Пример ===В Еще раз используем в качестве состояния динамики будем использовать профиль размеров nпримера задачу о замощении. В этом профиле 1 Базовая линия теперь будет означать что клетка закрашена в черный цветломаной: при прохождении через <tex>i</tex>-ю вертикаль сверху вниз, она переходит на предыдущую вертикаль и спускается до низу. Теперь профиль — это не только маска, но ещё и 0 если в белыйместо излома.[[Файл:img34.gif|300px|thumb|right|]]Из профиля Профилем будет пара <tex>(p, i )</tex>, в j-ый можно перейти если выполнено условие:* если поставить <tex>p</tex> будет информация о <tex>n + 1</tex> маленьком квадратике слева от базовой линии, имеющем с ней общие точки; <tex>i</tex> обозначает номер горизонтали, на которой произошел излом. Квадратики профиля будут нумероваться сверху вниз, так что угловой будет иметь номер <tex>i и j профиль рядом+ 1</tex>. Горизонтали будем нумеровать с нуля, то не должно быть квадратов так что <tex>i</tex> пробегает значения от <tex>0</tex> до <tex>2\times 2n - 1</tex> одного цвета.

Пусть <tex>d[ipr_1][jpr_2] = 1</tex> если из профиля i <tex>pr_1</tex> = <tex>(p_1, i_1)</tex> можно перейти в j-ый<tex>pr_2 = (p_2, i_2)</tex>, иначе <tex>0</tex>.

Пусть так же * Eсли <tex>a[k][i]< n - 1</tex> - количество способов раскрашивания первые k-, то <tex>i_1 + 1 столбцов и заканчивавшийся на i профиле.Тогда = i_2</tex>, иначе <tex>a[k][i]=\displaystyle \sum_{ji_2 =0}^{2^n -1} a[k-1][j]\cdot d[j][i]</tex>;

Ответом * Mожно так положить доминошку, накрывающую квадратик с номером <tex>i + 1</tex>, что после этого в <tex>p_2</tex> будет храниться в точности информация о соответствующих квадратиках.Проще говоря, доминошку можно класть только двумя способами {{---}} как показано на рисунках (на квадратик с номером <tex>i + 1</tex> можно положить не более одной вертикальной и горизонтальной доминошки). То, что потом получается после сдвига вниз излома, и будет новым профилем. Заметим, что если клетка <tex>i + 1</tex> \displaystyle \sum_занята, то доминошку уже не надо класть, и <tex>(p, i)</tex> логично отождествить с <tex>(p, i + 1)</tex>. Условно пишется {j{---}} "<tex>i + 1</tex>", однако, нужно всегда иметь в виду возможность <tex>i =0}^{2^n -1} a[m][i]</tex>.

Для удобства можно хранить профиля Легко заметить, что количество профилей увеличилось в виде двоичных масок <tex>2n</tex> раз (добавилось число от <tex>1</tex> до <tex>n</tex> и еще один бит). Но зато количество переходов резко сократилось с <tex>2^n</tex> до <tex>2</tex>.

'''Реализация:''' <font color=green>//nДля профиля (p, m размеры таблицы for i) выводятся все переходы из него (нумерация горизонталей начинается с нуля и i = 0..(n - 1)</font> <nfont color=green>// Функция bit(x,i), возвращающая единицу или ноль или i-1й бит в двоичной записи числа x</font> for j = 0.. '''print_all_links'''(1<tex>\mathtt{p}</tex>, <tex>\mathtt{i}<n/tex>)-1: '''if можно перейти из ''' <tex>\mathtt{bit}(\mathtt{p, \mathtt{i в j профиль } + \mathtt{1}}) == \mathtt{0}</tex> d[ '''if''' <tex>\mathtt{i][j] } == \mathtt{n} - \mathtt{1; }</tex> else d[ '''println'''<tex>((\mathtt{p} - (\mathtt{2} << \ \mathtt{i][j] = })) << \ \mathtt{1}</tex>, " ", <tex>\mathtt{0;})</tex> '''else''' for i = 0.. '''println'''<tex>(\mathtt{p} - (1\mathtt{2} <<n\ \mathtt{i})-</tex>, " ", <tex>\mathtt{i} + \mathtt{1})</tex> a[ '''else''' '''if''' <tex>\mathtt{bit}(\mathtt{p}, \mathtt{i][}) == \mathtt{0] = 1; }<//Так как мы можем начать c любого профиляtex> for k '''if''' <tex>\mathtt{i} == 1..m\mathtt{n} -\mathtt{1} </tex> for i = 0.. '''println'''<tex>((\mathtt{p} << \ \mathtt{1})</tex>, " ", <ntex>\mathtt{0})-1</tex> '''else''' for j = 0.. '''println'''<tex>(\mathtt{p} + (\mathtt{1} <<\ \mathtt{n})-</tex>, " ", <tex>(\mathtt{i} + \mathtt{1}) % \mathtt{n})</tex> a[k][ '''if''' <tex>\mathtt{i] += a[k} < \mathtt{n} -\mathtt{1][j] * d[j][}</tex> && <tex>\mathtt{bit}(\mathtt{p, \mathtt{i]; ans } + \mathtt{2}}) == \mathtt{0;}</tex> for i = 0.. '''println'''<tex>(\mathtt{p} + (1\mathtt{4} <<n\ \mathtt{i})-</tex>, " ", <tex>\mathtt{i} + \mathtt{1})</tex> ans += a[m-1[Файл:ok.jpg|640px|thumb|left|Возможные переходы][i]//Так как мы можем закончить любым профилем return ans;

''' Оценка сложности При такой реализации существует немало профилей только с одним переходом (например, у которых <tex>(i + 1)</tex>-й бит равен единице).Отождествим все профили с один переходом с теми, кто их них получается. Это будет выглядеть так: пусть <tex>pr_2</tex> (и только он) получается из <tex>pr_1</tex>, который, в свою очередь, получается из <tex>pr_0</tex>. Тогда имеются такие соотношения: '''подсчет <tex>d - 2^{2n}[pr_0, pr_1] = 1</tex> , <tex>d[pr_1, pr_2] = 1</tex>. Отождествить <tex>pr_1</tex> и подсчет <tex>a pr_2</tex> {{- 2^{2n--}}\times mэто, по сути, заменить эти два соотношение на одно, то есть теперь <tex>d[pr_0, pr_1] = 0</tex> в итоге и <tex>d[pr_1, pr_2] = 0</tex>, но <tex>O(2^{2n}\times m)d[pr_0, pr_2] = 1</tex>, и так далее.

''' Оценка памяти : '''<tex>O(2^{2n}+2^{2n}\times m)</tex>Таким образом, так же возможно сокращение профилей не менее чем вдвое. Хотя можно заметить что в массиве <tex>a</tex> для k состояния нам нужно только k-1 состояние, при такой реализации нужно будет <tex>O(2^{2n})</tex>совершить дальнейшие оптимизации. Еще можно не считать массив d, а просто каждый раз перепроверять можем ли мы перейти в это состояние в В итоге потребуется асимптотика составляет <tex>O(2\times 2^nnnm)</tex> памяти. Это доказывает, но нам потребуется больше времени <tex>2^{2n}\times m\times f(i,j)</tex>, где <tex>f(i,j)</tex> время проверки возможности перехода из i в j, обычно проверка равна n и тогда время получается <tex>O(2^{2n}\times m\times n)</tex>что данный метод значительно лучше простого способа подсчёта динамики.

*[[Динамическое_программированиеДинамическое программирование]] == Ссылки Источники информации ==