Динамическое программирование по профилю — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показана 41 промежуточная версия 10 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition='''Динамическое программирование по профилю''' (англ. ''dynamic programming with profile'') {{---}} способ оптимизации перебора количества вариантов с помощью [[Динамическое программирование|динамического программирования]], когда одно из измерений | + | |definition='''Динамическое программирование по профилю''' (англ. ''dynamic programming with profile'') {{---}} способ оптимизации перебора количества вариантов с помощью [[Динамическое программирование|динамического программирования]], когда одно из измерений небольшое. |
}} | }} | ||
{{Определение | {{Определение | ||
Строка 7: | Строка 7: | ||
== Общие принципы == | == Общие принципы == | ||
− | Обычно дана таблица и надо посчитать количество замощений этой таблицы некоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию. Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо заполнить и для него нам надо <tex>k</tex> предыдущих линий. Тогда можно перебрать все замощения длиной <tex>k\times n</tex>. В итоге нужно заполнить данную таблицу этими замощениями. Получается, что если перебирать все варианты нам | + | Обычно дана таблица и надо посчитать количество замощений этой таблицы некоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию. Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо заполнить и для него нам надо <tex>k</tex> предыдущих линий. Тогда можно перебрать все замощения длиной <tex>k\times n</tex>. В итоге нужно заполнить данную таблицу этими замощениями. Получается, что если перебирать все варианты нам понадобится <tex>O(a^{nm})</tex> времени, а если перебирать только состояния и переходить по ним нам потребуется <tex>O(a^{kn}m)</tex> времени (где <tex>a</tex> {{---}} количество способов замощения одной клетки). |
== '''Задача о замощении домино''' == | == '''Задача о замощении домино''' == | ||
Строка 15: | Строка 15: | ||
==='''Решение'''=== | ==='''Решение'''=== | ||
+ | [[Файл:Домино.png|270px|thumb|right|Переходы (1-правильный переход, 2,3-неправильные)]] | ||
Для удобства можно хранить профили в виде двоичных масок. | Для удобства можно хранить профили в виде двоичных масок. | ||
В качестве состояния динамики будем использовать профили размерами <tex>n</tex>. В этом профиле <tex>1</tex> будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе <tex>0</tex>. Таких профилей будет <tex>2^n</tex>. | В качестве состояния динамики будем использовать профили размерами <tex>n</tex>. В этом профиле <tex>1</tex> будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе <tex>0</tex>. Таких профилей будет <tex>2^n</tex>. | ||
Теперь проверим из какого профиля в какой можно перейти. | Теперь проверим из какого профиля в какой можно перейти. | ||
− | |||
− | |||
Из профиля <tex>i</tex> в профиль <tex>j</tex> можно перейти если выполняются условия: | Из профиля <tex>i</tex> в профиль <tex>j</tex> можно перейти если выполняются условия: | ||
Строка 33: | Строка 32: | ||
Тогда <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> {{---}} профиль, который может быть последним (т.е. все группы из <tex>0</tex> имеют четные размеры) | + | Ответом будет <tex> \sum a[m][i]</tex>, где <tex>i</tex> {{---}} профиль, который может быть последним (т.е. все группы из <tex>0</tex> имеют четные размеры). |
==='''Реализация'''=== | ==='''Реализация'''=== | ||
− | <font color=green>// n, m - размер таблицы </font> | + | <font color=green>// n, m {{---}} размер таблицы </font> |
− | + | '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> | |
− | '''for''' <tex>j = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> | + | '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> |
− | '''if''' можно перейти из <tex>i</tex> в <tex>j</tex> профиль | + | '''if''' можно перейти из <tex>\mathtt{i}</tex> в <tex>\mathtt{j}</tex> профиль |
− | + | <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}] = \mathtt{1}</tex> | |
'''else''' | '''else''' | ||
− | <tex>\mathtt{d}[i][j] = \mathtt{0}</tex> | + | <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> | <tex>\mathtt{a}[\mathtt{0}][\mathtt{0}] = \mathtt{1}</tex> <font color=green>// Так как мы можем начать только с профиля где все клетки 0 </font> | ||
− | '''for''' <tex>k = \mathtt{1}..m - \mathtt{1} </tex> | + | '''for''' <tex>k = \mathtt{1}..\mathtt{m} - \mathtt{1} </tex> |
− | '''for''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> | + | '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> |
− | '''for''' <tex>j = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> | + | '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> |
− | <tex>\mathtt{a}[k][i] = \mathtt{a}[k][i] + \mathtt{a}[k - \mathtt{1}][j] \cdot \mathtt{d}[j][i]</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>ans = \mathtt{0}</tex> | + | <tex>\mathtt{ans} = \mathtt{0}</tex> |
− | '''for''' <tex>i = \mathtt{0}..(\mathtt{1} | + | '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt \ \mathtt{n}) - \mathtt{1}</tex> |
− | '''if''' можно закончить <tex>i</tex> профилем | + | '''if''' можно закончить <tex>\mathtt{i}</tex> профилем |
− | <tex>ans = ans + \mathtt{a}[m - \mathtt{1}][i]</tex> | + | <tex>\mathtt{ans} = \mathtt{ans} + \mathtt{a}[\mathtt{m} - \mathtt{1}][\mathtt{i}]</tex> |
− | '''return''' <tex>ans</tex> | + | '''return''' <tex>\mathtt{ans}</tex> |
''' Оценка сложности: ''' | ''' Оценка сложности: ''' | ||
− | подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n} | + | подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n}m</tex> в итоге <tex>O(2^{2n}m)</tex>. |
''' Оценка памяти: ''' | ''' Оценка памяти: ''' | ||
− | <tex>O(2^{2n}+2^{2n} | + | <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>. |
== '''Задача о симпатичных узорах''' == | == '''Задача о симпатичных узорах''' == | ||
Строка 79: | Строка 78: | ||
Тогда <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> \displaystyle \sum_{ | + | Ответом будет <tex> \displaystyle \sum_{i=0}^{2^n -1} a[m][i]</tex> |
==='''Реализация'''=== | ==='''Реализация'''=== | ||
− | <font color=green>// n, m - размер таблицы </font> | + | <font color=green>// n, m {{---}} размер таблицы </font> |
− | '''for''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> | + | '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> |
− | '''for''' <tex>j = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> | + | '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> |
− | '''if''' можно перейти из <tex>i</tex> в <tex>j</tex> профиль | + | '''if''' можно перейти из <tex>\mathtt{i}</tex> в <tex>\mathtt{j}</tex> профиль |
− | <tex>\mathtt{d}[i][j]\ =\ \mathtt{1}</tex> | + | <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{1}</tex> |
'''else''' | '''else''' | ||
− | <tex>\mathtt{d}[i][j]\ =\ \mathtt{0}</tex> | + | <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{0}</tex> |
− | '''for''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> | + | '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> |
− | <tex>\mathtt{a}[ | + | <tex>\mathtt{a}[0][\mathtt{i}]\ = \mathtt{1}</tex> <font color=green >// Так как мы можем начать c любого профиля</font> |
− | '''for''' <tex>k = \mathtt{1}..m - \mathtt{1} </tex> | + | '''for''' <tex>\mathtt{k} = \mathtt{1}.. \mathtt{m} - \mathtt{1} </tex> |
− | '''for''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> | + | '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> |
− | '''for''' <tex>j = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> | + | '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> |
− | <tex>\mathtt{a}[k][i] = \mathtt{a}[k][i] + \mathtt{a}[k - 1][j] \cdot \mathtt{d}[j][i]</tex> | + | <tex>\mathtt{a}[\mathtt{k}][\mathtt{i}] = \mathtt{a}[\mathtt{k}][\mathtt{i}] + \mathtt{a}[\mathtt{k} - 1][\mathtt{j}] \cdot \mathtt{d}[\mathtt{j}][\mathtt{i}]</tex> |
− | <tex>ans = \mathtt{0}</tex> | + | <tex>\mathtt{ans} = \mathtt{0}</tex> |
− | '''for''' <tex>i = \mathtt{0}..(\mathtt{1}<<n) - \mathtt{1}</tex> | + | '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex> |
− | <tex>ans = ans + a[m - \mathtt{1}][i]</tex> <font color=green>// Так как мы можем закончить любым профилем </font> | + | <tex>\mathtt{ans} = \mathtt{ans} + \mathtt{a}[\mathtt{m} - \mathtt{1}][\mathtt{i}]</tex> <font color=green>// Так как мы можем закончить любым профилем </font> |
− | '''return''' <tex>ans</tex> | + | '''return''' <tex>\mathtt{ans}</tex> |
''' Оценка сложности: ''' | ''' Оценка сложности: ''' | ||
− | подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n} | + | подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n}m</tex> в итоге <tex>O(2^{2n}m)</tex>. |
''' Оценка памяти: ''' | ''' Оценка памяти: ''' | ||
− | <tex>O(2^{2n}+2^{2n} | + | <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>. |
== Динамика по изломанному профилю == | == Динамика по изломанному профилю == | ||
Строка 112: | Строка 111: | ||
}} | }} | ||
− | Это очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому). | + | Это очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому). |
− | == Пример == | + | === Пример === |
− | Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через i-ю | + | Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через <tex>i</tex>-ю вертикаль сверху вниз, она переходит на предыдущую вертикаль и спускается до низу. Теперь профиль — это не только маска, но ещё и место излома. |
+ | [[Файл:img34.gif|300px|thumb|right|]] | ||
+ | Профилем будет пара <tex>(p, i)</tex>, в <tex>p</tex> будет информация о <tex>n + 1</tex> маленьком квадратике слева от базовой линии, имеющем с ней общие точки; <tex>i</tex> обозначает номер горизонтали, на которой произошел излом. Квадратики профиля будут нумероваться сверху вниз, так что угловой будет иметь номер <tex>i + 1</tex>. Горизонтали будем нумеровать с нуля, так что <tex>i</tex> пробегает значения от <tex>0</tex> до <tex>n - 1</tex>. | ||
− | + | Пусть <tex>d[pr_1][pr_2] = 1</tex> если из профиля <tex>pr_1</tex> = <tex>(p_1, i_1)</tex> можно перейти в <tex>pr_2 = (p_2, i_2)</tex>, иначе <tex>0</tex>. | |
+ | |||
+ | * Eсли <tex>i < n - 1</tex>, то <tex>i_1 + 1 = i_2</tex>, иначе <tex>i_2 = 0 </tex>; | ||
+ | |||
+ | * Mожно так положить доминошку, накрывающую квадратик с номером <tex>i + 1</tex>, что после этого в <tex>p_2</tex> будет храниться в точности информация о соответствующих квадратиках. | ||
+ | Проще говоря, доминошку можно класть только двумя способами {{---}} как показано на рисунках (на квадратик с номером <tex>i + 1</tex> можно положить не более одной вертикальной и горизонтальной доминошки). То, что потом получается после сдвига вниз излома, и будет новым профилем. Заметим, что если клетка <tex>i + 1</tex> занята, то доминошку уже не надо класть, и <tex>(p, i)</tex> логично отождествить с <tex>(p, i + 1)</tex>. Условно пишется {{---}} "<tex>i + 1</tex>", однако, нужно всегда иметь в виду возможность <tex>i = n - 1</tex>. | ||
+ | |||
+ | Легко заметить, что количество профилей увеличилось в <tex>2n</tex> раз (добавилось число от <tex>1</tex> до <tex>n</tex> и еще один бит). Но зато количество переходов резко сократилось с <tex>2^n</tex> до <tex>2</tex>. | ||
− | Для | + | <font color=green>//Для профиля (p, i) выводятся все переходы из него (нумерация горизонталей начинается с нуля и i = 0..n - 1)</font> |
+ | <font color=green>// Функция bit(x,i), возвращающая единицу или ноль или i-й бит в двоичной записи числа x</font> | ||
+ | '''print_all_links'''(<tex>\mathtt{p}</tex>, <tex>\mathtt{i}</tex>): | ||
+ | '''if''' <tex>\mathtt{bit}(\mathtt{p, \mathtt{i} + \mathtt{1}}) == \mathtt{0}</tex> | ||
+ | '''if''' <tex>\mathtt{i} == \mathtt{n} - \mathtt{1}</tex> | ||
+ | '''println'''<tex>((\mathtt{p} - (\mathtt{2} << \ \mathtt{i})) << \ \mathtt{1}</tex>, " ", <tex>\mathtt{0})</tex> | ||
+ | '''else''' | ||
+ | '''println'''<tex>(\mathtt{p} - (\mathtt{2} << \ \mathtt{i})</tex>, " ", <tex>\mathtt{i} + \mathtt{1})</tex> | ||
+ | '''else''' | ||
+ | '''if''' <tex>\mathtt{bit}(\mathtt{p}, \mathtt{i}) == \mathtt{0}</tex> | ||
+ | '''if''' <tex>\mathtt{i} == \mathtt{n} - \mathtt{1} </tex> | ||
+ | '''println'''<tex>((\mathtt{p} << \ \mathtt{1})</tex>, " ", <tex>\mathtt{0})</tex> | ||
+ | '''else''' | ||
+ | '''println'''<tex>(\mathtt{p} + (\mathtt{1} << \ \mathtt{n})</tex>, " ", <tex>(\mathtt{i} + \mathtt{1}) % \mathtt{n})</tex> | ||
+ | '''if''' <tex>\mathtt{i} < \mathtt{n} - \mathtt{1}</tex> && <tex>\mathtt{bit}(\mathtt{p, \mathtt{i} + \mathtt{2}}) == \mathtt{0}</tex> | ||
+ | '''println'''<tex>(\mathtt{p} + (\mathtt{4} << \ \mathtt{i})</tex>, " ", <tex>\mathtt{i} + \mathtt{1})</tex> | ||
+ | [[Файл:ok.jpg|640px|thumb|left|Возможные переходы]] | ||
− | + | При такой реализации существует немало профилей только с одним переходом (например, у которых <tex>(i + 1)</tex>-й бит равен единице). | |
− | + | Отождествим все профили с один переходом с теми, кто их них получается. Это будет выглядеть так: пусть <tex>pr_2</tex> (и только он) получается из <tex>pr_1</tex>, который, в свою очередь, получается из <tex>pr_0</tex>. Тогда имеются такие соотношения: <tex>d[pr_0, pr_1] = 1</tex>, <tex>d[pr_1, pr_2] = 1</tex>. Отождествить <tex>pr_1</tex> и <tex>pr_2</tex> {{---}} это, по сути, заменить эти два соотношение на одно, то есть теперь <tex>d[pr_0, pr_1] = 0</tex> и <tex>d[pr_1, pr_2] = 0</tex>, но <tex>d[pr_0, pr_2] = 1</tex>, и так далее. | |
− | |||
− | + | Таким образом, возможно сокращение профилей не менее чем вдвое. Хотя можно совершить дальнейшие оптимизации. | |
+ | |||
+ | В итоге асимптотика составляет <tex>O(2^nnm)</tex>. Это доказывает, что данный метод значительно лучше простого способа подсчёта динамики. | ||
== См. также == | == См. также == | ||
Строка 132: | Строка 157: | ||
== Источники информации == | == Источники информации == | ||
*[http://informatics.mccme.ru/moodle/file.php/9/dyn_prof.pdf Динамическое программирование по профилю] | *[http://informatics.mccme.ru/moodle/file.php/9/dyn_prof.pdf Динамическое программирование по профилю] | ||
− | + | *[http://informatics.mccme.ru/mod/book/view.php?id=290&chapterid=78 Динамическое программирование по изломанному профилю] | |
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Динамическое программирование]] | [[Категория: Динамическое программирование]] |
Текущая версия на 19:27, 4 сентября 2022
Определение: |
Динамическое программирование по профилю (англ. dynamic programming with profile) — способ оптимизации перебора количества вариантов с помощью динамического программирования, когда одно из измерений небольшое. |
Определение: |
Профиль (англ. profile) — один из столбцов (строк), удовлетворяющий условию задачи. Обычно используется в качестве состояния динамики. |
Общие принципы
Обычно дана таблица и надо посчитать количество замощений этой таблицы некоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию. Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо заполнить и для него нам надо
предыдущих линий. Тогда можно перебрать все замощения длиной . В итоге нужно заполнить данную таблицу этими замощениями. Получается, что если перебирать все варианты нам понадобится времени, а если перебирать только состояния и переходить по ним нам потребуется времени (где — количество способов замощения одной клетки).Задача о замощении домино
Условие
Найти количество способов замостить таблицу
с помощью доминошек размерами .Решение
Для удобства можно хранить профили в виде двоичных масок. В качестве состояния динамики будем использовать профили размерами
. В этом профиле будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе . Таких профилей будет . Теперь проверим из какого профиля в какой можно перейти.Из профиля
в профиль можно перейти если выполняются условия:- Можно положить горизонтальные домино. То есть там где в профиле стоит , в профиле должен стоять .
- Можно доложить в оставшиеся клетки вертикальные домино. То есть оставшиеся в профиле должны образовывать четные подстроки.
Пусть
если из профиля можно перейти в -ый, иначе .Пусть так же
— количество способов замощения первых столбцов и заканчивавшийся на -ом профиле. ТогдаОтветом будет
, где — профиль, который может быть последним (т.е. все группы из имеют четные размеры).Реализация
// n, m — размер таблицы forfor if можно перейти из в профиль else // Так как мы можем начать только с профиля где все клетки 0 for for for for if можно закончить профилем return
Оценка сложности: подсчет
, и подсчет в итоге .Оценка памяти:
, так же можно заметить что в массиве для состояния нам нужно только состояние, при такой реализации нужно будет . Еще можно не считать массив , а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется памяти, но нам потребуется больше времени , где время проверки возможности перехода из в равно и тогда время получается .Задача о симпатичных узорах
Условие
Дана таблица
, каждая клетка которой может быть окрашена в один из двух цветов: белый или черный. Симпатичным узором называется такая раскраска, при которой не существует квадрата , в котором все клетки одного цвета. Требуется найти количество симпатичных узоров для соответствующей таблицы.Решение
Для удобства можно хранить профиля в виде двоичных масок. В качестве состояния динамики будем использовать профили размера
. В этом профиле будет означать что клетка закрашена в черный цвет, и если в белый. Из профиля в -ый можно перейти если выполнено условие:- если поставить и профиль рядом, то не должно быть квадратов одного цвета
Пусть
если из профиля можно перейти в -ый, иначе .Пусть так же
— количество способов раскрашивания первые столбцов и заканчивавшийся на -ом профиле. ТогдаОтветом будет
Реализация
// n, m — размер таблицы forfor if можно перейти из в профиль else for // Так как мы можем начать c любого профиля for for for for // Так как мы можем закончить любым профилем return
Оценка сложности: подсчет
, и подсчет в итоге .Оценка памяти:
, так же можно заметить что в массиве для состояния нам нужно только состояние, при такой реализации нужно будет . Еще можно не считать массив , а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется памяти, но нам потребуется больше времени , где время проверки возможности перехода из в равно и тогда время получается .Динамика по изломанному профилю
Определение: |
Изломанный профиль (англ. broken profile) — обобщение прямого профиля на случай, когда обработанным является не целое число столбцов, а некоторое количество столбцов и несколько первых клеток следующего столбца. |
Это очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому).
Пример
Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через
-ю вертикаль сверху вниз, она переходит на предыдущую вертикаль и спускается до низу. Теперь профиль — это не только маска, но ещё и место излома.Профилем будет пара
, в будет информация о маленьком квадратике слева от базовой линии, имеющем с ней общие точки; обозначает номер горизонтали, на которой произошел излом. Квадратики профиля будут нумероваться сверху вниз, так что угловой будет иметь номер . Горизонтали будем нумеровать с нуля, так что пробегает значения от до .Пусть
если из профиля = можно перейти в , иначе .- Eсли , то , иначе ;
- Mожно так положить доминошку, накрывающую квадратик с номером , что после этого в будет храниться в точности информация о соответствующих квадратиках.
Проще говоря, доминошку можно класть только двумя способами — как показано на рисунках (на квадратик с номером
можно положить не более одной вертикальной и горизонтальной доминошки). То, что потом получается после сдвига вниз излома, и будет новым профилем. Заметим, что если клетка занята, то доминошку уже не надо класть, и логично отождествить с . Условно пишется — " ", однако, нужно всегда иметь в виду возможность .Легко заметить, что количество профилей увеличилось в
раз (добавилось число от до и еще один бит). Но зато количество переходов резко сократилось с до .//Для профиля (p, i) выводятся все переходы из него (нумерация горизонталей начинается с нуля и i = 0..n - 1) // Функция bit(x,i), возвращающая единицу или ноль или i-й бит в двоичной записи числа x print_all_links(, ): if if println , " ", else println , " ", else if if println , " ", else println , " ", if && println , " ",
При такой реализации существует немало профилей только с одним переходом (например, у которых
-й бит равен единице). Отождествим все профили с один переходом с теми, кто их них получается. Это будет выглядеть так: пусть (и только он) получается из , который, в свою очередь, получается из . Тогда имеются такие соотношения: , . Отождествить и — это, по сути, заменить эти два соотношение на одно, то есть теперь и , но , и так далее.Таким образом, возможно сокращение профилей не менее чем вдвое. Хотя можно совершить дальнейшие оптимизации.
В итоге асимптотика составляет
. Это доказывает, что данный метод значительно лучше простого способа подсчёта динамики.