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

Главная

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

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИФГБОУ ВПО «УДМУРТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
КАФЕДРА ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ И ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ
Применение метода динамического программирования в различных задачах
Глава 1. Обзор задач решаемых методом динамического программирования
1.1 Составление маршрута оптимальной длины
Глава 2. Динамическое программирование по профилю
2.1 Некоторые обозначения и определения
Повышение эффективности вычислений при решении определенного класса задач математического программирования может быть достигнуто путем использования методов динамического программирования. Особенностями методов динамического программирования являются использование для их реализации принципов инвариантного погружения и оптимальности. Принцип инвариантного погружения предполагает замену общей задачи на эквивалентную совокупность более простых (пошаговых) задач. Принцип оптимальности определяет возможность получения глобально-оптимальных решений на основе решений пошаговых задач оптимизации. Методы динамического программирования позволяют существенно сократить число анализируемых вариантов решений в процессе определения глобально-оптимального решения за счет учета априорной информации о решениях, не являющихся допустимыми, и использования информации, полученной на предыдущих шагах оптимизации. Кроме того, достоинством методов динамического программирования является их инвариантность к классу целевой и ограничительных функций.
Динамическое программирование по большому счету это техника, позволяющая решать некоторые задачи комбинаторики, оптимизации и другие задачи, обладающие определенным свойством. Проблема оптимизации это очень большая область, с которой сталкиваются и ученные и мы в повседневной жизни. Максимизация минимизации прибылей и расходов, максимизация шансов выиграть лотерею, максимизация вероятности того, что наши вложения которые мы совершили на бирже принесут прибыль а не убытки. Минимизация расходов для человека, у которого есть свое дело, свой магазин или производит те или иные заказы, максимизация вероятности сдать экзамен, перечислять можно бесконечно долго. Большинство проблем, с которыми мы сталкиваемся в жизни можно отнести к оптимизации. Не все задачи можно решить методом динамического программирования, а только те, которые обладают определенными свойствами. Но даже этот подкласс задач, которые можно решить с помощью динамического программирования, необычайно богат и используются во многих областях математики, статистики, теории игр, информатики, экономики и в компьютерных науках.
Глава 1. Обзор задач решаемых методом динамического программирования
Динамическое программирование позволяет решать задачи более простым способом. Предположим, что в задаче есть свойство оптимальности. Из всей задачи можно взять одну переменную, например х1, и решить задачу только для х1. После решения этой маленькой задачи и нахождения для нее оптимального решения используя принцип оптимальности подзадач, и найти решение для более сложной задачи с помощью первой подзадачи. После получения оптимального решения для задачи с переменными х1 и х2 используя ее для решения следующей задачи с переменными х1 х2 и х3 и так дальше пока не решим всю задачу.
1.1 Составления маршрута оптимальной длины
В качестве примера можно рассмотреть для начала одну простенькую задачу про составление маршрутов. Задача очень простая, и в то же время очень полезная для каждого человека. Задача формулируется следующим образом: есть некая карта дорог, которую можно изобразить в виде графа, и наша цель добраться из пункта А в пункт Б. Нужно выбрать путь с минимальным расстоянием, и придерживаясь которого будет истрачено минимальное количество топлива. Для нахождения кратчайшего пути необходимо принять решения. Куда повернуть на каждом перекрестке. Целевой функцией является минимизировать расстояние и затраты на топливо. Есть переменные выбора: для каждого перекрестка нужно решить куда ехать. Задачи такого типа называются задачами оптимизации. Целью таких задач является выбор самого оптимального варианта из всех возможных.
Следующий пример динамического программирования - алгоритм позволяющий решить задачу о перемножении цепочки матриц. Постановка задачи такова: пусть имеется последовательность, состоящая из n матриц, и нужно вычислить их произведение A1A2…An.
Этот выражение можно вычислить, используя в качестве подпрограммы стандартный алгоритм перемножения пар матриц. Но для этого сначала необходимо расставить скобки, чтобы все неоднозначности в порядке перемножения. Порядок произведения матриц полностью определен скобками, если произведение является либо отдельной матрицей, либо взятым в скобки произведением двух последовательностей матриц, в котором порядок перемножения полностью определен скобками. Матричное умножение обладает свойством ассоциативности, поэтому результат не зависит от расстановки скобок. Например, если задана последовательность матриц (A1,A2,A3,A4), то способ вычисления их произведения можно полностью определить с помощью скобок пятью различными способами:
От того как расставлены скобки при перемножении последовательности матриц, может сильно зависеть время, затраченное на вычисление произведения. Сначала рассмотрим, как определить стоимость произведения двух матриц. Ниже приводится псевдокод стандартного алгоритма. Атрибуты rows и columns означают количество строк и столбцов матрицы.
do C[i,j] < C[i,j] + A[i, k] * B[k,j]
Матрицы А и В можно перемножать, только если они совместимы: количество столбцов матрицы А должно совпадать с количеством строк матрицы В. Если А -- это матрица размера р * 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 принимает вид:
Величины 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 в порядке, соответствующем решению задачи о расстановке скобок в последовательностях матриц возрастающей длины:
do q < m[i, k] + m [k +1, j] + pi-1pkpj
Рис. 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 и имеющие одинаковый оттенок фона:
Несложный анализ структуры вложенных циклов в процедуре 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, s[i, j})
Print_Optimal_Parens(s, s[i, j] + 1, j)
В примере, проиллюстрированном на рис.1 в результате вызова процедуры Print_Optimal_Parens(s, 1,6) выводится строка ((A1 (A2A3)) ((А4A5) A6)).
Задача формулируется следующим образом: у маленького мальчика есть набор из 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).
Пример из молекулярной биологии. Молекулы ДНК, содержащие генетическую информацию - это длинные слова из четырех букв (А, Г, Ц, Т). В процессе эволюции, в результате мутаций, последовательности меняются, одна буква может замениться на другую, выпасть, а может добавиться новая. Насколько похожи два фрагмента, каким наименьшим числом превращений можно один из них получить из другого? Формулировка задачи. Даны два слова (длины M и N), состоящие из букв А, Г, Ц, Т. Найти подпоследовательность наибольшей длины, входящую в то и другое слово.
Пример. Слова ГЦАТАГГТЦ и АГЦААТГГТ. Схема решения иллюстрируется следующим рисунком. На рисунке закрашены клетки, в строке и в столбце которых находятся одинаковые буквы. Принцип заполнения таблицы W следующий: элемент W[i,j] равен наибольшему из чисел W[i-1,j], W[i,j-1],а если клетка закрашена, то и W[i-1,j-1]+1.
Рис.3. Схема работы алгоритма Нудельмана-Вунша.
Формирование первой строки и первого столбца выполняется до заполнения таблицы и осуществляется так: единицей отмечается первое совпадение, затем эта единица автоматически заносится во все оставшиеся клетки. Например, W[3,1] - первое совпадение в столбце, затем эта единица идет по первому столбцу. Подпоследовательность формируется при обратном просмотре заполненной таблицы от клетки, помеченной максимальным значением. Путь - это клетки с метками, отличающимися на единицу, буквы из закрашенных клеток выписываются. Последовательность этих букв - ответ задачи. Для нашего примера две подпоследовательности: ГЦААГГТ и ГЦАТГГТ.
if S1[i]=S2[j] then A[i,j]:=Max(A[i,j],A[i-1,j-1]+1);
Writeln(`Ответ: ',A[Length(S1),Length(S2)]);
В некоторой стране имеются монеты достоинством 1, 3, 5 и 10 копеек. Сколько существует способов вернуть сдачу номиналом n копеек? Порядок монет в сдаче важен. Для решения задачи нужно одновременно понять сколько использовать монет номиналом 1 коп. 3 коп. 5 коп. и 10 коп. Так как невозможно сразу понять, сколько использовать монет каждого номинала, нужно воспользоваться динамическим программированием.
Решение задачи. Предположим, что есть только одна монета номиналом 1 коп.
В этом случае задача решается достаточно легко. Потом используя это решение для решения следующей задачи для монет с номиналами 1 коп. и 3 коп.F(i) - количество способов вернуть сдачу размера n. Целью задачи является вычисление F(n).
Схема решения задачи следующая F(0) Применение метода динамического программирования в различных задачах курсовая работа. Программирование, компьютеры и кибернетика.
Как Любовь Влияет На Человека Итоговое Сочинение
Реферат: Linda Pastan And Sharon Olds Essay Research
Сочинение О Пользе Чтения 8 Класс
Реферат: Swan Lake Vs Revelations Essay Research Paper
Это Ядовитое Слово Обломовщина Мини Сочинение
Реферат: Формы и методы осуществления электронных платежей
Реферат Интервал Между Строками
Комарова 7 Класс Контрольные Работы
Сочинение по теме Трагедия “Гамлет”
Реферат: Объединение русских земель и образование московского государства. Скачать бесплатно и без регистрации
Клише Для Сочинения По Литературе 10 Класс
Коррекция Отклоняющегося Поведения Ребенка Средствами Сказкотерапии Реферат
Математика Наука Рассуждать И Мыслить Эссе
Реферат по теме Товароведная характеристика натурального кофе
Реферат: Спортивные сооружения для зимних видов спорта
Курсовая работа: Особенности воображения у детей с общим недоразвитием речи
Структура Философского Знания Реферат По Философии
Доклад: Профессионализм политолога: анализ, принятие решений, управление событиями. Скачать бесплатно и без регистрации
Актуальные Темы Курсовых Работ По Международному Праву
Реферат по теме Феномен управления в истории
Образование в России XIX века - История и исторические личности реферат
Налоговое правоотношение - Государство и право контрольная работа
Прикладна теорія цифрових автоматів - Программирование, компьютеры и кибернетика курсовая работа