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

Материал из Викиконспекты
Перейти к: навигация, поиск
(нам понадобиться O(a^nm) времени -> нам понадобится O(a^nm) времени)
(не показано 47 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition='''Динамическое программирование по профилю''' <tex>-</tex> способ оптимизации перебора количества вариантов с помощью [[Динамическое программирование|динамического программирования]], когда одно из измерений не большое.
+
|definition='''Динамическое программирование по профилю''' (англ. ''dynamic programming with profile'') {{---}} способ оптимизации перебора количества вариантов с помощью [[Динамическое программирование|динамического программирования]], когда одно из измерений небольшое.
 
}}
 
}}
 
{{Определение
 
{{Определение
|definition='''Профиль''' - один из столбцов (строк), удовлетворяющий условию задачи. Обычно используется в качестве состояния динамики.
+
|definition='''Профиль''' (англ. ''profile'') {{---}} один из столбцов (строк), удовлетворяющий условию задачи. Обычно используется в качестве состояния динамики.
 
}}
 
}}
  
 
== Общие принципы ==
 
== Общие принципы ==
Обычно дана таблица и надо посчитать количество замощений этой таблицы некоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию. Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо заполнить и для него нам надо <tex>k</tex> предыдущих линий. Тогда можно перебрать все замощения  длиной <tex>k\times n</tex>. В итоге нужно заполнить данную таблицу этими замощениями. Получается, что если перебирать все варианты нам понадобиться <tex>O(a^{nm})</tex> времени, а если перебирать только состояния и переходить по ним нам потребуется <tex>O(a^{kn}*m)</tex> времени (где а - количество способов замещения 1 клетки).
+
Обычно дана таблица и надо посчитать количество замощений этой таблицы некоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию. Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной. Затем пусть у нас есть правило по которому надо заполнить и для него нам надо <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>. В этом профиле 1 будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе 0. Таких профилей будет <tex>2^n</tex>.
+
В качестве состояния динамики будем использовать профили размерами <tex>n</tex>. В этом профиле <tex>1</tex> будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе <tex>0</tex>. Таких профилей будет <tex>2^n</tex>.
 
Теперь проверим из какого профиля в какой можно перейти.
 
Теперь проверим из какого профиля в какой можно перейти.
 
[[Файл:Домино.png|270px|thumb|right|Переходы (1-правильный переход, 2,3-неправильные)]]
 
  
 
Из профиля <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> имеют четные размеры).
  
 
==='''Реализация'''===
 
==='''Реализация'''===
 
+
<font color=green>// n, m {{---}} размер таблицы </font>
  // n, m размеры таблицы
+
  '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
for i = 0..(1<<n) - 1
+
    '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
for j = 0..(1<<n) - 1
+
        '''if''' можно перейти из <tex>\mathtt{i}</tex> в <tex>\mathtt{j}</tex> профиль  
if можно перейти из i в j профиль  
+
            <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}] = \mathtt{1}</tex>
        d[i][j] = 1;
+
'''else'''
else  
+
    <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}] = \mathtt{0}</tex>
d[i][j] = 0;
+
  <tex>\mathtt{a}[\mathtt{0}][\mathtt{0}] = \mathtt{1}</tex> <font color=green>// Так как мы можем начать только с профиля где все клетки 0 </font>
  a[0][0] = 1; // Так как мы можем начать только с профиля где все клетки 0
+
  '''for''' <tex>k = \mathtt{1}..\mathtt{m} - \mathtt{1} </tex>
  for k = 1..m - 1
+
    '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
for i = 0..(1<<n) - 1
+
        '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
for j = 0..(1<<n) - 1
+
    <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>
a[k][i] += a[k-1][j] * d[j][i];
+
  <tex>\mathtt{ans} = \mathtt{0}</tex>
  ans = 0;
+
  '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \lt \lt \ \mathtt{n}) - \mathtt{1}</tex>
  for i = 0..(1<<n) - 1
+
    '''if''' можно закончить <tex>\mathtt{i}</tex> профилем
if можно закончить i профилем
+
        <tex>\mathtt{ans} = \mathtt{ans} + \mathtt{a}[\mathtt{m} - \mathtt{1}][\mathtt{i}]</tex>
ans += a[m-1][i];
+
  '''return''' <tex>\mathtt{ans}</tex>
  return ans;
 
  
 
''' Оценка сложности: '''
 
''' Оценка сложности: '''
подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n}\times m</tex> в итоге <tex>O(2^{2n}\times m)</tex>
+
подсчет <tex>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n}m</tex> в итоге <tex>O(2^{2n}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)</tex> памяти, но нам потребуется больше времени <tex>2^{2n}\times m\times f(i,j)</tex>, где <tex>f(i,j)</tex> время проверки возможности перехода из <tex>i</tex> в <tex>j</tex> равно <tex>n</tex> и тогда время получается <tex>O(2^{2n}\times m\times n)</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>.
  
 
== '''Задача о симпатичных узорах''' ==
 
== '''Задача о симпатичных узорах''' ==
Строка 71: Строка 69:
 
==='''Решение'''===
 
==='''Решение'''===
 
Для удобства можно хранить профиля в виде двоичных масок.
 
Для удобства можно хранить профиля в виде двоичных масок.
В качестве состояния динамики будем использовать профили размера <tex>n</tex>. В этом профиле 1 будет означать что клетка закрашена в черный цвет, и 0 если в белый.
+
В качестве состояния динамики будем использовать профили размера <tex>n</tex>. В этом профиле <tex>1</tex> будет означать что клетка закрашена в черный цвет, и <tex>0</tex> если в белый.
 
Из профиля <tex>i</tex> в <tex>j</tex>-ый можно перейти если выполнено условие:
 
Из профиля <tex>i</tex> в <tex>j</tex>-ый можно перейти если выполнено условие:
 
* если поставить <tex>i</tex> и <tex>j</tex> профиль рядом, то не должно быть квадратов <tex>2\times 2</tex> одного цвета
 
* если поставить <tex>i</tex> и <tex>j</tex> профиль рядом, то не должно быть квадратов <tex>2\times 2</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> \displaystyle \sum_{j=0}^{2^n -1} a[m][i]</tex>
+
Ответом будет <tex> \displaystyle \sum_{i=0}^{2^n -1} a[m][i]</tex>
  
 
==='''Реализация'''===
 
==='''Реализация'''===
  // n, m размеры таблицы   
+
  <font color=green>// n, m {{---}} размер таблицы </font>  
  for i = 0..(1<<n) - 1
+
  '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
for j = 0..(1<<n) - 1
+
    '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
if можно перейти из i в j профиль  
+
        '''if''' можно перейти из <tex>\mathtt{i}</tex> в <tex>\mathtt{j}</tex> профиль  
d[i][j] = 1;
+
            <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{1}</tex>
else  
+
'''else'''
d[i][j] = 0;
+
    <tex>\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{0}</tex>
  for i = 0..(1<<n) - 1
+
  '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
a[i][0] = 1; // Так как мы можем начать c любого профиля
+
    <tex>\mathtt{a}[0][\mathtt{i}]\ = \mathtt{1}</tex> <font color=green >// Так как мы можем начать c любого профиля</font>
  for k = 1..m - 1
+
  '''for''' <tex>\mathtt{k} = \mathtt{1}.. \mathtt{m} - \mathtt{1} </tex>
for i = 0..(1<<n) - 1
+
    '''for'''  <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
for j = 0..(1<<n) - 1
+
        '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
a[k][i] += a[k-1][j] * d[j][i];
+
    <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> 
  ans = 0;
+
  <tex>\mathtt{ans} = \mathtt{0}</tex>
  for i = 0..(1<<n) - 1
+
  '''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} << \ \mathtt{n}) - \mathtt{1}</tex>
ans += a[m-1][i] // Так как мы можем закончить любым профилем
+
    <tex>\mathtt{ans} = \mathtt{ans} + \mathtt{a}[\mathtt{m} - \mathtt{1}][\mathtt{i}]</tex> <font color=green>// Так как мы можем закончить любым профилем </font>
  return ans;
+
  '''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>d - 2^{2n}</tex> , и подсчет <tex>a - 2^{2n}m</tex> в итоге <tex>O(2^{2n}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)</tex> памяти, но нам потребуется больше времени <tex>2^{2n}\times m\times f(i,j)</tex>, где <tex>f(i,j)</tex> время проверки возможности перехода из <tex>i</tex> в <tex>j</tex> равно <tex>n</tex> и тогда время получается <tex>O(2^{2n}\times m\times n)</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>.
 +
 
 +
== Динамика по изломанному профилю ==
 +
 
 +
{{Определение
 +
|definition='''Изломанный профиль''' (англ. ''broken profile'') {{---}} обобщение прямого профиля на случай, когда обработанным является не целое число столбцов, а некоторое количество столбцов и несколько первых клеток следующего столбца.
 +
}}
 +
 
 +
Это очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому).
 +
 
 +
=== Пример ===
 +
Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через <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>. Это доказывает, что данный метод значительно лучше простого способа подсчёта динамики.
  
 
== См. также ==
 
== См. также ==
 
*[[Динамическое программирование]]
 
*[[Динамическое программирование]]
== Ссылки ==
+
 
 +
== Источники информации ==
 
*[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 Динамическое программирование по изломанному профилю]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Динамическое программирование]]
 
[[Категория: Динамическое программирование]]

Версия 09:28, 12 апреля 2021

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


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


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

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

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

Условие

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

Решение

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

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

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

Решение

Для удобства можно хранить профиля в виде двоичных масок. В качестве состояния динамики будем использовать профили размера [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_{j=0}^{2^n -1} a[k-1][j]\cdot d[j][i][/math]

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

Реализация

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

Img34.gif

Профилем будет пара [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].

//Для профиля (p, i) выводятся все переходы из него (нумерация горизонталей начинается с нуля и i = 0..n - 1)
// Функция bit(x,i), возвращающая единицу или ноль или i-й бит в двоичной записи числа x
print_all_links([math]\mathtt{p}[/math], [math]\mathtt{i}[/math]):
    if [math]\mathtt{bit}(\mathtt{p, \mathtt{i} + \mathtt{1}}) == \mathtt{0}[/math]
        if [math]\mathtt{i} == \mathtt{n} - \mathtt{1}[/math]
            println[math]((\mathtt{p} - (\mathtt{2} \lt \lt  \ \mathtt{i})) \lt \lt  \ \mathtt{1}[/math], " ", [math]\mathtt{0})[/math]
        else
            println[math](\mathtt{p} - (\mathtt{2} \lt \lt  \ \mathtt{i})[/math], " ", [math]\mathtt{i} + \mathtt{1})[/math]
    else 
        if [math]\mathtt{bit}(\mathtt{p}, \mathtt{i}) == \mathtt{0}[/math]
            if [math]\mathtt{i} == \mathtt{n} - \mathtt{1} [/math]
               println[math]((\mathtt{p} \lt \lt  \ \mathtt{1})[/math], " ", [math]\mathtt{0})[/math]
            else   
               println[math](\mathtt{p} + (\mathtt{1} \lt \lt  \ \mathtt{n})[/math], " ", [math](\mathtt{i} + \mathtt{1}) % \mathtt{n})[/math]
    if [math]\mathtt{i} \lt  \mathtt{n} - \mathtt{1}[/math] && [math]\mathtt{bit}(\mathtt{p, \mathtt{i} + \mathtt{2}}) == \mathtt{0}[/math]
            println[math](\mathtt{p} + (\mathtt{4} \lt \lt  \ \mathtt{i})[/math], " ", [math]\mathtt{i} + \mathtt{1})[/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]. Это доказывает, что данный метод значительно лучше простого способа подсчёта динамики.

См. также

Источники информации