Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 89
Текст из файла (страница 89)
В качестве примера приведем один из способов преобразования исходной строки а1дог1гЬв в конечную строку а1сгц1эсйс. В ходе этого преобразования выполняется перечисленная ниже последовательносп операций, в которых символы подчерка — это элементы х [1] и х [~] после выполнения очередной операции: Операция а а1 а1г а1С а1сг а1сги Исходные строки Копирование Копирование Замена символом г Удаление Копирование Вставка символа ц а1дог1с1ип а1дог1гЬв а1дог1Г1ца а1догйггпп а1дог1гйт а1догйг1нп а1дог1гйт Глава 15.
Динамическое программирование 437 Вставка символа з. Вставка символа з Перестановка Вставка символа с Удаление остатка а1дог1ПЬв а1дог1~1пп а1дог1сЫп а 1 до г1 ПЫп а1сог1ТЬв а11го1 а1сгцуз а1пгоузс1 а1пгцузпйс а1сгцузпус Заметим, что существует несколько других последовательностей операций, позволяющих преобразовать строку а 1 дог 1пгпп в строку а1сгц1зсус.
а) Пусть имеется две последовательности х [1..т1 и у[1..п], а также множество, элементами которого являются стоимости операций преобразования. Расстояииак редактирования (едй гйз~алсе) от х до у называется минимальная стоимость последовательности операций преобразования х в у. Опишите основанный на принципах динамического программирования алгоритм, в котором определяется расстояние редактирования от х [1..т[ до у [1..п[ и выводится оптимальная последовательность операций редактирования.
Проанализируйте время работы этого алгоритма и требуемую для него память. Задача о расстоянии редактирования — это обобщение задачи об анализе двух ДНК (см., например, книгу Сетубала (БешЬа!) и Мейданиса (МеЫап1з) [272, раздел 3.2)). Имеется два метода, позволяющих оценить подобие двух ДНК путем их выравнивания. Один способ выравнивания двух последовательностей х и у заключается в том, чтобы вставлять пробелы в произвольных местах этих двух последовательностей (включая позиции, расположенные в конце одной из них). Получившиеся в результате последовательности х' и у' должны иметь одинаковую длину, однако они не могут содержать пробелы в одинаковых позициях (т.е. не сушествует С каждой операцией преобразования связана своя стоимость, которая зависит от конкретного приложения.
Однако мы предположим, что стоимость каждой операции — известная константа. Кроме того, предполагается, что стоимости отдельно взятых операций копирования и замены меньше суммарной стоимости операций удаления и вставки, иначе применять этн операции было бы нерационально. Стоимость данной последовательности операций преобразования представляет собой сумму стоимостей отдельных операций последовательности. Стоимость приведенной выше последовательности преобразований строки а1догугЬп~ в строку а1~гцузпус равна сумме трех стоимостей копирования, стоимости замены, стоимости удаления, четырем стоимостям вставки, стоимости перестановки и удаления остатка.
Часть 1Ч. Усовершенствованные методы разработки и анализа 438 такого индекса у, чтобы и зэ [з], и у' [Я были пробелами). Далее каждой позиции присваивается определенное количество баллов в соответствии со сформулированными ниже правилами: ° +1, если ж' [т] = у' [з] и ни один из этих элементов не является пробелом; ° — 1, если х'[Я ф у'[з] и ни один из этих элементов не является пробелом; ° — 2, если элемент х'[з] или элемент у'[з] является пробелом. Стоимость выравнивания определяется как сумма баллов, полученных при сравнении отдельных позиций. Например, если заданы последовательности х = САТССССАТ и у = СААТСТСААТС, то одно из возможных выравниваний имеет вид: С АТСС ССАТ СААТ СТСААТС -*++*+*+-++* Символ + под позицией указывает на то, что ей присваивается балл +1, символ — означает балл — 1, а символ * — балл — 2.
Таким образом, полная стоимость равна 6 1 — 2. 1 — 4 2 = — 4. б) Объясните, как свести задачу о поиске оптимального выравнивания к задаче о поиске расстояния редактирования с помощью подмножества операций преобразования, состоящего из копирования, замены, удаления элемента, вставки, перестановки и удаления остатка. !5-4. Вечеринка в фирме Профессор Тамада является консультантом президента корпорации по вопросам проведения вечеринок компании. Взаимоотношения между сотрудниками компании описываются иерархической структурой.
Это означает, что отношение "начальник-подчиненный" образует дерево, во главе (в корне) которого находится президент. В отделе кадров каждому служашему присвоили рейтинг дружелюбия, представленный действительным числом. Чтобы на вечеринке все чувствовали себя раскованно, президент выдвинул требование, согласно которому ее не должны одновременно посещать сотрудник и его непосредственный начальник. Профессору Тамаде предоставили дерево, описывающее структуру корпорации в представлении с левым дочерним и правым сестринским узлами, описанном в разделе 10.4. Каждый узел дерева, кроме указателей, содержит имя сотрудника и его рейтинг дружелюбия. Опишите алгоритм, Глава 15. Динамическое программирование 439 предназначенный для составления списка гостей„который бы давал максимальное значение суммы рейтингов дружелюбия гостей.
Проанализируйте время работы этого алгоритма. 15-5. Алгоритм Витерби Подход динамического программирования можно использовать в ориентированном графе С = (У, Е) для распознавания речи. Каждое ребро (и, о) е Е графа помечено звуком и (и, е), который является членом конечного множества звуков Е. Граф с метками представляет собой формальную модель речи человека, который разговаривает на языке, состоящем из ограниченного множества звуков. Все пути в графе, которые начинаются в выделенной вершине оо е У, соответствуют возможной последовательности звуков, допустимых в данной модели. Метка направленного пути по определению является объединением меток, соответствующих ребрам, из которых состоит путь.
а) Разработайте эффективный алгоритм, который для заданного графа С с помеченными ребрами и выделенной вершиной оо, и последовательности а = (~ты аз,..., пь) символов из множества Е возвращал бы путь в графе С, который начинается в вершине ео и имеет метку а (если таковой существует). В противном случае алгоритм должен возвращать строку хо-я~си-РАтн (нет такого пути). Проанализируйте время работы алгоритма.
(Указание: могут оказаться полезными концепции, изложенные в главе 22.) Теперь предположим, что каждому ребру (и, е) Е Е также сопоставляется неотрицательная вероятность р(е, а) перехода по этому ребру из вершины и. При этом издается соответствующий звук. Сумма вероятностей по всем ребрам, исходящим из произвольной вершины, равна !. По определению вероятность пути равна произведению вероятностей составляющих его ребер.
Вероятность пути, берущего начало в вершине оо, можно рассматривать как вероятность "случайной прогулки", которая начинается в этой вершине и продолжается по случайному пути. Выбор каждого ребра на этом пути в вершине и производится в соответствии с вероятностями ребер, исходящих из этой вершины. б) Обобщите сформулированный в части а) ответ так, чтобы возвращаемый путь (если он существует) был наиболее вероятным из всех путей, начинающихся в вершине оо и имеющих метку ж Проанализируйте время работы этого алгоритма. 15-6. Передвижение по шахматной доске Предположим, имеется шахматная доска размером п х и клеток и шашка.
Необходимо провести шашку от нижнего края доски к верхнему. Ходы Часть 1Ч. Усовершенствованные методы разработки н анализа 440 можно делать в соответствии со сформулированным далее правилом. На каждом ходу шашка передвигается в одну из следующих клеток: а) на соседнюю клетку, расположенную непосредственно над текущей; б) на ближайшую клетку, расположенную по диагонали в направлении вверх и влево (если шашка не находится в крайнем левом столбце); в) на ближайшую клетку, расположенную по диагонали в направлении вверх и вправо (если шашка не находится в крайнем правом столбце).
Каждый ход из клетки х в клетку у имеет стоимость р (х, у), которая задается для всех пар (х, у), допускающих ход. При этом величины р (х, у) не обязательно положительны. Сформулируйте алгоритм, определяюший последовательность ходов, лля которой стоимость полного пути от нижнего края доски к верхнему краю будет максимальной. В качестве начальной может быть выбрана любая клетка в нижнем ряду.
Аналогично, маршрут может заканчиваться в любой клетке верхнего ряда. Чему равно время работы этого алгоритма? 15-7. Расписание для получения максимального дохода Предположим, что имеется один компьютер и множество, состоящее нз и заданий иы аз, ., а„, которые нужно выполнить на этом компьютере. Каждому заданию а соответствует время обработки 1з, прибыль р и конечный срок выполнения Н .
Компьютер не способен выполнять несколько заданий одновременно. Кроме того, если запущено задание аз, то оио должно выполняться без прерываний в течение времени 1 . Если задание а завершается до того, как истечет конечный срок его выполнения г)1, вы получаете доход р . Если же это произойдет после момента времени йз, то полученный доход равен нулю. Сформулируйте алгоритм, который бы выдавал расписание для получения максимальной прибыли. При этом предполагается, что любое время выполнения задания выражается целым числом в интервале от 1 до и. Чему равно время работы этого алгоритма? Заключительные замечания Беллман (й. Вейшап) приступил к систематическому изучению динамического программирования в 1955 году.
Как в названии "динамическое программирование", так и в термине "линейное программирование" слово "программирование" относится к методу табличного решения. Методы оптимизации, включающие в себя элементы динамического программирования, были известны и раньше, однако именно Беллман дал строгое математическое обоснование этой области [34]. Глава 15. Динамическое программирование 441 Ху (Ни) и Шинг (ЯЫп8) (159,160] сформулировали алгоритм, позволяющий решить задачу о перемножении матриц в течение времени О (и 18 п). По-видимому, алгоритм решения задачи о самой длинной общей подпоследовательности, время работы которого равно О (тп), — плод "народного" творчества. Кнут (Кппбп) [63] поставил вопрос о том, существует ли алгоритм решения этой задачи, время работы которого возрастало бы медленнее, чем квадрат размера.
Масек (Мазек) и Патерсон (Ра~егзоп) ответили на этот вопрос утвердительно, разработав алгоритм, время работы которого равно О (гоп/18 п), где и ( т, а последовательности составлены из элементов множества ограниченного размера. Шимански (Бгппапзк() (288] показал, что в особом случае, когда ни один элемент не появляется во входной последовательности более одного раза, эту задачу можно решить в течение времени О ((и+ гп) 18(п+ т)). Многие из этих результатов были обобщены для задачи о вычислении расстояния редактирования (задача 15-3). Ранняя работа Гильберта (ОВЬегг) и Мура (Мооге) (114], посвященная бинарному кодированию переменной длины, нашла применение при конструировании оптимального бинарного дерева поиска для случая, когда все вероятности р; равны О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
