Алгоритмы - построение и анализ (1021735), страница 87
Текст из файла (страница 87)
15.9б показан кратчайший битонический маршрут, проходящий через те же семь точек. В этом случае возможна разработка алгоритма, время работы которого является полиномиальным. Напишите алгоритм, предназначенный для определения оптимального битонического маршрута, время работы которого будет равным О (пз]. Предполагается, что не существует двух точек, координаты х которых совпадают.
(Указание: перебор вариантов следует организовать слева направо, поддерживая оптимальные возможности для двух частей, из кото- рых состоит маршрут.) Глава 15. Динамическое программирование 435 а) Рис. 15.9. а) кратчайший (ие битоиический) замкнутый маршрут длиной 24.89; б) кратчайший битоиический маршрут длиной 25.58 15-2. Вывод на печать с форматированием Рассмотрим задачу о форматировании параграфа текста, предназначенного для вывода на печать. Входной текст представляет собой последовательность, состоящую из п слов, длины которых равны 1м1з,..., 1„ (длина слов измеряется в символах). При выводе на печать параграф должен быть аккуратно отформатирован и размещен в несколько строк, в каждой из которых помещается по М символов.
Сформулируем критерий "аккуратного" форматирования. Если данная строка содержит слова от г-го до з-го и мы оставляем между словами ровно по одному пробелу, количество оставшихся пробелов„равное М вЂ” ) + г — ~;э~,. 1ш должно быть неотрицательно, чтобы все слова поместились в строке. Мы хотим минимизировать сумму возведенных в куб остатков по всем строкам, кроме последней. Сформулируйте алгоритм, основанный на принципах динамического программирования, который аккуратно выводит на принтер параграф, состоящий из и слов.
Проанализируйте время работы этого алгоритма и требуемое для его работы количество памяти. 15-3. Расстояние редактирования Для того чтобы преобразовать исходную строку текста х[1..т[ в конечную строку у [1..п]„можно воспользоваться различными операциями преобразования. Наша цель заключается в том, чтобы для данных строк х и у определить последовательность преобразований, превращающих х в у. Для хранения промежуточных результатов используется массив г (предполагается, что он достаточно велик для хранения необходимых промежуточных результатов).
Изначально массив г пуст, а в конце работы з [2[ = у [Я для всех ) = 1, 2,..., и. Поддерживается текущий индекс г массива к и индекс з массива г, и в ходе выполнения операций преобразования разрешено изменять элементы массива з и эти индексы. В начале работы алгоритма г = з = 1. В процессе преобразования необходимо Часть И. Усовершенствованные методы разработки и анализа 436 проверить каждый символ массива х. Это означает, что в конце выполне- ния последовательности операций значение г должно быть равно т + 1.
Всего имеется шесть перечисленных ниже операций преобразования. Копирование символа из массива х в массив г путем присвоения х [Я вЂ” х [г] с последующим увеличением индексов г и у. В этой операции проверяется элемент х [1]. Замена символа из массива х другим символом с путем присвоения я [Я с с последующим увеличением индексов г и тд В этой операции проверяется элемент х [4]. Удаление символа из массива х путем увеличения на единицу индекса г и сохранения индекса 1 прежним.
В этой операции проверяется элемент х [1]. Вставка символа с в массив г путем присвоения г [у] — с и увеличения на единицу индекса з при сохранении индекса г прежним. В этой операции не проверяется ни один элемент массива х. Перестановка двух следующих символов путем копирования их из массива х в массив з в обратном порядке. Это делается путем присваиваний з [Я вЂ” х [г + Ц и г [у + 1] — х [г] с последующим изменением значений индексов г — 1+ 2 и з — т'+ 2. В этой операции проверяются элементы х [г] и х [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догйг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. Алгоритм Витерби Подход динамического программирования можно использовать в ориентированном графе С = (У, Е) для распознавания речи.
Каждое ребро (и, о) е Е графа помечено звуком и (и, е), который является членом конечного множества звуков Е. Граф с метками представляет собой формальную модель речи человека, который разговаривает на языке, состоящем из ограниченного множества звуков. Все пути в графе, которые начинаются в выделенной вершине оо е У, соответствуют возможной последовательности звуков, допустимых в данной модели. Метка направленного пути по определению является объединением меток, соответствующих ребрам, из которых состоит путь. а) Разработайте эффективный алгоритм, который для заданного графа С с помеченными ребрами и выделенной вершиной оо, и последовательности а = (~ты аз,..., пь) символов из множества Е возвращал бы путь в графе С, который начинается в вершине ео и имеет метку а (если таковой существует). В противном случае алгоритм должен возвращать строку хо-я~си-РАтн (нет такого пути).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
