ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ РФ

ГОУ ВПО «АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Физико-технический факультет

Кафедра прикладной физики, электроники и информационной

безопасности

Динамическое программирование

Методические указания к выполнению лабораторной работы

Барнаул - 2010

ББК

УДК

Составитель: А.А. Лепендин

Динамическое программирование. Методические указания к выполнению лабораторной работы / Барнаул: Изд-во АлтГУ, 2010. - 13 с.

Методические указания к выполнению лабораторной работы «Динамическое программирование» по курсу «Методы программирования» предназначены для студентов 2 курса по специальности: 090105.65 – «Комплексное обеспечение информационной безопасности автоматизированных систем»

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

Рецензент: к.ф.-м.н., доц. А.В. Головин

Цель работы

Изучить метод динамического программирования, применяющийся при решении задач оптимизации.

Оборудование и программное обеспечение

ПЭВМ, ОС Windows, компилятор языка C++ (Dev-C++).

Задание

Результаты выполнения лабораторной работы необходимо отразить в отчете. Отчет следует оформить в виде текстового документа (формат файла отчета – doc, rtf либо odt) со вставленными блок-схемами, листингами исходного кода и необходимыми комментариями, иллюстрирующими основные этапы работы. Изучите теоретический материал по данной теме. Решите одну задачу из списка ниже на усмотрение преподавателя. Необходимо написать три версии алгоритма для решения предложенной задачи.

• неэффективная, при помоши рекуррентного спуска.

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

• модификация первой, основанная на механизме «запоминания».

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

Теоретические сведения

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

Оптимальная подструктура

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

Можно видеть, что поиск оптимальной подструктуры происходит по общему образцу.

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

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

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

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

Характеризуя пространство подзадач, следует придерживаться такого практического правила: это пространство должно быть как можно проще, а потом расширьте его до необходимых пределов.

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

1. количество вспомогательных задач, которые используются при оптимальном решении исходной задачи;

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

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

• общего количества вспомогательных задач;

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

Оптимальная подструктура используется в динамическом программировании в восходящем направлении. Другими словами, сначала находятся оптимальные решения вспомогательных задач, после чего определяется оптимальное решение поставленной задачи. Поиск оптимального решения задачи влечет за собой необходимость выбора одной из вспомогательных задач, которые будут использоваться в решении полной задачи. Стоимость решения задачи обычно определяется как сумма стоимостей решений вспомогательных задач и стоимости, которая затрачивается на определение правильного выбора.

Оптимальной подструктурой могут обладать и так называемые жадные алгоритмы. Но между ними и динамическим программированием существует различие, заключающееся в том, что в жадных алгоритмах оптимальная подструктура используется в нисходящем направлении. Вместо того чтобы находить оптимальные решения вспомогательных задач с последующим выбором одного из возможных вариантов, в жадных алгоритмах сначала делается выбор, который выглядит наилучшим на текущий момент, а потом решается возникшая в результате вспомогательная задача.

Некоторые тонкости

Следует быть особенно внимательным в отношении вопроса о применимости оптимальной подструктуры, когда она отсутствует в задаче. Рассмотрим такие две задачи, в которых имеется ориентированный граф G=(V, Е) и вершины .

Задача о кратчайшем невзвешенном пути. Нужно найти путь от вершины и к вершине v, состоящий из минимального количества ребер. Этот путь обязан быть простым, поскольку в результате удаления из него цикла получается путь, состоящий из меньшего количества ребер.

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

В задаче о кратчайшем пути возникает оптимальная подструктура. Это можно показать с помощью таких рассуждений. Предположим, что и≠v и задача является нетривиальной. В этом случае любой путь р от и к v должен содержать промежуточную вершину, скажем, w. (Заметим, что вершина w может совпадать с вершиной и или v.) Поэтому путь можно разложить на вспомогательные пути . Очевидно, что количество ребер, входящих в путь р, равно сумме числа ребер в путях р₁ и р₂. Утверждается, что если путь р от вершины и к вершине v оптимальный (т.е. кратчайший), то р₁ должен быть кратчайшим путем от вершины и к вершине w. Почему? Аргумент такой: если бы существовал другой путь, соединяющий вершины и и v и состоящий из меньшего количества ребер, чем p₁, скажем, , можно было бы вырезать путь р₁ и вставить путь , в результате чего получился бы путь, состоящий из меньшего количества ребер, чем путь р. А это противоречит предположению об оптимальности пути р. Аналогично, р₂ должен быть кратчайшим путем от вершины и к вершине v. Таким образом, кратчайший путь от вершины и к вершине v можно найти, рассмотрев все промежуточные вершины w, отыскав кратчайший путь от вершины и к вершине w и кратчайший путь от вершины w к вершине v, и выбрав промежуточную вершину w, через которую весь путь окажется кратчайшим.

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

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

Вторая составляющая часть, наличие которой необходимо для применения динамического программирования, заключается в том, что пространство вспомогательных задач должно быть "небольшим" в том смысле, что в результате выполнения рекурсивного алгоритма одни и те же вспомогательные задачи решаются снова и снова, а новые вспомогательные задачи не возникают. Обычно полное количество различающихся вспомогательных задач выражается как полиномиальная функция от объема входных данных. Когда рекурсивный алгоритм снова и снова обращается к одной и той же задаче, говорят, что задача оптимизации содержит перекрывающиеся вспомогательные задачи. В отличие от описанной выше ситуации, в задачах, решаемых с помощью алгоритма разбиения, на каждом шаге рекурсии обычно возникают полностью новые задачи. В алгоритмах динамического программирования обычно используется преимущество, заключающееся в наличии перекрывающихся вспомогательных задач. Это достигается путем однократного решения каждой вспомогательной задачи с последующим сохранением результатов в таблице, где при необходимости их можно будет найти за фиксированное время.

Построение оптимального решения

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

Запоминание

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

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

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

В общем случае, если все вспомогательные задачи необходимо решить хотя бы по одному разу, восходящий алгоритм, построенный по принципу динамического программирования, обычно работает быстрее, чем нисходящий алгоритм с запоминанием. Причины — отсутствие непроизводительных затрат на рекурсию и их сокращение при поддержке таблицы. Более того, в некоторых задачах после определенных исследований удается сократить время доступа к таблице или занимаемый ею объем. Если же можно обойтись без решения некоторых вспомогательных задач, содержащихся в пространстве подзадач данной задачи, запоминание результатов решений обладает тем преимуществом, что решаются только необходимые вспомогательные задачи.

Задачи

1. За долгую и верную службу Рыцарю позволено набрать сокровищ в сокровищнице своего сеньора. Сокровищница имеет форму прямоугольника, состоящего из отдельных "клеток" — прямоугольных комнат. В каждой комнате хранятся сокровища известной стоимости. Рыцарь может вынести сколько угодно сокровищ, но пройдя через сокровищницу только один раз. Он может начать с любой комнаты вдоль внешней северной стены сокровищницы (выбор комнаты — за рыцарем). На каждом шаге он может переходить в одну из трех "южно-соседних" комнат: южную, юго-восточную или юго-западную. Из комнат, граничащих с восточной или западной внешней стеной, возможны только два направления выхода. Закончить путь Рыцарь должен в любой из комнат на южной внешней стороне сокровищницы.

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

По заданной карте нужно найти один из допустимых путей, обеспечивающих наибольшую возможную сумму сокровищ.

Вход. Первая строка в тексте содержит два числа N и М, обозначающие "ширину" и "высоту", далее М строк по N неотрицательных целых чисел в каждой — стоимости сокровищ соответствующих комнат. Размеры сокровищницы не более чем 80x80 комнат.

Выход. В первой строке указывается номер (по порядку с запада на восток) комнаты северного ряда, из которой нужно начать движение, во второй — строка символов, означающих на­правление очередного перехода (S — на юг, Е — на юго-восток, W — на юго-запад); в третьей — полученная максимально возможная суммарная стоимость. Если есть несколько путей с максимальной суммой, вывести любой из них.

2. Прямоугольная таблица имеет М строк и N столбцов. В каждой ее клетке записано натуральное число не больше 200. Нужно пройти из левого верхнего угла таблицы в правый нижний, на каждом шаге перемещаясь на 1 клетку вправо или вниз. Очевидно, таких путей много, и для каждого можно найти сумму чисел в пройденных клетках. Ясно, что среди этих сумм есть максимальная.

"Хорошими" считаются не только пути с максимально возможной суммой, но и пути, сумма которых отличается от максимальной не более чем на К. Количество "хороших" путей гарантированно не больше 10.

Найти максимально возможную сумму и количество "хороших" путей.

Вход. Первая строка входного текста содержит три целых числа М (2<М<200), N (2<N<200) и K (0<K<200). Каждая из следующих М строк задает N чисел в соответствующих клетках.

Выход. Первая строка текста должна содержать максимально возможную сумму, вторая — количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.

3. Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины. Если таких несколько, то из них нужно выбрать ту, у которой наибольшая сумма чисел.

Вход. Первая строка текста sequence.dat содержит длину последовательности N (1<N<5000), вторая — N целых чисел (элементы последовательности, среди которых могут быть одинаковые). Значения элементов целые, от 0 до 50000.

Выход. В первой строке текстового файла sequence.sol должна быть выбранная подпоследовательность, во второй — сумма ее элементов.

4. Даны N коробок в форме прямоугольных параллелепипедов размерами a_i x b_i x c_i. Некоторые из них, как правило, можно вложить в другие. Толщина стенок коробок пренебрежимо мала, но строго больше нуля. Коробки разрешается вращать, но только на углы, кратные 90° (иначе говоря, вкладывать коробки можно только "ровно", а не "наискось"). Коробки вкладываются "как матрешки", т.е. меньшая в среднюю, а средняя в большую, но нельзя вложить в большую коробку несколько маленьких рядом.

Среди заданных коробок необходимо выбрать такие, которые можно последовательно вложить одну в другую, причем их суммарный объем должен быть как можно больше. Написать программу построения такой "цепочки" коробок. Если есть различные решения с одним и тем же максимальным суммарным объемом, вывести любое из них.

5. Денежная система некоторой страны предоставляет монеты номиналом с, = 1, с2, ..., сN. Как выдать сумму S с помощью минимального числа монет?

Вход. В первой строке — сумма S и количество номиналов N, во второй — значения номиналов: 1<N≤20, 1=с1<с2<...< сN≤50000, S≤100000.

Выход. В первой строке — минимальное количество монет, во второй — N чисел (количества монет каждого номинала).

6. Существует следующий способ набора букв на мобильном телефоне. Клавише 2 сопоставлены буквы abc, клавише 3 ‑ def и т.д. При наборе текста одно нажатие на клавишу 2 порождает символ а, два подряд нажатия ‑ символ b, три подряд ‑ символ c; аналогично, одно нажатие на 3 порождает d, два подряд ‑ е и т.д. Если же нужно набрать две буквы а, то нажимают на 2, немного ждут и снова нажимают на 2.

Обобщим ситуацию. Пусть есть алфавит из N символов, который нужно сопоставить М клавишам (M<N). Для каждого символа алфавита известна частота его использования. Нужно задать соответствие символов алфавита клавишам так, чтобы символы с первого по некоторый соответствовали первой клавише, с по некоторый ‑ второй клавише и т.д., а среднее количество нажатий на клавиши (исходя из известных частот) было минимальным. Формально говоря, нужно минимизировать характеристику , где fj ‑ частота использования j-го символа согласно входным данным, ti ‑ количество нажатий, нужное для набора i-го символа согласно построенному разбиению алфавита.

Вход. В первой строке текста записаны N и M, в следующих N строках — по одному целому числу, пропорциональному частоте использования символа (2<М≤100, М<N≤250).

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

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

Нужно найти такое разбиение абзаца на строки, чтобы высота абзаца была минимальной.

Вход. Первая строка текста содержит ширину области печати (т.е. максимальную допустимую длину строки) и число N (количество блоков в абзаце), где 5<N<200; следующие N строк ‑ по два числа (ширину и высоту блока); все размеры ‑ натуральные числа не больше 1000000.

Выход. В первую строку текста вывести полученную высоту абзаца, во вторую ‑ количество строк М, на которые нужно разбить абзац, в следующие N строк ‑ количества блоков в соответствующих строках абзаца.

8. Задана строка, символы которой могут повторяться. За один ход разрешается вычеркнуть в любом месте строки один или несколько одинаковых символов, идущих в строке подряд. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний.

Вход. Строка длиной не больше 255.

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

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

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

10. Триангуляция многоугольника— это разбиение его на треугольники непересекающимися диагоналями. Стоимость триангуляции определяется как сумма длин проведенных в ней диагоналей. Задан выпуклый многоугольник. Найти его триангуляцию с наименьшей стоимостью.

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

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

11. Заданы две строки длиной не больше 10⁴. Нужно найти:

а) самую длинную из их общих подстрок (например, для строк гавгав и кваква это будут а и в). Если таких подстрок несколько, найти наиболее "прижатую влево" в первой строке (а);

б) самую длинную из их общих подпоследовательностей символов (ава или вав для строк гавгав и кваква). Если их несколько, найти наиболее "прижатую влево" в первой строке (ава).

в) "расстояние" между строками — минимальное количество вставок и удалений символов, необходимых для преобразования одной строки в другую (гавгав и кваква имеют расстояние 6: удалить г, г и в в конце и вставить к, в и к).

12. Роман состоит из C глав. Нужно, не переставляя главы, разбить его на B (В<С) томов так, чтобы максимальная толщина тома (сумма количеств страниц вошедших в него глав) была как можно меньше. Каждую главу начинают с новой страницы, поэтому толщина тома есть сумма длин глав, входящих в него. Разрывать главы нельзя. Если есть несколько равноценных оптимальных решений, вывести любое из них.

Вход. В первой строке текста ‑ количества С и В, в следующих С строках ‑ длины глав. 3≤В≤40, В≤С≤250, суммарное число страниц не больше 3x104.

Выход. В первой строке ‑ максимальная толщина тома, в следующих В строках ‑ номера первой и последней глав каждого тома. Например, если пять глав имеют длины 300, 300, 500, 300, 300 и распределяются по трем томам, то максимальная толщина тома ‑ 600, первый том начинается главой 1 и заканчивается 2, второй включает только главу 3, третий ‑ главы 4 и 5.

13. Входной текст состоит из слов с известными длинами (количеством символов) l1, l2,..., lп и представляет абзац. Его нужно "правильно отформатировать" и вывести в несколько строк длиной М символов (M≥max li). Форматирование заключается в следующем. Если в строке размещаются слова с i-го по j-e, то между ними вставляется по одному пробелу и вычисляется остаток M‑j+i-(li+...+lj), который должен быть неотрицательным. Нужно минимизировать сумму кубов остатков по всем строкам, кроме последней.

14. "Дыра" и отрезки на прямой заданы целыми координатами своих концов. "Дыру" нужно закрыть с помощью отрезков; их суммарная длина должна быть минимальной.

Вход. "Дыра" и отрезки задаются в тексте: его первая строка содержит числа L и U (координаты левого и правого концов "дыры"), следующие строки — пары чисел Ai и Bi (0≤L<U≤1000, 0≤Аi<Вi≤1000). Отрезков не больше 100.

Выход. Если "дыру" можно закрыть, то в первую строку текста вывести сумму длин использованных отрезков, а в следующие строки ‑ пары координат в порядке возрастания координат левых концов использованных отрезков. Если дыру закрыть нельзя, то в первую строку вывести 0. Если решений несколько, вывести любое.

15. Строку S, состоящую из десятичных цифр, можно разделить на непустые последовательные подстроки S0, S1, S2,… (если записать их подряд, получим S). Каждая подстрока Si задает записанное ею число ai. Из чисел, заданных подстроками, образуется многочлен Нужно разбить строку S так, чтобы при заданном значении х этот многочлен имел минимальное значение (решений может быть несколько).

Вход. Первая строка текста содержит строку S длиной не больше 100, вторая— значение х (0,01≤x≤99,9).

Выход. В первой строке текста ‑ минимальное значение многочлена, во второй ‑ последовательность подстрок, разделенных пробелом.

16. Начальнику крупной организации нужно выбрать, какие заседания на конференции он посетит. Каждое заседание имеет интервал [ai, bi] и "важность" ci. Он не любит половинчатых решений, поэтому или находится на заседании все указанное время, или не приходит на него. Между заседаниями должен быть хотя бы минимальный перерыв, то есть, он может успеть на j-е после i-го только если aj>bi. Нужно максимизировать сумму важностей выбранных заседаний. Если возможны разные наборы с одинаковой суммарной важностью, выбрать тот, где меньше суммарная длина заседаний. Если одинаковы и сумма важностей, и сумма времен, выбрать любой из наборов.

Вход. Число заседаний N, затем N троек (ai, bi, сi).

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