Меню

Симпатичные узоры динамическое программирование

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

Определение:
Динамическое программирование по профилю (англ. dynamic programming with profile) — способ оптимизации перебора количества вариантов с помощью динамического программирования, когда одно из измерений небольшое.
Определение:
Профиль (англ. profile) — один из столбцов (строк), удовлетворяющий условию задачи. Обычно используется в качестве состояния динамики.

Содержание

Общие принципы [ править ]

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

Из профиля [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_^ <2^n -1>a[k-1][j]\cdot d[j][i][/math]

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

Реализация [ править ]

Оценка сложности: подсчет [math]d — 2^<2n>[/math] , и подсчет [math]a — 2^<2n>m[/math] в итоге [math]O(2^<2n>m)[/math] .

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

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

Условие [ править ]

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

Читайте также:  Узоры косы колосок спицами схемы

Решение [ править ]

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

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

Ответом будет [math] \displaystyle \sum_^ <2^n -1>a[m][i][/math]

Реализация [ править ]

Оценка сложности: подсчет [math]d — 2^<2n>[/math] , и подсчет [math]a — 2^<2n>m[/math] в итоге [math]O(2^<2n>m)[/math] .

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

Динамика по изломанному профилю [ править ]

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

Это очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому).

Пример [ править ]

Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через [math]i[/math] -ю вертикаль сверху вниз, она переходит на предыдущую вертикаль и спускается до низу. Теперь профиль — это не только маска, но ещё и место излома.

Профилем будет пара [math](p, i)[/math] , в [math]p[/math] будет информация о [math]n + 1[/math] маленьком квадратике слева от базовой линии, имеющем с ней общие точки; [math]i[/math] обозначает номер горизонтали, на которой произошел излом. Квадратики профиля будут нумероваться сверху вниз, так что угловой будет иметь номер [math]i + 1[/math] . Горизонтали будем нумеровать с нуля, так что [math]i[/math] пробегает значения от [math]0[/math] до [math]n — 1[/math] .

Пусть [math]d[pr_1][pr_2] = 1[/math] если из профиля [math]pr_1[/math] = [math](p_1, i_1)[/math] можно перейти в [math]pr_2 = (p_2, i_2)[/math] , иначе [math]0[/math] .

  • Eсли [math]i \lt n — 1[/math] , то [math]i_1 + 1 = i_2[/math] , иначе [math]i_2 = 0 [/math] ;
  • Mожно так положить доминошку, накрывающую квадратик с номером [math]i + 1[/math] , что после этого в [math]p_2[/math] будет храниться в точности информация о соответствующих квадратиках.

Проще говоря, доминошку можно класть только двумя способами — как показано на рисунках (на квадратик с номером [math]i + 1[/math] можно положить не более одной вертикальной и горизонтальной доминошки). То, что потом получается после сдвига вниз излома, и будет новым профилем. Заметим, что если клетка [math]i + 1[/math] занята, то доминошку уже не надо класть, и [math](p, i)[/math] логично отождествить с [math](p, i + 1)[/math] . Условно пишется — » [math]i + 1[/math] «, однако, нужно всегда иметь в виду возможность [math]i = n — 1[/math] .

Читайте также:  Схемы вязания людей спицами

Легко заметить, что количество профилей увеличилось в [math]2n[/math] раз (добавилось число от [math]1[/math] до [math]n[/math] и еще один бит). Но зато количество переходов резко сократилось с [math]2^n[/math] до [math]2[/math] .

При такой реализации существует немало профилей только с одним переходом (например, у которых [math](i + 1)[/math] -й бит равен единице). Отождествим все профили с один переходом с теми, кто их них получается. Это будет выглядеть так: пусть [math]pr_2[/math] (и только он) получается из [math]pr_1[/math] , который, в свою очередь, получается из [math]pr_0[/math] . Тогда имеются такие соотношения: [math]d[pr_0, pr_1] = 1[/math] , [math]d[pr_1, pr_2] = 1[/math] . Отождествить [math]pr_1[/math] и [math]pr_2[/math] — это, по сути, заменить эти два соотношение на одно, то есть теперь [math]d[pr_0, pr_1] = 0[/math] и [math]d[pr_1, pr_2] = 0[/math] , но [math]d[pr_0, pr_2] = 1[/math] , и так далее.

Таким образом, возможно сокращение профилей не менее чем вдвое. Хотя можно совершить дальнейшие оптимизации.

В итоге асимптотика составляет [math]O(2^nnm)[/math] . Это доказывает, что данный метод значительно лучше простого способа подсчёта динамики.

Источник

Симпатичные узоры динамическое программирование

Учебные задачи:
Задача A.
[Наибольшая общая подпоследовательность (НОП)]
В данной задаче можно применить классический алгоритм Нудельмана-Вунша.
Задача B.
[Наибольшая общая подпоследовательность с восстановлением ответа]
Продолжение предыдущей задачи с той разницей, что в текущей реализации использовались барьерные первый столбец и строка.
Задача C.
[Биномиальные коэффициенты]
Наверное последняя проходная задача на ДП в этом цикле. Суть задачи сводиться к классической черепашке.
Олимпиадные задачи:
Задача A.
[Движение по полосам]
Очень хорошая задача. Решаем ДП с двумя параметрами: количество использованных полос(s), количество использованных дорог(r). Ответом на вопрос будет являться значение dp(n,m), где n – общее количество полос, m – общее количество дорог. Чтобы найти значение на текущем шаге dp(s,r), необходимо перебрать и сложить все возможные значения dp(s-1,r’).
Задача B.
[Еловая аллея]
Данная реализация отражает идею, предложенную в разборе, но имеет сложность M*M*N.
Задача C.
[Почти палиндром]
Классическая LR динамика. Нужно быть осторожным в выборе типа данных для элементов таблицы.
Дополнительные олимпиадные задачи:
Задача A.
[Электронная почта]
Суть задачи сводится к поиску оптимальной стратегии в игре Zuma, с одним только отличием, что нет минимального количества рядом стоящих шариков, которые могут быть удалены за один раз. В обычной игре это число равно 3. На spoj.pl есть задача ZUMA, в которой как раз фигурирует это минимальное значение рядом стоящих шариков.
Решать будем двумерной LR динамикой. В таблице dp[i][j] находится оптимальный ответ для подмассива с i-ого по j-ый элементы. Базой динамики будут служить два факта:
1) if (i > j) dp[i][j] = 0
2) if (i == j) dp[i][j] = 1
Теперь рассмотрим общий случай для произвольных i и j:
I) Очевидно, что может быть такая ситуация, когда исходный массив можно разбить на набор непересекающихся подмассивов и последовательно избавиться от каждого из них. Например для массива A = это будет оптимальная стратегия. Этот случай обрабатывается в строках 40-41.
II) Отдельно стоит рассмотреть случай, когда элементы a[i] и a[j] равны. Возможно стоит сначала избавиться от подмассива [i+1, j-1], а потом за одну итерацию убрать крайние элементы за одну итерацию. Например для массива B = это будет оптимальная стратегия. Этот случай обрабатывается в строке 44.
III) Продолжим рассматривать случай, когда граничные элементы подмассива равны. Может возникнуть такая ситуация, когда есть элемент a[i] == a[k] == a[j], причем i оптимальной стратегия будет III с элементами II(для удаления подмассивов межды единицами). Этот момент обрабатывается в строках 45-49.
Задача B.
[Плитки]
Шикарная задача на динамику по рванному краю(динамика по профилю).
Будем заполнять таблицу dp[clr][len][mask], где clr – цвет, на который заканчивается последовательность длины len, удовлетворяющая битовой маске mask. Разберемся с битовой маской.
Сразу оговоримся, что предложенное решение использует маску, ориентированную на несимметричную матрицу цветов. Условно обозначим 3 возможных цвета как R,G и B. Тогда имеем матрицу:
R G B
R 0 1 2
G 3 4 5
B 6 7 8
На пересечении цветов указано значение row * 3 + col, где row – номер строки, col – номер столбца. Получаем следующий массив:
8 7 6 5 4 3 2 1 0 — номер сочетания цветов
BB BG BR GB GG GR RB RG RR — сочетание цветов
Пусть номер сочетания цветов указывает на бит в маске.
Зафиксируем для таблицы dp значение clr, len и mask. Номер единичного бита в mask говорит о том, что сочетание цветов, соответствующего номеру бита уже было в конце строки в диапазоне [len,n-1].
Отсюда можно получить базу динамики. Перебрав все пары цветов c1 и с2, в случае валидной комбинации c1-c2 dp[c1][n-2][code(c1,c2)] = 1. Случай, когда длина строки равна 1 можно рассмотреть отдельно.
Подсчет всех остальных значений отображен в строках 104-120:
Для фиксированных c1, c2, len, mask можно однозначно определить ответ:
dp[c1][len][mask] = dp[c2][len+1][mask] + dp[c2][len+1][mask ^ cur_mask], где cur_mask – закодированная комбинация цветов c1 и с2. Говоря другими словами последовательность, заканчивающаяся цветом c1 длины len и маской mask могла получиться из строки, заканчивающейся цветом c2, длины len+1 с той же маской, а также маской, в которой ранее не использовалось сочетание цветов c1 и с2.

Читайте также:  Шапка для подростка мальчика спицами с отворотом

Ответ формируется из элементов dp[c][0][mask], где с принимает все возможные значения цветов, а mask принимает все возможные валидные комбинации цветов, содержащие всю матрицу цветов.
Задача C.
[Симпатичные узоры возвращаются]
Задача является логическим продолжением задачи Симпатичные узоры, которое наверное является классикой динамики по рваному контуру. Ее разбор дан в лекции. Здесь лежит мое решение.
Исходная задача также разобрана в лекции. Суть ее сводится к быстрому перемножению матриц. Данный подход использовался в алгоритме для нахождения достижимости за k шагов произвольной вершины j из произвольной вершины i. Там нужно было возвести исходную матрицу смежности в степень k.

Источник