Алгоритм прямой прогонки

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Обозначим через g_j(x_j) максимальную прибыль, получаемую на этапах 1, 2,..., j при заданном x_j, (где x_j — размер стада к началу этапа J+1). Рекуррентное соотношение записывается в следующем виде:

Сравнение двух формулировок показывает, что представление x_j_-1 через x_j создает более существенные препятствия для вычислений, чем представление z_j₊₁ через z_j.

В замене x_j_-1=(x_j+y_j)/2 подразумевается целочисленность правой части, тогда как на равенство z_j₊₁=2(z_j-y_j) такое требование не накладывается. Таким образом в случае процедуры прямой прогонки значения y_j и x_j, связанные неравенством

должны дополнительно удовлетворять условию целочисленности их полусуммы, связанному с видом зависимости х_j_-1 от x_j,. Рассмотренный пример иллюстрирует трудности вычислительного характера, которые обычно возникают при использовании алгоритма прямой прогонки.

Сначала рассмотрим задачу в общей постановке. Если обозначить количество вопросов типа і через k_i, то задача принимает следующий вид:

Если отбросить требования целочисленности k_i, то решение задачи нетрудно найти с помощью симплекс-метода. В самом деле, так как остается лишь одно ограничение, базисной будет только одна переменная, и задача сводится к выбору типа і, для которого величина v_iW/w_i принимает максимальное значение. Исходная задача не является задачей линейного программирования, и для ее решения необходимо использовать метод динамического программирования. Следует отметить, что рассматриваемая задача может быть также решена с помощью методов целочисленного программирования.

Каждый из трех основных элементов модели ДП определяется следующим образом.

1. Этап j ставится в соответствии типу j, j=1, 2, …, N.

2. Состояние y_j на этапе j выражает суммарный вес вопросов, количество ответов на которые приняты на этапах j, j+1, …, N; при этом y₁=W и y_j=0, 1, …, W при j=2, 3, …, N.

3. Варианты решения k_j на этапе j описываются количеством вопросов типа j. Значение k_j заключено в пределах от нуля до [W/w_j], где [W/w_j]-целая часть числа (W/w_j).

Пусть f_i(y_i)-максимальный суммарный вес вопросов, ответы на которые приняты на этапах j, j+1, …, N при заданном состоянии y_j.

Рекуррентное соотношение (для процедуры обратной прогонки) имеет следующий вид:

Заметим, что максимальное допустимое значение k_j ограничено величиной [y_j/w_j]. Это позволяет автоматически исключать все не являющиеся допустимыми варианты при заданном значении переменной состояния y_j.

Оптимальное решение определяется теперь следующим образом. Из условия W=30 следует, что первый этап решения задачи при y₁=30 дает оптимальное решение k₁=0, которое означает, что на 0 (нуль) вопросов 1-го типа будут даны ответы. Далее находим:

Соответственно оптимальным решением задачи является (0, 0, 4, 1, 0, 0, 5, 7), соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 46.

В таблице для первого этапа нам, по существу, необходимо получить оптимальное решение лишь для y₁=30, так как это последний этап, подлежащий рассмотрению. Однако в таблицу включены вычисления для y₁=0, 1, …, 30, которые позволяют провести анализ чувствительности решения.

Например, что произойдет, если время отводимое на контрольную работу будет 20, вместо 30?

соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 34. Что произойдет, если время отводимое на контрольную работу будет 5, вместо 30?

соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 10. Что произойдет, если типов вопросов будет 4, вместо 8?

соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 39.

В экономических исследованиях иногда приходится оптимизировать задачи по нескольким критериям. Например, одновременно учитывать минимум затрат и максимум прибыли, максимум прибыли и минимум риска, максимум выпуска продукции и максимум прибыли, минимальные затраты и минимальный риск и т.д. Рассмотрим многокритериальный метод оптимизации, предложенный итальянским экономистом Парето.

Оптимальность по Парето – такое состояние системы, при котором значение каждого частного критерия, описывающего состояние системы, не может быть улучшено без ухудшения положения других элементов. Таким образом, по словам самого Парето: «Всякое изменение, которое никому не приносит убытков, а некоторым людям приносит пользу (по их собственной оценке), является улучшением». Значит, признаётся право на все изменения, которые не приносят никому дополнительного вреда.

Множество состояний системы, оптимальных по Парето, называют «множеством Парето», «множеством альтернатив, оптимальных в смысле Парето», либо «множеством парето-оптимальных альтернатив». Ситуация, когда достигнута эффективность по Парето – это ситуация, когда все выгоды от обмена исчерпаны.

Приведенное выше определение можно формализовать следующим утверждением: состояние экономики S * считается лучшим по Парето, чем другое состояние S ₁, если хотя бы один экономический субъект предпочитает S *, а все остальные по меньшей мере не делают различий между этими состояниями, но в то же время нет таких, кто предпочитает S ₁ состоянию S *. Последнее безразлично по Парето относительно состояния S ₁, если все экономические субъекты не делают между ними различий; наконец, оно оптимально по Парето, если не существует такого допустимого состояния экономики, которое было бы лучше, чем это.

Критерий Парето неприменим к весьма распространенным ситуациям, при которых экономическое мероприятие, приносящее пользу одним, в то же время наносит ущерб другим. На рис. a) точкой А показано исходное состояние экономической системы, состоящей из двух подсистем (группы X и Y). Улучшают его лишь те решения, которые приводят систему в любую точку, лежащую в заштрихованной области и на ее границах (напр., точки B, C, D). Решение, обозначенное точкой E, не удовлетворяет требованию Парето, несмотря на значительный рост удовлетворения потребностей членов группировки Y: он достигается за счет снижения уровня благосостояния группировки X.

Если x ₁ и y ₁ (см. рис. б)) соответственно отображают максимальные значения целевых функций подсистем X и Y при их независимом друг от друга функционировании, то участок FF ₁ множества Парето (недостижимый для каждой из них в отдельности) заинтересовывает их в совместной деятельности. Этот участок называется ядром экономической системы. Чем теснее взаимозависимы подсистемы, тем меньше различия между множеством Парето (“оптимумом по Парето”) и ядром системы. Выбор при планировании единственного наилучшего плана (напр., точки g) — вопрос согласования или, как говорят, “устройства” экономического механизма. Напр., такой точкой может быть точка равновесия по Нэшу.

Таким образом, оптимумов по Парето может быть много, но существенно меньше, чем вообще вариантов развития системы; оптимумов по Парето, входящих в ядро, еще меньше, и все это, в частности, позволяет сужать выбор вариантов, подлежащих рассмотрению в процессе оптимального композиционного планирования. (Те же рассуждения применимы и к анализу некооперативных игр.)

Эффективность по Парето является одним из центральных понятий для современной экономической науки. На основе этого понятия строятся первая и вторая фундаментальные теоремы благосостояния. Одним из приложений Парето-оптимальности является т.н. Парето-распределение ресурсов (трудовых ресурсов и капитала) при международной экономической интеграции, то есть экономическом объединении двух и более государств. Интересно, что Парето-распределение до и после международной экономической интеграции было адекватно математически описано (Далимов Р. Т., 2008). Анализ показал, что добавленная стоимость секторов и доходы трудовых ресурсов движутся противонаправленно в соответствии с хорошо известным уравнением теплопроводности аналогично газу или жидкости в пространстве, что дает возможность применить методику анализа, используемую в физике, в отношении экономических задач по миграции экономических параметров.

Рис. Геометрическая интерпретация паретовых решений для задачи с двумя критериями.

Множество F называется множеством достижения или граничных возможностей. Множество Парето представляет собой часть границы множества достижимости, то есть к нему принадлежат те значения критериев, над которыми не доминируют другие варианты. В данном случае множеством Парето будет дуга АСВ. Существенным моментом здесь есть то, что решение полученное таким методом, не является однозначным. Лицо, принимающее решение, на свое усмотрение выбирает оптимальное решение из множества Парето (точку на дуге ABC). Но имеет место чрезвычайно важное утверждение.

Утверждение. На множестве Парето каждая из характеристик f₁ f₂ - однозначная функция другой. Другими словами, если две характеристики принадлежат множеству Парето, то по одной характеристике можно однозначно определить другую.

Постановка задачи оптимального управления.

Состояние объекта управления характеризуется n-мерной вектор функцией, например, функцией времени x = [ x ₁(t), x ₂(t), …, x _n(t)].

От управляющего органа к объекту управления поступает вектор-функция u = [ u ₁(t), u ₂(t), …, u_r (t)].

Векторы x и u, обычно связаны между собой каким-либо соотношением.

Наиболее развитым в настоящее время является уравнение, в котором векторы связаны системой обыкновенных дифференциальных уравнений.

Итак, пусть движение управляемого объекта описывается системой дифференциальных уравнений:

где x = (x ₁, …, x_n) - вектор координат объекта или фазовых координат, f = (f ₁, …, f_n) - заданная вектор-функция, u = (u ₁, …, u_r) - вектор управлений или просто управление.

В уравнении (1) векторы x, u являются функциями переменной t, обозначающей время, причем

t Î [ t ₀, T ], где [ t ₀, T ] - отрезок времени, на котором происходит управление системой.

На управление обычно накладывается условие:

где U (t) - заданное множество в Rⁿ при каждом t Î [ t ₀, T ].

Будем называть далее управлением кусочно-непрерывную на отрезке [ t ₀, T ] (т. е. имеющую конечное число разрывов первого рода) r -мерную вектор-функцию u, непрерывную справа в точках разрыва и непрерывную в точке T.

Управление u называется допустимым, если оно удовлетворяет ограничению (2). Заметим, что ограничиться рассмотрением непрерывных управлений оказывается невозможным, так как с их помощью трудно моделировать моменты переключения управления такие, как, например, включение и отключение двигателей, отделение ступеней ракеты, поворот рулей и т. д. Иногда рассматривают и более широкие классы допустимых управлений, например, класс всех ограниченных измеримых управлений, удовлетворяющих условию (2).

Покажем, как при произвольном начальном положении x ₀ Î Rⁿ и допустимом управлении u определяется траектория управляемого объекта.

Поскольку при разрывных правых частях классическое понятие решения системы дифференциальных уравнений неприменимо, поясним, что понимается в данном случае под решением задачи (3).

Пусть функция u имеет скачки в точках r ₁, r ₂, …, r_k причем t ₀< r ₁< r ₂< … < r_k < T.

Предположим, что задача (3) имеет решение х, определенное на всем отрезке [ t ₀, r ₁], причем x (r ₁) = x ₁.

Предполагая, что она имеет решение на отрезке [ r ₁, r ₂] и x(r₂) = x₂, приходим к задаче:

Если функцию x удалось определить указанным способом на всем отрезке [ t ₀, Т ], то будем называть ее решением задачи (3) или фазовой траекторией (иногда просто траекторией), соответствующей управлению u.

Отметим, что x - непрерывная по построению функция, удовлетворяющая на отрезке [ t ₀, T ] равенству:

При выполнении определенных условий на f решение задачи (3), соответствующее управлению u, существует и единственно при произвольном начальном положении x ₀ и произвольном допустимом управлении u.

Помимо ограничения на управление могут существовать ограничения и на фазовые координаты:

Ограничения на концах траектории целесообразно рассматривать отдельно:

здесь S₀(t₀), S(T) - заданные множества из R; q₀, q - заданные множества из R, причем infq ₀ < supq, t ₀ < T.

Таким образом, начальный и конечный моменты времени не обязательно фиксированы.

Случаю фиксированных t ₀, Т соответствуют множества q ₀, q, состоящие из одной точки; при этом говорят, что рассматривается задача с закрепленным временем.

Если S ₀(t ₀) = { x ₀} при любом t ₀Î q ₀₀, то левый конец траектории называют закрепленным.

Если же S ₀(t ₀) = R при всех t ₀Î q ₀₀, то левый конец траектории называют свободным.

Во всех остальных случаях левый конец называют подвижным.

В аналогичных ситуациях говорят о закрепленном, свободном или подвижном правом конце траектории.

Цель управления в задаче оптимального управления состоит в минимизации некоторого функционала на множестве допустимых наборов.

Если каждой функции y = f(x) определенного класса ставится в соответствии по некоторому закону определенное числовое значение переменной I, то эту переменную называют функционалом от одной функциональной переменной I = I[y] = I[y(x)] = I[f(x)].

Наиболее часто под задачами управления понимаются задачи, в которых роль функционала выполняет интегральный функционал:

Мы будем рассматривать задачу с целевым функционалом:

представляющим собой сумму интегрального функционала

Ее частными случаями являются задача с интегральным функционалом, называемая задачей Лагранжа, и задача с терминальным функционалом, называемая задачей Майера.

Задача с интегральным функционалом при f ₀ º 1называется задачей оптимального быстродействия.

Набор (t ₀, Т, х ₀, u, х), минимизирующий функционал (6), называется решением задачи оптимального управления, управление u - оптимальным управлением, а траектория х - оптимальной траекторией.

Часто решением задачи оптимального управления называют пару (u, х).

Принцип максимума Понтрягина - необходимое условие оптимальности в таких задачах.

Рассмотрим задачу оптимального управления, являющуюся частным случаем задачи, сформулированной выше:

x¢ (t) = f(x(t), u(t), t), x(t ₀ ) Î S ₀, x(T) Î S_T, u(t) Î U, t ₀ £ t £ T, где

При этом предполагается, что моменты t ₀, Т фиксированы, т. е. рассматривается задача с закрепленным временем; множество U не зависит от времени, фазовые ограничения отсутствуют. Положим: H(x, u, t, Y ₀, Y) =

, где Y ₀ - константа, Y(t) = (j ₁ (t), …, j_n(t))

Система линейных дифференциальных уравнений Y¢ = -Н_x¢ относительно переменных (j ₁ (t), …, j_n(t)) называется сопряженной системой, соответствующей управлению uи траектории x.

В более подробной покоординатной записи сопряженная система принимает вид:

Система (3) имеет при любых начальных условиях единственное решение Y, определенное и непрерывное на всем отрезке [t ₀, T].

Следующая теорема выражает необходимые условия оптимальности в задаче (7).

Пусть функции f ₀, …, f_n, u, f, g ₁ ,..., g_m имеют частные производные по переменным х ₁ ,..., x_n и непрерывны вместе с этими производными по совокупности аргументов х Î Rⁿ, u Î U, t Î [t ₀, Т]. Предположим, что (u, х) - решение задачи (7). Тогда существует решение Y сопряженной системы (9), соответствующей управлению u и траектории х, и константа Y ₀£ 0 такие, что | Y ₀| + || Y(t) || при t Î [ t ₀, Т ], и выполняются следующие условия:

а) (условие максимума) при каждом t Î [t ₀, Т] функция Гамильтона H(x, u, t, Y ₀, Y), достигает максимума по v Î U при v = u(t), т.е.

б) (условие трансверсальности на левом конце траектории) существуют числа l ₁, …, l_m ₀, такие, что

в) (условие трансверсальности на правом конце траектории) существуют числа l_m ₀₊₁, …, l_m такие, что:

Центральным в теореме является условие максимума (10).

Если отказаться от предположения о том, что конечный момент времени Т фиксирован, то теорема останется справедливой за исключением условия трансверсальности на правом конце траектории. Условие (12) заменим условием:

и добавить еще одно условие трансверсальности на правом конце траектории:

1. Простейшая задача оптимального быстродействия.

Пусть точка движется по прямой в соответствии с законом:

где х - координата. Требуется найти управление u, переводящее точку из начального положения в начало координат за минимальное время Т (задача оптимального быстродействия). При этом скорость точки в конце траектории должна быть нулевой, а управление - удовлетворять условию:

Применим к сформулированной задаче принцип максимума Понтрягина. Введем фазовые переменные x ₁ = x, x ₂ = x ¢. Тогда движение управляемого объекта описывается системой двух дифференциальных уравнений первого порядка:

при t₀=0 и конечное положение (0, 0) фиксированы, а конечный момент времени Т не фиксирован.

В обозначениях приведенных выше в данной задаче U = [-1, 1], f₀=1, Ф=0, а функция Гамильтона имеет вид:

Очевидно, что максимум функции Н по uÎ U достигается при:

Таким образом, оптимальное управление uможет принимать лишь два значения + 1.

2. Определить управление u(t), которое дает минимум интегралу:

Для этой переменной имеем дифференциальное уравнение:

с начальными условиями, получаемыми из (2), т.е. х₂(0)=0. Минимизирующий функционал, используя (2), можно записать в виде I[T]=x₂(T).

По принципу максимума функция Н при фиксированных х₁ и Y₁ достигает максимума по u:

, откуда Y₁(t) = u(t).

Осталось решить систему уравнений (2) и (3) при условии Y₁(t) = u(t), Y₂(Т)=-1,

Сведем данную систему к одному уравнению относительно u.

Добавим к этому уравнению граничные условия u(T)=0, u(T) = u₀ и решим его. Составим характеристическое уравнение k²- (а²+1)=0, k_{1, 2}=±

= ±l, u = C₁e^l^t + C₂e^-^l^t

Найдем С₁ и С₂. C₁e^l^t + C₂e^-^l^t = 0, С₂=-C₁е²^l^t. Тогда u(t) = C₁(e^l^t - e^l⁽²^T^-^t⁾)

Таким образом, определено оптимальное решение

Тема 10. Особенности решения задач динамического программирования. Примеры.

Связь динамического программирования и регулярных выражений.

Чтобы понять, что такое динамика по профилю, будем рассматривать разные задачи и разбирать их решения с помощью этого приема. Для начала рассмотрим известную задачу: дана таблица n × m, нужно найти количество способов полностью замостить ее неперекрывающимися костяшками домино (прямоугольниками 2× 1 и 1× 2). Считаем n, m £ 10.

Заметим, что в процессе замощения каждая клетка таблицы будет иметь одно из двух состояний: покрыта какой-нибудь домино или нет. Чтобы запомнить состояние клеток одного столбца, достаточно одной переменной P типа integer. Положим i -й бит P равным 1, если i -я сверху клетка данного столбца занята, 0 – если свободна. Будем говорить в таком случае, что P – битовая карта нашего столбца. Теперь дадим определение базовой линии и профиля.

Базовой линией будем называть вертикальную прямую, проходящую через узлы таблицы. Можно занумеровать все базовые линии, по порядку слева направо, начиная с нуля. Таким образом, базовая линия с номером i – это прямая, отсекающая первые i столбцов от всех остальных (если такие имеются). Отныне через b _i будем обозначать базовую линию с номером i. Столбцы занумеруем так: слева от b _i будет столбец с номером i. Другими словами, столбец с номером i находится между b _{i - 1} и b _i.

Профилем для базовой линии с номером i (b _i) будем называть битовую карту для столбца с номером i при следующих дополнительных условиях:

3)считается, что справа от b _i нет покрытых клеток.

Первое условие возникает от желания считать количество способов постепенно, сначала рассматривая первый столбец, потом второй при условии, что первый уже заполнили и т.д. Второе и третье вводятся для того, чтобы один и тот же способ покрытия не был посчитан более одного раза. Точный смысл этих условий будет раскрыт ниже.

Для каждого профиля p ₁ базовой линии b _i определим множество профилей p ₂ базовой линии b _{i + 1}, которые могут быть из него получены. На таблицу, соответствующую p ₁ (то есть все клетки слева от b _{i - 1} полностью покрыты, в i -м столбце клетки отмечены согласно p ₁), можно класть домино только двух типов:

1)горизонтальные домино, которые пересекают b _i (то есть делятся ей пополам);

2)вертикальные домино, которые лежат слева от b _i.

Также должны быть выполнены естественные дополнительные условия:

1)новые домино не должны перекрываться друг с другом;

2)они должны покрывать только незанятые клетки;

3)каждая клетка i -го столбца должна быть покрыта.

Битовая карта столбца i + 1 и будет возможным профилем p ₂.

Очевидно, что полученный таким образом профиль p ₂ действительно удовлетворяет всем условиям, накладываемым на профиль.

Пусть d [ p ₁, p ₂] - количество способов из профиля p ₁ (для b _i) получить p ₂ (для b _{i + 1}). Очевидно, для данной задачи про домино это число может быть только единицей или нулем. Различные задачи будут отличаться в основном только значениями d [ p ₁, p ₂].

Заметим, что всего профилей 2ⁿ: от 00...0₂ = 0 до 11...1₂ = 2ⁿ - 1. Поэтому в данном случае матрица D будет иметь размер 2ⁿ× 2ⁿ. Пусть теперь a [ i, p ] – количество способов таким образом расположить домино, что p – профиль для b _i (таким образом, все клетки левее b _{i - 1} покрыты). Напишем рекуррентное соотношение.

· Начальные значения (i = 1):
a [1, 0] = 1;
a [1, p ₂] = 0, p ₂ = 1,..., 2ⁿ - 1

Заметим, что для базовой линии номер 1 существует единственный профиль (то есть битовая карта, удовлетворяющая условиям профиля) – карта незаполненного столбца.

Ответ на вопрос задачи будет записан в a [ m + 1, 0]. Ошибкой бы было считать правильным ответом число a [ m, 2ⁿ - 1], так как в этом случае не учитывается возможность класть вертикальные домино в последнем столбце (см. второй пример).

Обсудим " странные" условия на домино при получении одного профиля из другого. Казалось бы, забыт еще один тип домино, которые могут участвовать при формировании нового профиля, а именно полностью лежащие в столбце i + 1. Дело в том, что если разрешить их, то некоторые способы замощения будут считаться более одного раза. Например, пусть n = 2, m = 2. Тогда d' [0][3] = 2, так как можно положить либо две вертикальные домино, либо две горизонтальные. Аналогично, d' [3][3] = 1 (можно положить одну вертикальную). В итоге

Имеем неправильный ответ 3 (можно посчитать вручную, что на самом деле ответ 2).

Напротив, если следовать данному правилу получения из одного профиля другого, то можно убедиться в верности вычислений.

Упражнение. Доказать, что a[i, p] вычисляется правильно.

Таким образом, замостить домино таблицу 2× 4 можно 5 способами, а таблицу 2× 2 – двумя. Если смотреть a [ m, 2ⁿ - 1], то получим 2 и 1. Очевидно, что таблицу 2× 2 можно замостить двумя, а не одним способом: пропущен вариант, когда кладутся две вертикальные домино. В случае 2× 4 пропущены три замощения – все случаи, когда последний столбец покрыт вертикальной домино.

Существует два способа для вычисления D. Первый заключается в том, чтобы для каждой пары профилей p ₁ и p ₂ проверять, можно ли из p ₁ получить p ₂ описанным способом.

При втором способе для каждого профиля p ₁ пытаемся его замостить, кладя при этом только домино разрешенных двух типов. Для всех профилей p ₂ (и только для них), которые при этом получались в следующем столбце, положим d [ p 1, p 2]=1. В большинстве случаев этот способ более экономичный, так что логично использовать именно его.

Ниже приведен код рекурсивной процедуры, которая заполняет строку d [ p ], то есть находит все профили, которые можно получить из p:

if (len = n) then begin // как только profile получился длины n, выходим

if (bit(p, len) = 0) then begin // текущая ячейка в p (с номером len + 1) не занята

go(p, profile + (1 shl len), len + 1); // положили горизонтальную домино

if (bit(p, len + 1) = 0) then begin // не занята еще и следующая ячейка

go(p, profile, len + 2); // положили вертикальную домино

go(p, profile, len + 1); // текущая ячейка занята, ничего положить не можем

go(p, 0, 0); // запускать надо именно с такими параметрами

Алгоритм вычисления D и A работает за O (2²ⁿ) (вычисление D) + O (2²ⁿ m) (вычисление A) = O (2²ⁿ m).

Рассмотрим еще одну задачу с прямоугольной таблицей. Дана таблица n × m, каждая клетка которой может быть окрашена в один из двух цветов: белый или черный. Симпатичным узором называется такая раскраска, при которой не существует квадрата 2× 2, в котором все клетки одного цвета. Даны n и m. Требуется найти количество симпатичных узоров для соответствующей таблицы.

Будем считать профилем для b _i битовую карту i -го столбца (единицей будет кодировать черную клетку, а нулем -- белую). При этом узор, заключенный между нулевой и i -й базовыми линиями, является симпатичным. Из профиля p₁ для b_i можно получить p₂ для b_{i + 1}, если и только если можно так закрасить (i + 1)-й столбец, что его битовая карта будет соответствовать p₂, и между b_{i - 1} и b_{i + 1} не будет полностью черных либо белых квадратиков 2× 2.

Сколькими же способами из одного профиля можно получить другой? Понятно, что закрасить нужным образом либо можно, либо нельзя (так как раскрашивать можно единственным образом -- так, как закодировано в p ₂). Таким образом, d [ p ₁, p ₂] Î {0, 1}.

Вычислять D можно либо проверяя на " совместимость" (то есть наличие одноцветных квадратов 2× 2) все пары профилей, либо генерируя все допустимые профили для данного. Ниже приведен код, реализующий первую идею:

После того, как вычислена матрица D, остается просто применить формулу (так как рассуждения на этом этапе не изменяются). Связь ДП по профилю и линейной алгебры. Рекуррентное соотношениебудет встречаться нам не только в задаче о замощении или симпатичном узоре, но и во многих других задачах, решаемых динамикой по профилю. Поэтому логично, что существует несколько способов вычисления A, используя уже вычисленную D. В этом пункте мы рассмотрим способ, основанный на возведении в степень матрицы:

a [ i ] = a [ i - 1] D. Если расписать эту формулу по определению произведения, то получится в точности. Следуя определению степени матрицы, получаем

Вспомним, как возвести действительное число a в натуральную степень b за O (log b). Представим b в двоичной системе счисления: b = 2ⁱ₁ + 2ⁱ₂ +...+ 2ⁱ_k, где i ₁ < i ₂ <...< i _k. Тогда k = O (log b). Заметим, что a ²ⁱ получается из a ^{2(i - 1)} возведением последнего в квадрат. Таким образом, за O (k) можно вычислить все a ^p_t, p _t = 2ⁱ_t, t = 1,..., k. Перемножить их за линейное время тоже не представляет труда.

Логично предположить, что аналогичный алгоритм сгодится и для квадратных матриц. Единственное нетривиальное утверждение – A ²ⁱ = (A ^{2i - 1})², ведь по определению

, а мы хотим приравнять его к (A ^t)(A ^t). Его истинность следует из ассоциативности умножения матриц (AB) C = A (BC). Само свойство можно доказать непосредственно, раскрыв скобки в обеих частях равенства. Приведем код процедуры возведения в степень (функция mul перемножает две квадратные матрицы размера w × w):

Как уже говорилось, будет сделано O (log b) перемножений. В данном случае, на каждое перемножение тратится n ³ операций (где n – размерность матрицы). Так что этот алгоритм будет работать за O (n ³log b).Матрицу D мы умеем вычислять за O ((2ⁿ)² n) = O (4ⁿ n) (как в рассмотренных задачах). Вектор a [ m ] сумеем найти за O ((2ⁿ)³log b) = O (8ⁿlog m). В итоге получаем асимптотику O (8ⁿlog m). При больших m (например, 10¹⁰⁰) этот способ вычисления A несравнимо лучше наивного.

Связь динамического программирования и регулярных выражений

Шаблоном называется строка состоящая из букв латинского алфавита (a, …, z, A, …, Z) и символов? и *. Каждый из символов? разрешается заменить на одну произвольную букву, а каждый из символов * на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблонов такими заменами, будем говорить, что она удовлетворяет данному шаблону. Тогда задачу состоит в том, чтобы для двух заданных шаблонов найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выяснить, что такой строки не существует.

Нельзя не отметить, что подобного рода задачи, находят большое применение на практике, обычно они возникают при анализе и разборе регулярных выражений. Итак, пусть заданы два шаблона, S [1… M ] и T [1… N ]. Введем обозначение F (i, j) для строки минимальной длины, которая удовлетворяет шаблонам S [1… i ] и T [1… j ]. Если такой строки нет, то в F (i, j), будет стоять специальная пометка, говорящая об этом.

Вычисляем значение F (i, j) в порядке возрастания i, а при равных i, в порядке возрастания j. Возможны следующие содержательные ситуации (считаем, что i, j > 0, а разбор граничных случаев, не представляет особого интереса, и может быть оставлен как упражнение).

1. S [ i ] и T [j] – буквы. Если они совпадают, то в качестве значения F (i, j) берем F (i − 1, j − 1) с добавленной в конце этой буквой. Если в F (i − 1, j − 1) стоит пометка, говорящая о том, что строки не существует, то аналогичную пометку можно поставить и в F (i, j). В случае несовпадения букв S [ i ] и T [ j ], в F (i, j) необходимая строка также не существует.

2. S [ i ] и T [ j ] – буква и символ «?» или два символа «?». Поступаем точно так же, как и в предыдущей ситуации, однако случае несовпадения букв из-за наличия «?» здесь быть не может.

3. S [ i ] – символ «*», а T [ j ] – буква или символ «?». В данной ситуации выбираем наиболее короткое среди значений F (i, j − 1) и F (i − 1, j) с дописанной к нему буквой T [ j ] (или любой буквой, если T [ j ] есть символ «?»).

4. S [ i ] – буква или символ «?», а T [ j ] – символ «*». Поступаем аналогично разобранному выше пункту.

5. S [ i ] и T [ j ] – два символа «*». В этом случае в качестве F (i, j), берем наиболее короткое из значений F (i, j − 1) и F (i − 1, j).

В качестве еще одного примера динамического программирования рассмотрим задачу триангуляции многоугольника. Заданы вершины многоугольника и расстояния между каждой парой вершин. Это расстояние может быть геометрическим расстоянием на плоскости или произвольной функцией стоимости, заданной в виде таблицы. Задача заключается в том, чтобы выбрать такую совокупность хорд (линий между несмежными вершинами), что никакие две хорды не будут пересекаться, а весь многоугольник будет поделен на треугольники. Общая длин всех хорд должна быть минимальной. Такая совокупность хорд называется минимальной триангуляцией. Зафиксируем несколько фактов, которые помогут разработать необходимый алгоритм. Предполагаем, что наш многоугольник имеет n вершин v ₀, v ₁, …, v_n _{− 1}, перечисленных по часовой стрелке.

1. В случае триангуляции любого многоугольника, содержащего более трех вершин, с каждой парой смежных вершин связана, по крайней мере одна хорда. Чтобы убедиться в этом, предположим, что ни v_i, ни v_i ₊₁ не связаны ни с одной из хорд. В таком случае область, ограничиваемая стороной (v_i, v_i ₊₁), должна бы включать стороны (v_i _{− 1}, v_i), (v_i ₊₁, v_i ₊₂) и по крайней мере еще одну дополнительную сторону или хорду. Но в таком случае это область не была бы треугольником.

2. Если (v_i, v_j) является хордой в триангуляции, значит должна найтись, такая вершина v_k что каждая из линий (v_i, v_k) и (v_k, v_i) либо стороной многоугольника либо хордой. В противном случае хорда (v_i, v_j), ограничивала бы область, не являющуюся треугольником.

Чтобы приступить к поиску минимальной триангуляции, выберем две смежные вершины, например v ₀ и v ₁. Из указанных выше фактов следует, что в любой триангуляции (а значит и в минимальной) должна найтись такая вершина v_k, что (v ₁, v_k) и (v_k, v ₀) являются хордами или сторонами многоугольника. Необходимо рассмотреть, насколько приемлемую триангуляцию можно построить после выбора каждого значения k. Если в многоугольнике n вершин, то в нашем распоряжении имеется (n − 2) возможных вариантов. Каждый вариант выбора k приводит к не более чем двум подзадачам, где мы имеем многоугольники образованные, одной хордой и сторонами исходного многоугольника. Например, могут возникнуть такие подзадачи при случае выбора вершины v ₃.

Далее нужно найти минимальную триангуляцию для многоугольников, полученных в результате появления новых подзадач. Правда, если мы будем решать все подзадачи, которые будут появляться, то мы получим алгоритм с экспоненциальной трудоемкостью. Но, имея треугольник, включающий хорду (v ₀, v_k), нам никогда не придется рассматривать многоугольники, у которых более одной стороны являются хордами исходного многоугольника. «Факт 2» говорит о том, что при минимальной триангуляции хорда в подзадаче (например, хорда (v ₀, v ₃) на рис. 1) должна составлять треугольник с одной из остальных вершин многоугольника.

Определим подзадачу размера s, начинающуюся с вершины v_i и обозначаемую S_is, как задачу минимальной триангуляции для многоугольника, образованного s вершинами, начинающегося с вершины v_i и содержащего вершины v_i, v_i ₊₁, …, v_i _{+ s − 1}, перечисляемые в порядке обхода вершин по часовой стрелке. В v ₀ хордой является замыкающая сторона (v_i, v_i _{+ s − 1}). Чтобы решить подзадачу S_is необходимо рассмотреть три варианта:

1. Можно выбрать вершину v_i _{+ s − 2}, чтобы составить треугольник с хордами (v_i, v_i _{+ s − 1}), (v_i, v_i _{+ s − 2}) и третьей стороной (v_i _{+ s − 2}, v_i _{+ s − 1}), а затем решить подзадачу S_i _{, s − 1}.

2. Мы можем выбрать вершину v_i ₊₁, чтобы составить треугольник с хордами (v_i, v_i _{+ s − 1}), (v_i ₊₁, v_i _{+ s − 1}) и третьей стороной (v_i, v_i ₊₁), а затем решить подзадачу S_i _{+1, s − 1}.

3. Для некоторого k из диапазона от 2 до s − 3 можно выбрать вершину v_i _{+ k} и образовать треугольник со сторонами (v_i, v_i _{+ k}), (v_i _{+ k}, v_i _{+ s − 1}), (v_i, v_i _{+ s − 1}), а затем решить подзадачи S_i _{, k +1} и S_i _{+ k, s − k}.

Если учесть, что решение подзадачи размером не более трех не требует вообще никаких действий, то рассматривая описанные варианты 1–3, следует предпочесть вариант 3, где нужно выбрать некоторое k из диапазона от 1 до s − 2 и решить подзадачи S_i _{, k +1} S_i _{+ k, s − k}. Если для решения задачи размером более четыре и более воспользоваться очевидным рекурсивным алгоритмом, непосредственно вытекающим из перечисленных выше вариантов, то можно показать что общее число рекурсивных вызовов составляет 3 ^s ^{− 4}, если подсчитать лишь обращения к подзадачам размером четыре и более. Таким образом количество подзадач, которые необходимо решить, возрастает по экспоненциальному закону в зависимости от s. А следовательно общее количество шагов экспоненциально зависит и от n.

Но известно, что, помимо исходной задачи существует лишь n (n − 4) различных подзадач, которые в любом случае необходимо решить. Значит в приведенном анализе что-то явно не совсем верно. Очевидно, что совсем не все подзадачи отличаются между собой, если действовать рекурсивно, как приведено выше, то у нас возникают ситуации, когда одни и те же ситуации приходится решать несколько раз. Именно это подсказывает нам эффективный способ вычисления триангуляции. Прежде всего, вычисления удобно организовать в виде таблицы. Назначим стоимость C_is триангуляции S_is для всех i и s. Поскольку решение любой данной задачи зависит от решения задач меньшего размера, то логичным порядком заполнения такой таблицы является порядок, основанный на размерах подзадач, т. е. для размеров s = 4, 5, …, n − 1 мы указываем минимальную стоимость задач S_is для всех вершин i. Удобно включить и задачи размеров 0 ≤ s < 4, но при этом нужно помнить, что S_is имеет стоимость 0, если s < 4.

В соответствии с перечисленными выше вариантами действий 1–3 при определении подзадач формула вычисления C_is при s ≥ 4 должна иметь следующий вид:

C_is = min_{1≤ k ≤ s − 2} { C_i _{, k +1} + C_i _{+ k, s − k} + D (v_i, v_i _{+ k}) + D (v_i _{+ k}, v_i _{+ s − 1})},

где D (v_p, v_q) – это длина хорды между вершинами v_p и v_q, если v_p и v_q не являются смежными вершинами многоугольника; D (v_p, v_q) равняется 0, если являются смежными вершинами.

Отметим, что таким образом, мы вычислим всю таблицу, и определим стоимость минимальной триангуляции, но не саму триангуляцию. Поэтому, как и в задаче про наибольшую общую подпоследовательность для того, чтобы найти саму триангуляцию, мы должны еще также хранить информацию, о том, при каком значении k достигается минимум. И потом уже, по всем сохраненным значениям k мы можем легко восстановить минимальную триангуляцию.

Формальная запись решения задачи оптимизации произведения матриц

Обозначим через m[i, j] минимальную стоимость вычисления матрицы Ai..j. Элементарным случаем тогда будет i=j, т.е. Аi..j=Ai и умножения вообще не нужны, следовательно стоимость равна 0.

В этом равенстве подразумевается, что лучшее значение k нам известно. В действительности его еще нужно найти. Тут единственным вариантом является перебор всех значений k в промежутке от i до j-1. Т.е. окончательно получаем:

Тема 11. Применение метода динамического программирования к задачам синтеза расписаний обслуживания.

Задачи обслуживания множеств заявок. Однопроцессорные задачи синтеза расписаний обслуживания конечных детерминированных потоков заявок. Задачи синтеза расписаний обслуживания для систем с параллельными и последовательными процессорами. Задачи оптимального обслуживания стационарных объектов, расположенных в одномерной зоне.

В данном разделе изучается ряд задач синтеза расписаний обслуживания; обслуживанию подлежат объекты, условно именуемые заявками. Излагаемые алгоритмы основаны, главным образом, на принципе динамического программирования. В каждой задаче предполагается, что выполнение искомого расписания начинается от момента t = 0. Время считается дискретным, все временные характеристики заявок целочисленные. Рассматриваемые задачи делятся на две группы. В задачах первой группы считается, что по состоянию на момент времени t = 0 все заявки готовы к обслуживанию. В задачах второй группы считается, что по состоянию на момент t = 0 в систему обслуживания поступила лишь часть заявок, для каждой из остальных заявок известен момент ее прибытия (любая заявка, начиная с момента прибытия, полагается готовой к обслуживанию). Задачи первой группы будем называть задачами обслуживания множеств заявок, задачи второй группы – задачами обслуживания потоков заявок.