Изменения

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

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

<tex>\mathtt{d}[\mathtt{i}][\mathtt{j}] = \mathtt{0}</tex>

'''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}\times m</tex> в итоге <tex>O(2^{2n}\times m)</tex>.

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

Ответом будет <tex> \displaystyle \sum_{ji=0}^{2^n -1} a[m][i]</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>

<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}[i0][0\mathtt{i}]\ = \mathtt{1}</tex> <font color=green >// Так как мы можем начать c любого профиля</font> '''for''' <tex>\mathtt{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 } - 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}<<\ \mathtt{n}) - \mathtt{1}</tex> <tex>\mathtt{ans } = \mathtt{ans } + \mathtt{a}[\mathtt{m } - \mathtt{1}][\mathtt{i}]</tex> <font color=green>// Так как мы можем закончить любым профилем </font> '''return''' <tex>\mathtt{ans}</tex>

подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n}\times m</tex> в итоге <tex>O(2^{2n}\times m)</tex>.

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

Это очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому). === Пример ===Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через <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><p, i>+ 1</tex>, что после этого в <tex>pp_2</tex> будет храниться в точности информация о соответствующих квадратиках.Проще говоря, доминошку можно класть только двумя способами {{---}} как показано на рисунках (на квадратик с номером <tex>n i + 1</tex> маленьком квадратике слева от базовой линииможно положить не более одной вертикальной и горизонтальной доминошки). То, что потом получается после сдвига вниз излома, и будет новым профилем. Заметим, имеющем с ней общие точки; что если клетка <tex>i+ 1</tex> обозначает номер горизонтализанята, на которой произошел излом. Квадратики профиля будут нумероваться сверху внизто доминошку уже не надо класть, так что угловой будет иметь номер и <tex>(p, i + 1)</tex>. Горизонтали будем нумеровать логично отождествить с нуля, так что <tex>(p, i+ 1)</tex> пробегает значения от . Условно пишется {{---}} "<tex>0i + 1</tex> до ", однако, нужно всегда иметь в виду возможность <tex>i = n - 1</tex>.

Для двух Легко заметить, что количество профилей увеличилось в <tex>pr12n</tex> = раз (добавилось число от <tex>1<p1, i1/tex> до <tex>n</tex> и еще один бит). Но зато количество переходов резко сократилось с <tex>pr2 = <p2, i2>2^n</tex> положим до <tex>d[pr1][pr2] = 12</tex> если и только если:.

<font color=green>//Для профиля (p, i) выводятся все переходы из него (нумерация горизонталей начинается с нуля и i = 0..n - 1. Eсли )</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>i1 \mathtt{i} + \mathtt{1 })</tex> '''else''' '''if''' <tex>\mathtt{bit}(\mathtt{p}, \mathtt{i}) == \mathtt{0}</tex> '''if''' <tex>\mathtt{i} == i2\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>i2 \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|Возможные переходы]]

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

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