Динамика по профилю





Классическими задачами, решающимися динамикой по профилю, являются задачи на замощение поля какими-нибудь фигурами. Причём спрашиваться могут разные вещи, например, количество способов замощения или замощение минимальным количеством фигур.

Эти задачи можно решить полным перебором за , где a — количество вариантов замощения одной клетки. Динамика по профилю же оптимизирует время по одной из размерностей до линейной, оставив от себя в экспоненте только коэффициент. Получится что-то такое: .

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

Почти всегда состояние — это профиль и то, где этот профиль. А переход увеличивает это местоположение на один. Узнать, можно ли перейти из одного профиля в другой можно за линейное от размера профиля время. Это можно проверять каждый раз во время пересчёта, но можно и предподсчитать. Предподсчитывать будем двумерный массив can[mask][next_mask] — можно ли от одной маски перейти к другой, положив несколько фигурок, увеличив положение профиля на один. Если предподсчитывать, то времени на выполнение потребуется меньше, а памяти — больше.

Работы которые могут быть Вам интерессными captulo-xxiii.html

captulo-xxiv.html

captulo-xxix.html

captulo-xxvii.html

captulo-xxviii.html

captulo-xxx.html

captulo-xxxi.html

captulo-xxxii.html

captulo-xxxiii.html

captulo-xxxiv.html

captulo-xxxix.html

captulo-xxxv.html

captulo-xxxvi.html

captulo-xxxvii.html

captulo-xxxviii.html

caractere-evolutive-ale-tumorilor-benigne.html

caractere-macroscopice-ale-tumorilor-benigne.html

caractere-macroscopice-ale-tumorilor-maligne.html

caractersticas.html

car-aleksej-mihajlovich-patriarh-nikon.html

caravan-to-chautauqua.html

© domain.tld 2017. Design by Design by toptodoc.ru


Автор:

Дата:

Каталог: Образовательный документ