Применение метода динамического программирования в различных задачах

Размещено на http://www.allbest.ru/

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИФГБОУ ВПО «УДМУРТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КАФЕДРА ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ И ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ

КУРСОВАЯ РАБОТА

Применение метода динамического программирования в различных задачах

Выполнил: Николаев Д.П.

Научный руководитель: Коган Ю.В.

ИЖЕВСК 2015

Содержание

Введение

Глава 1. Обзор задач решаемых методом динамического программирования

1.1 Составление маршрута оптимальной длины

1.2 Перемножение цепочки матриц

1.3 Задача " Лестницы"

1.4 Алгоритм Нудельмана-Вунша

1.5 Задача о сдаче

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

2.1 Некоторые обозначения и определения

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

Заключение

Литература

Приложения



Введение

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

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



Глава 1. Обзор задач решаемых методом динамического программирования

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

1.1 Составления маршрута оптимальной длины

В качестве примера можно рассмотреть для начала одну простенькую задачу про составление маршрутов. Задача очень простая, и в то же время очень полезная для каждого человека. Задача формулируется следующим образом: есть некая карта дорог, которую можно изобразить в виде графа, и наша цель добраться из пункта А в пункт Б. Нужно выбрать путь с минимальным расстоянием, и придерживаясь которого будет истрачено минимальное количество топлива. Для нахождения кратчайшего пути необходимо принять решения. Куда повернуть на каждом перекрестке. Целевой функцией является минимизировать расстояние и затраты на топливо. Есть переменные выбора: для каждого перекрестка нужно решить куда ехать. Задачи такого типа называются задачами оптимизации. Целью таких задач является выбор самого оптимального варианта из всех возможных.



1.2 Перемножение цепочки матриц

Следующий пример динамического программирования - алгоритм позволяющий решить задачу о перемножении цепочки матриц. Постановка задачи такова: пусть имеется последовательность, состоящая из n матриц, и нужно вычислить их произведение A1A2…An.

Этот выражение можно вычислить, используя в качестве подпрограммы стандартный алгоритм перемножения пар матриц. Но для этого сначала необходимо расставить скобки, чтобы все неоднозначности в порядке перемножения. Порядок произведения матриц полностью определен скобками, если произведение является либо отдельной матрицей, либо взятым в скобки произведением двух последовательностей матриц, в котором порядок перемножения полностью определен скобками. Матричное умножение обладает свойством ассоциативности, поэтому результат не зависит от расстановки скобок. Например, если задана последовательность матриц (A1,A2,A3,A4), то способ вычисления их произведения можно полностью определить с помощью скобок пятью различными способами:

(А1(А2(А3 А4))),

(А1((А2 А3)А4)),

((А1 А2)(А3 А4)),

((А1(А2А3))А4) ,

От того как расставлены скобки при перемножении последовательности матриц, может сильно зависеть время, затраченное на вычисление произведения. Сначала рассмотрим, как определить стоимость произведения двух матриц. Ниже приводится псевдокод стандартного алгоритма. Атрибуты rows и columns означают количество строк и столбцов матрицы.



Matrix_Multiply(А, В)

if columns[A] ? rows[B]

then error "Несовместимые размеры"

else for i < 1 to rows[A]

do for j < 1 to columns[B]

do C[i,j] < 0

for k < 1 to columns[A]

do C[i,j] < C[i,j] + A[i, k] * B[k,j]

return С

Матрицы А и В можно перемножать, только если они совместимы: количество столбцов матрицы А должно совпадать с количеством строк матрицы В. Если А -- это матрица размера р * q, а В -- матрица размера q * r, то в результате их перемножения получится матрица С размера р * г. Время вычисления матрицы С преимущественно определяется количеством произведений скаляров, которое выполняется в строке 7. Это количество равно pqr. Итак, стоимость умножения матриц будет выражаться в количестве умножений скалярных величин.

Чтобы проиллюстрировать, как расстановка скобок при перемножении нескольких матриц влияет на количество выполняемых операций, рассмотрим пример, в котором перемножаются три матрицы (A1,A2,A3). Предположим, что размеры этих матриц равны 10 * 100, 100 * 5 и 5 * 50 соответственно. Перемножая матрицы в порядке, заданном выражением ((A1A2)A3), необходимо выполнить 10 *100 * 5 = 5 000 скалярных умножений, чтобы найти результат произведения A1A2 (при этом получится матрица размером 10 * 5), а затем -- еще 10 * 5 * 50 = 2 500 скалярных умножений, чтобы умножить эту матрицу на матрицу А3. Всего получается 7 500 скалярных умножений. Если вычислять результат в порядке, заданном выражением (А1 (А2А3)), то сначала понадобится выполнить 100 * 5 * 50 = 25 000 скалярных умножений (при этом будет найдена матрица А2 А3 размером 100 * 50), а затем еще 10 * 100 * 50 = 50 000 скалярных умножений, чтобы умножить А1на эту матрицу. Всего получается 75 000 скалярных умножений. Таким образом, для вычисления результата первым способом понадобится в 10 раз меньше времени.

Задачу о перемножении последовательности матриц (matrix-chain multiplication problem) можно сформулировать так: для заданной последовательности матриц (A1,A2,..., An), в которой матрица Ai, i = 1,2,... , n имеет размер pi-1 * pi, с помощью скобок следует полностью определить порядок умножений в матричном произведении A1A2...An, при котором количество скалярных умножений сведется к минимуму.

Обратите внимание, что само перемножение матриц в задачу не входит. Наша цель -- определить оптимальный порядок перемножения. Обычно время, затраченное на нахождение оптимального способа перемножения матриц, с лихвой окупается, когда выполняется само перемножение (как это было в рассмотренном примере, когда удалось обойтись всего 7 500 скалярными умножениями вместо 75 000).

Первый этап: структура оптимальной расстановки скобок

Первый этап применения парадигмы динамического программирования -найти оптимальную вспомогательную подструктуру, а затем с ее помощью сконструировать оптимальное решение задачи по оптимальным решениям вспомогательных задач. Оптимальная вспомогательная подструктура для данной задачи. Предположим, что в результате оптимальной расстановки скобок последовательность AiAi+1...Aj разбивается на подпоследовательности между матрицами Ak и Ak+1.Тогда расстановка скобок в "префиксной" подпоследовательности AiAi+1...Ak тоже должна быть оптимальной. Потому что если бы существовал более экономный способ расстановки скобок в последовательности АiAi+1... Аj, то его применение позволило бы перемножить матрицы АiAi+1... Аj еще эффективнее, что противоречит предположению об оптимальности первоначальной расстановки скобок. Аналогично можно прийти к выводу, что расстановка скобок в подпоследовательности матриц Ak+1Ak+1...Aj, возникающей в результате оптимальной расстановки скобок в последовательности АiAi+1... Аj, также должна быть оптимальной.

Теперь с помощью нашей оптимальной вспомогательной подструктуры покажем, что оптимальное решение задачи можно составить из оптимальных решений вспомогательных задач. Мы уже убедились, что для решения любой нетривиальной задачи об оптимальном произведении последовательности матриц всю последовательность необходимо разбить на подпоследовательности и что каждое оптимальное решение содержит в себе оптимальные решения подзадач. Другими словами, решение полной задачи об оптимальном перемножении последовательности матриц можно построить путем разбиения этой задачи на две подзадачи -- оптимальную расстановку скобок в подпоследовательностях AiAi+1...Ak и Ak+1Ak+2...Aj. После этого находятся оптимальные решения подзадач, из которых затем составляется оптимальное решение полной задачи. Необходимо убедиться, что при поиске способа перемножения матриц учитываются все возможные разбиения -- только в этом случае можно быть уверенным, что найденное решение будет глобально оптимальным.

Второй этап: рекурсивное решение

Далее, рекурсивно определим стоимость оптимального решения в терминах оптимальных решений вспомогательных задач. В задаче о перемножении последовательности матриц в качестве вспомогательной задачи выбирается задача об оптимальной расстановке скобок в подпоследовательности Ai Ai+i...Aj при 1 ? i ? j ? n. Путь m[i, j] -- минимальное количество скалярных умножений, необходимых для вычисления матрицы Ai..j. Тогда в полной задаче минимальная стоимость матрицы А1..n равна m[1, n].

Рекурсивное определение величины m [i, j] происходит следующим образом. Если i = j, то задача становится тривиальной: последовательность состоит всего из одной матрицы Ai..j = Aj, и для вычисления произведения матриц не нужно выполнять никаких скалярных умножений. Таким образом, при i = 1,2, ...,n m [i, i] = 0. Чтобы вычислить m[i, j] при i < j, воспользуемся свойством подструктуры оптимального решения, исследованным на первом этапе. Предположим, что в результате оптимальной расстановки скобок последовательность Ai Ai+i...Aj разбивается между матрицами Ak и Ak+1, где i ? k < j.

Тогда величина m [i, j] равна минимальной стоимости вычисления частных произведений Ai..k и Ak+1..j плюс стоимость умножения этих матриц друг на друга.

Если вспомнить, что каждая матрица Аi имеет размеры pi-1* pi, то нетрудно понять, что для вычисления произведения матриц Ai..kAk+1..j понадобится pi-1pkpj скалярных умножений. Таким образом, получаем:

m [i, j] = m [i, к] + m [к + i, j] + pi-1pkpj.

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

Таким образом, рекурсивное определение оптимальной расстановки скобок в произведении Ai Ai+1...Aj принимает вид:

(1)

Величины m[i,j] равны стоимостям оптимальных решений вспомогательных задач. Чтобы легче было проследить за процессом построения оптимального решения, обозначим через s[i,j] значение k, при котором последовательность AiAi+1...Aj разбивается на две подпоследовательности в процессе оптимальной расстановки скобок. Таким образом, величина s [i, j] равна значению k, такому что

m[i,j] = m[i,k] + m[k + 1, j] + pi-1pkpj.

Третий этап: вычисление оптимальной стоймости.

Важное наблюдение, которое можно сделать на данном этапе, заключается в том, что у нас относительно мало подзадач: по одной для каждого выбора величин i и j, удовлетворяющих неравенству 1 ? i ? j ? n, т.е. всего + n = и(n2). В рекурсивном алгоритме каждая вспомогательная задача может неоднократно встречаться в разных ветвях рекурсивного дерева. Такое свойство перекрытия вспомогательных подзадач -- вторая отличительная черта применимости метода динамического программирования.

Вместо решения рекуррентного соотношение выполним третий этап парадигмы динамического программирования и вычислим оптимальную стоимость путем построения таблицы в восходящем направлении. В описанной ниже процедуре предполагается, что размеры матриц Аi равны pi-1 * pi (i = 1,2,…,n). Входные данные представляют собой последовательность p = (p0,p1,…,pn ) длина данной последовательности равна length [р] -- n + 1. В процедуре используется вспомогательная таблица m [l..n, l..n] для хранения стоимостей m [i, j] и вспомогательная таблица s [l..n, l..n], в которую заносятся индексы k, при которых достигаются оптимальные стоимости m[i,j]. Таблица s будет использоваться при построении оптимального решения.

Чтобы корректно реализовать восходящий подход, необходимо определить, с помощью каких записей таблицы будут вычисляться величины m [i,j]. Из уравнения видно, что стоимость m [i, j] вычисления произведения последовательности j - i + 1 матриц зависит только от стоимости вычисления последовательностей матриц, содержащих менее j - i + 1 матриц. Другими словами, при k = i, i + 1,...,j -1 матрица Ai..k представляет собой произведение k - i + 1 < j - i + 1 матриц, а матрица Ak+1..j -- произведение j - k < j - i + 1 матриц. Таким образом, в ходе выполнения алгоритма следует организовать заполнение таблицы m в порядке, соответствующем решению задачи о расстановке скобок в последовательностях матриц возрастающей длины:

Matrix_Chain_Order(p)

n < length[p] -- 1

for i <1 to n

do m[i,i] < О

for l < 2 to n

do for i < l to n - l + 1

do j <i + l - 1

m[i, j] < ?

for k < i to j - 1

do q < m[i, k] + m [k +1, j] + pi-1pkpj

if q < m[i, j]

then m[i, j] < q

s [i, j] <k

return m и s .



Рис. 1. Таблицы m и s, вычисленные процедурой Matrix_Chain_Order для n=6.

На рис. 1 описанный выше процесс проиллюстрирован для цепочки, состоящей из n = 6 матриц, размеры которых равны: A1- 30 *35, A2 -- 35 * 15, А3 -- 15 * 5, A4 -- 5 * 10, A5 -- 10 * 20, A6 -- 20 * 25. Поскольку величины m [i, j] определены только при i ? j, используется только часть таблицы m, расположенная над ее главной диагональю. То же можно сказать и о таблице s. На рис. 1 таблица повернута так, чтобы ее главная диагональ была расположена горизонтально. В нижней части рисунка приведен список матриц, входящих в последовательность. На этой схеме легко найти минимальную стоимость m [i, j] перемножения частичной последовательности матриц AiAi+1...Aj. Она находится на пересечении линий, идущих от матрицы Аi вправо и вверх, и от матрицы Aj -- влево и вверх. В каждой горизонтальной строке таблицы содержатся стоимости перемножения частных последовательностей, состоящих из одинакового количества матриц. В процедуре Matrix_Chain_Order строки вычисляются снизу вверх, а элементы в каждой строке -- слева направо. Величина m[i, j] вычисляется с помощью произведений pi-1pkpj для k = i, i + 1,..., j - 1и величин внизу слева и внизу справа от m[i,j]. Из таблицы m видно, что минимальное количество скалярных умножений, необходимых для вычисления произведения шести матриц, равно m [1,6] = 15 125. Для пояснения приведем пример. При вычислении элемента m [5,2] использовались пары элементов, идущие от матриц A2 и А5 и имеющие одинаковый оттенок фона:

m[2,5]= min

= 7125. (2).

Несложный анализ структуры вложенных циклов в процедуре Matrix_Chain_Order показывает, что время ее работы составляет О(n3). Глубина вложения циклов равна трем, а индексы в каждом из них (l, i и k) принимают не более n - 1 значений. Таким образом, процедура Matrix_Chain_Order намного эффективнее, чем метод перебора и проверки всевозможных способов расстановки скобок, время работы которого экспоненциально зависит от количества перемножаемых матриц.

Четвертый этап: конструирование оптимального решения

Несмотря на то, что в процедуре Matrix_Chain_Order определяется оптимальное количество скалярных произведений, необходимых для вычисления произведения последовательности матриц, в нем не показано, как именно перемножаются матрицы. Оптимальное решение несложно построить с помощью информации, хранящейся в таблице s. В каждом элементе s[i,j] хранится значение индекса k, где при оптимальной расстановке скобок в последовательности AiAi+1...Aj выполняется разбиение. Таким образом, нам известно, что оптимальное вычисление произведения матриц A1..n выглядит как A1..s[1,n]As[1,n]+1..n.Эти частные произведения матриц можно вычислить рекурсивно, поскольку элемент s [1, з[1, п]] определяет матричное умножение, выполняемое последним при вычислении A1..s[1,n],a s[s[1,n]+1,n] -- последнее умножение при вычислении As[1,n]+ 1..n. Приведенная ниже рекурсивная процедура выводит оптимальный способ расстановки скобок в последовательности матриц (Ai, Ai+1,…, Aj), по таблице s, полученной в результате работы процедуры Matrix_Chain_Order, и индексам i и j. В результате вызова процедуры Print_Optimal_Parens(s, l,n) выводится оптимальная расстановка скобок в последовательности (A1, A2,..., Аn)

Print_Optimal_Parens(s, i, j)

lf i = j

then print "A"i

else print"("

Print_Optimal_Parens(s, i, s[i, j})

Print_Optimal_Parens(s, s[i, j] + 1, j)

print “)”

В примере, проиллюстрированном на рис.1 в результате вызова процедуры Print_Optimal_Parens(s, 1,6) выводится строка ((A1 (A2A3)) ((А4A5) A6)).

1.3 Задача " Лестницы"

Задача формулируется следующим образом: у маленького мальчика есть набор из N кубиков (5 ? N ? 500).

Из этих кубиков можно сложить различные лестницы. Лестницы имеют ступени различного размера, следующие в порядке возрастания этого размера, лестница не может иметь две одинаковые ступени. Каждая лестница должна иметь минимум две ступени, и каждая ступень должна состоять минимум из одного кубика. На рисунке приведены примеры лестниц для N=11 и N=5:

Рис. 2. Примеры лестниц для N=11 и N=5.

Нужно найти число Q различных лестниц, которые маленький мальчик может построить ровно из N кубиков. Эту задачу можно решить двумя способами. Первый способ:

n- количество кубиков, k- высота лестницы, j - высота k-1 ступеньки. Если последняя лесенка высоты k то предпоследняя должна быть высоты j где j от 1 до k - 1

Второй способ: - количество лестниц из n кубиков в которых ширина равна k если удалим нижний слой лестницы получится лестница либо той же ширины (если первая ступенька была высоты больше чем 1) либо лестница шириной на единицу меньше(если первая ступенька была высоты 1).

d[n-k][k-1] + d[n-k][k] (4)



1.4 Алгоритм Нудельмана-Вунша

Пример из молекулярной биологии. Молекулы ДНК, содержащие генетическую информацию - это длинные слова из четырех букв (А, Г, Ц, Т). В процессе эволюции, в результате мутаций, последовательности меняются, одна буква может замениться на другую, выпасть, а может добавиться новая. Насколько похожи два фрагмента, каким наименьшим числом превращений можно один из них получить из другого? Формулировка задачи. Даны два слова (длины M и N), состоящие из букв А, Г, Ц, Т. Найти подпоследовательность наибольшей длины, входящую в то и другое слово.

Пример. Слова ГЦАТАГГТЦ и АГЦААТГГТ. Схема решения иллюстрируется следующим рисунком. На рисунке закрашены клетки, в строке и в столбце которых находятся одинаковые буквы. Принцип заполнения таблицы W следующий: элемент W[i,j] равен наибольшему из чисел W[i-1,j], W[i,j-1],а если клетка <i,j> закрашена, то и W[i-1,j-1]+1.

Рис.3. Схема работы алгоритма Нудельмана-Вунша.

Формирование первой строки и первого столбца выполняется до заполнения таблицы и осуществляется так: единицей отмечается первое совпадение, затем эта единица автоматически заносится во все оставшиеся клетки. Например, W[3,1] - первое совпадение в столбце, затем эта единица идет по первому столбцу. Подпоследовательность формируется при обратном просмотре заполненной таблицы от клетки, помеченной максимальным значением. Путь - это клетки с метками, отличающимися на единицу, буквы из закрашенных клеток выписываются. Последовательность этих букв - ответ задачи. Для нашего примера две подпоследовательности: ГЦААГГТ и ГЦАТГГТ.

Фрагмент основной логики.

for i:=1 to Length(S1) do

for j:=1 to Length(S2) do begin

A[i,j]:=Max(A[i-1,j],A[i,j-1]);

if S1[i]=S2[j] then A[i,j]:=Max(A[i,j],A[i-1,j-1]+1);

end;

Writeln(`Ответ: ',A[Length(S1),Length(S2)]);

1.5 Задача о сдаче

В некоторой стране имеются монеты достоинством 1, 3, 5 и 10 копеек. Сколько существует способов вернуть сдачу номиналом n копеек? Порядок монет в сдаче важен. Для решения задачи нужно одновременно понять сколько использовать монет номиналом 1 коп. 3 коп. 5 коп. и 10 коп. Так как невозможно сразу понять, сколько использовать монет каждого номинала, нужно воспользоваться динамическим программированием.

Решение задачи. Предположим, что есть только одна монета номиналом 1 коп.

В этом случае задача решается достаточно легко. Потом используя это решение для решения следующей задачи для монет с номиналами 1 коп. и 3 коп.F(i) - количество способов вернуть сдачу размера n. Целью задачи является вычисление F(n).

Схема решения задачи следующая F(0) <F(1) < F(2) < F(3)…F(n-1) < F(n) .

F(0) = 1. Количество способов ничего не возвращать равняется единице. Каждую монету возвращаем по 0 штук.

F(1) = 1. Сдачу равной 1 коп. можно вернуть только одним способом.

F(2) = F(1) = 1. Возвращаем монету номиналом 1 коп. и остается вернуть еще 1 коп.

F(3) = F(2) + F(0) = 2. Есть выбор с какой монеты начинать или 1 коп. или 3коп. если начнем с монеты номиналом 1 коп. то останется еще вернуть 2 коп. Если начнем с монеты номиналом 3 коп. то возвращать уже ничего не надо.

F(4) = F(3) + (1) = 3. Задача для F(4) решается аналогично, как и для F(3). F(5) = F(4) + F(2) + F(0) = 5.

Формула для F

(k)k?10=F(k-1) + F(k-3) + F(k-5) + F(k-10).



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

Динамическое программирование по профилю -- это способ оптимизации перебора количества вариантов с помощью динамического программирования, когда одно из измерений небольшое.

К большинству олимпиадных задач ограничения жюри подбирает по принципу «как можно больше». То есть чтобы любые разумные реализации правильного решения проходили, а всё остальное -- нет. Когда встречается задача с маленькими ограничениями, это означает, что либо автор намеренно сбивает Вас с правильного пути, либо действительно эта задача решается каким-то (оптимизированным) перебором. Динамическое программирование по профилю -- одна из таких оптимизаций. Часто в таких задачах дело происходит на прямоугольной таблице, одна из размерностей которой достаточно мала (не более 10). Как и в обычном динамическом программировании требуется проверить существование, посчитать количество способов, стоимость и т.д. Асимптотика алгоритма, основанного на этой идее, является экспоненциальной только по одной размерности, а по второй -- линейная или даже лучше.

2.1 Некоторые обозначения и определения

Матрицей размера n * m называется прямоугольная таблица n * m, составленная из чисел. Обычно матрицы обозначают заглавными латинскими буквами.

Элемент i-й строки j-го столбца матрицы A обозначают через aij или a[i,j]. Произведением двух матриц и называется матрица такая , что



В этом случае пишут: C = AB.

D в степени k (Dk), при условии, что D -- квадратная (т. е. n = m) определяется следующим образом:

* D0 = E (единичная матрица),где

На диагонали у нее стоят единицы, в остальных клетках -- нули. Она не зря называется единичной -- при умножении на нее матрица не изменяется: AE = EA= A.

* Di = Di-1 D, i > 0.

В приводимом коде будет использоваться функция bit(x,i), возвращающая единицу или ноль -- i-й бит в двоичной записи числа x (нумерация битов с нуля).

// возвращает i-й бит числа x, нумерация с нуля

function bit(x, i : integer) : integer;

begin

if (i < 0) then bit := 0 else

if (x and (1 shl i) = 0) then bit := 0 else bit := 1;

end;



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

Дана таблица m*n, нужно найти количество способов полностью замостить ее неперекрывающимися костяшками домино ( прямоугольниками 2*1 и 1*2). Пусть m,n ? 10. В процессе замощения каждая клетка таблицы будет иметь одно из двух состояний: покрыта какой-нибудь доминошкой или нет. Чтобы запомнить состояние клеток одного столбца, достаточно одной переменной Р типа integer. Положим i-й бит P равным 1, если i-я сверху клетка данного столбца занята, 0 - если свободна. Будем говорить в таком случае, что P - битовая карта нашего столбца.

Дадим определение базовой линии и профиля.

Базовой линией будем называть вертикальную прямую, проходящую через узлы таблицы. Можно занумеровать все базовые линии, по проядку слева направо, начиная с нуля, таким образом, базовая линия с номером i - это прямая, отсекающая первые i столбцов от всех остальных (если такие имеются). Через bi будем обозначать базовую линию с номером i.

Столбцы занумеруем так: слева от bi будет столбец с номером i. Столбец с номером i находится между bi-1 и bi.

Рис. 4.



Профиль будет таким: 1001012 = 1 + 4 + 32 = 37 (заняты первая + третья + шестая клетки).

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

1) все клетки слева от bi-1 уже покрыты;

2) в i-м столбце нет вертикальных доминошек;

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

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

Для каждого профиля p1 базовой линии bi определим множество профилей p2 базовой линии bi+1, которые могут быть из него получены. На таблицу, соответствующую p1 можно класть доминошки только двух типов:

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

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

Рис. 5.



p1 = 37, p2 = 2; нетрудно заметить по рисунку 4, что из p1 можно получить p2. Таким образом, d[37, 2] = 1.

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

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

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

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

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

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

Пусть d[p1, p2] - количество способов из профиля p1 (для bi) получить p2 (для bi+1). Очевидно, для данной задачи про доминошки это число может отличаться в основном только значениями d[p1, p2].

Заметим, что всего профилей 2n: от 00…02 = 0 до 11…12 = 2n-1.поэтому в данном случае матрица D будет иметь размер 2n * 2n.

Пусть теперь a[i, p] - количество способов таким образом расположить доминошки, что p- профиль для bi (таким образом, все клетки левее bi-1 покрыты).

Начальные значения (i = 1):

a[1, 0] = 1;

a[1, p2] = 0, p2 = 1, … , 2n-1.

Общая формула (i ? 1):

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

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

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

D' = , A'= .

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

D и A при n = 2, m = 4:

D = , А =

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

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



Заключение

динамический программирование вероятностный матрица

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



Список литературы

1. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. - 2-е изд. - М.: Вильямс, 2005. - 1296 с.

2. Московские учебно-тренировочные сборы по информатике. Весна-2006 / Под ред. В.М. Гуровица -- М.: МЦНМО,2007.-- 194 с.

3. Окулов С.М. Решение сложных олимпиадных задач.

4. Динамическое программирование / С. М. Окулов, О. А. Пестов. --М. : БИНОМ. Лаборатория знаний, 2012.--296 с.

5. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960. 400 с.

6. Акулич И.Л. Математическое программирование в примерах и задачах. -- М.: 1986. -- 319 с.

7. Габасов Р., Кириллова Ф. М. Основы динамического программирования. -- Мн.: Изд-во БГУ, 1975. -- 262 с.

8. Щербина О. А. Методологические аспекты динамического программирования. 2007, вып. 22. -- c.21-36.

9. Bellman R., Dreyfus S. Applied Dynamic Programming. - Princeton: Princeton University Press, 1962.

10. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969. 118 с.

11. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. 458 с.



Приложения

Приложение 1

#include<vector>

#include<iostream>

#include<fstream>

using namespace std;

int main(){

int i,j,n,k;

ifstream fin("input.txt");

ofstream fout("output.txt");

fout<<"N=";

fin>>n;

fout<<n<<endl;

++n;

vector<_int64> a(n);

vector< vector<_int64> > p(n,a),q(n,a);

for(i=1;i<n;++i)

p[i][i]=1;

_int64 s;

for(i=3;i<n;++i)

for(j=1;j<i;++j)

{

s=0;

for(k=1;k<j;++k)

s+=p[i-j][k];

p[i][j]=s;

}

s=0;

for(j=1;j<n-1;++j)

s+=p[n-1][j];

fout<<"Q="<<s<<endl;

q[1][1]=1;

for(i=2;i<n;++i)

for(j=1;j<i;++j)

q[i][j]=q[i-j][j-1]+q[i-j][j];

s=0;

for(j=1;j*j<2*i;++j)

s+=q[n-1][j];

fout<<"Q1="<<s-1<<endl;

system("pause");

return 0;

}

Результаты работы программы:

N=32

Q=389

Q1=389

N - это значение которое вводится с клавиатуры Q, Q1 - результат работы программы.



Приложение 2

#include <iostream>

#include <vector>

using namespace std;

vector< vector<unsigned long long> > cache;

unsigned long long compress(const vector<unsigned> &coins, unsigned n, unsigned i)

{

unsigned long long result = 0;

if (!n)

return 0;

if (coins[i] == 1)

return 1;

const unsigned n_coins = n / coins[i];

if (!n_coins)

{

unsigned long long *cached_value = &cache[n][i - 1];

if (!*cached_value)

*cached_value = compress(coins, n, i - 1);

return *cached_value;

}

for (unsigned j = 0; j <= n_coins; ++j)

{

const unsigned piece_to_cut = j * coins[i];

if (piece_to_cut == n)

++result;

else if (i > 1)

{

const unsigned remainder = n - piece_to_cut;

unsigned long long *cached_value = &cache[remainder][i - 1];

if (!*cached_value)

*cached_value = compress(coins, remainder, i - 1);

result += *cached_value;

}

else

++result;

}

return result;

}

unsigned long long solve_v3(unsigned n, const vector<unsigned> &coins)

{

if (cache.size() < n + 1)

cache.resize(n + 1);

for (unsigned i = 0; i < cache.size(); ++i)

{

if (cache[i].size() < coins.size())

cache[i].resize(coins.size());

}

return compress(coins, n, coins.size() - 1);

}

int main()

{

vector<unsigned> coins;

coins.push_back(1);

coins.push_back(3);

coins.push_back(5);

coins.push_back(10);

//coins.push_back(50);

unsigned n;

cout<<"enter the amount- ";

while (cin >> n)

{

unsigned long long solutions = solve_v3(n, coins);

if (solutions > 1)

cout << "There are " << solutions << " ways to produce " << n << " cents change.\n";

else

cout << "There is only 1 way to produce " << n << " cents change.\n";

}

return 0;

}

Результаты работы программы:



Приложение 3

#include <iostream>

#include <cmath>

#include <map>

#include <iomanip>

class T_doska

{

typedef std::map<int, int> T_horizontal;

typedef std::map<int, T_horizontal> T_kletki;

static const int EMPTY_KLETKA = -1;

int dim_;

int count_;

double vsego_kostey_domino_;

double variant_max_;

T_kletki kletki_;

public:

T_doska(int dim)

: dim_(dim),

count_(0),

vsego_kostey_domino_(dim_ * dim_ / 2),

variant_max_(pow(static_cast<double>(2), vsego_kostey_domino_))

{}

void count_zamostit_domino()

{

for(unsigned cur_variant = 0; cur_variant < variant_max_; ++cur_variant)

{

if(uspeshno_zamostil(cur_variant))

{

++count_;

print_kletki();

}

}

std::cout << "Всего получили "

<< count_

<< " вариантов замощения доски "

<< dim_

<< " x "

<< dim_

<< " костями домино."

<< std::endl;

}

private:

void print_kletki()

{

std::cout << "Вариант № "

<< count_

<< std::endl;

for(int i = 0; i < dim_; ++i)

{

for(int j = 0; j < dim_; ++j)

{

if(kletki_[i][j] == EMPTY_KLETKA)

{

std::cout << std::setw(4)

<< "";

}

else

{

std::cout << std::setw(4)

<< kletki_[i][j];

}

}

std::cout << std::endl

<< std::endl;

}

}

bool uspeshno_zamostil(unsigned cur_variant)

{

unsigned temp_cur_variant = cur_variant;

kletki_clear();

for(int cur_cost_domino = 1; cur_cost_domino <= vsego_kostey_domino_;

++cur_cost_domino)

{

int variant_bin_dig = temp_cur_variant % 2;

temp_cur_variant /= 2;

const int VPRAVO = 0;

const int VNIZ = 1;

//Ищем первую пустую клетку доски.

int first_empty_kletka_i;

int first_empty_kletka_j;

if(!get_first_empty_kletka(first_empty_kletka_i, first_empty_kletka_j))

{

return false;

}

kletki_[first_empty_kletka_i][first_empty_kletka_j] = cur_cost_domino;

switch(variant_bin_dig)

{

case VPRAVO:

{

int& kletka_sprava_ot_pustoy

= kletki_[first_empty_kletka_i][first_empty_kletka_j + 1];

if(kletka_sprava_ot_pustoy != EMPTY_KLETKA) return false;

kletka_sprava_ot_pustoy = cur_cost_domino;

break;

}

case VNIZ:

{

int& kletka_snizu_ot_pustoy

= kletki_[first_empty_kletka_i + 1][first_empty_kletka_j];

if(kletka_snizu_ot_pustoy != EMPTY_KLETKA) return false;

kletka_snizu_ot_pustoy = cur_cost_domino;

break;

}

}//switch(variant_bin_dig)

}//for(int cur_cost_domino = 1; cur_cost_domino <= vsego_kostey_domino_;

return true;

}

bool get_first_empty_kletka

(

int& first_empty_kletka_i,

int& first_empty_kletka_j

)

{

for(int i = 0; i < dim_; ++i)

{

for(int j = 0; j < dim_; ++j)

{

if(kletki_[i][j] == EMPTY_KLETKA)

{

first_empty_kletka_i = i;

first_empty_kletka_j = j;

return true;

}

}

}

return false;

}

void kletki_clear()

{

for(int i = 0; i < dim_; ++i)

{

for(int j = 0; j < dim_; ++j)

{

kletki_[i][j] = EMPTY_KLETKA;

}

}

}

};

int main()

std::locale::global(std::locale(""));

std::cout << "Введите длину стороны доски: ";

int doska_dim;

std::cin >> doska_dim;

T_doska doska(doska_dim);

doska.count_zamostit_domino();

system("pause");

return 0;



Результат работы программы:

Размещено на Allbest.ru