Изменения

Перейти к: навигация, поиск

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

481 байт убрано, 00:45, 15 января 2015
Пример
Таким образом, возможно сокращение профилей не менее чем вдвое. Дальнейшие оптимизации мы оставляем читателю.
 
По-прежнему <tex>a[k][i]</tex> {{---}} количество способов замощения первых <tex>k - 1</tex> столбцов и заканчивавшийся на <tex>p_i</tex>-ом профиле.
Тогда <tex>a[k][p_i]=\displaystyle \sum_{j = 0}^{2^nn - 1} a[k - 1][j]\cdot d[j][p_i]</tex>
Ответом будет <tex> \sum a[m][p_i]</tex>, где <tex>p_i</tex> {{---}} профиль, который может быть последним.
В итоге получаем асимптотику <tex>O(2^nnm)</tex>. Она значительно лучше всего, что мы получали до сих пор, и это серьезный повод использовать изломанный профиль вместо обычного.
49
правок

Навигация