3622
правки
Изменения
м
Нет описания правки
Это очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому).
=== Пример ===
Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через <tex>i</tex>-ю горизонталь сверху вниз, она переходит на предыдущую вертикаль и спускается до низу. Теперь профиль — это не только маска, но ещё и место излома.
[[Файл:img34.gif|300px|thumb|right|]]
Отождествим все профили с один переходом с теми, кто их них получается. Это будет выглядеть так: пусть <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>. Она Это доказывает, что данный метод значительно лучше всего, что мы получали до сих пор, и это серьезный повод использовать изломанный профиль вместо обычногопростого способа подсчёта динамики.
== См. также ==
