Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 95
Текст из файла (страница 95)
Поддерживаются текущий индекс з массива х и индекс 5 массива г, и в ходе выполнения операций преобразования разрешено изменять элементы массива з и эти индексы. Изначально з = 5 = 1. В процессе преобразования необходимо проверить каждый символ массива х. Это означает, что в конце выполнения последовательности операций значение з должно быть равно т + 1.
Всего имеется шесть перечисленных ниже операций преобразования. Копирование символа из массива х в массив г путем присвоения з]1] = х]з] с последующим увеличением индексов з и ~. В этой операции проверяется элемент х]з]. Замена символа из массива х другим символом с путем присвоения зЦ = с с последуюшим увеличением индексов з и з( В этой операции проверяется элемент х]з]. Глава З Ь диламичеояе лрограммировалие 44! Удаление символа из массива х путем увеличения на единицу индекса 1 н сохранения индекса з прежним. В этой операции проверяется элемент х[1].
Вставка символа с в массив х путем присвоения гЦ] = с и увеличения на единицу индекса у при сохранении индекса 1 прежним. В этой операции не проверяется ни один элемент массива х. Перестановка двух следующих символов путем их копирования из массива х в массив х в обратном порядке.
Это делается путем присваиваний х[з] х[1 + Ц и х[з + 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ГЬзп а1|ЗогйТЬзп а1|Зог1ЕЬп| а а1 а1г а1г а1сг а1гги а1ггий а1йгийв а1йгийакй а1ггийвг1с а1пгийаГ1с 44з Часть ГК усовершенствованные методы разработки н аназнза а Пусть имеются две последовательности, х[1..пз] и у[1..п], а также множество, элементами которого являются стоимости операций преобразования. Расстоянием редактирования (ес(йс сйз1алсе) между х и у называется мимимальная стоимость последовательности операций преобразования х в у. Опишите основанный на принципах динамического программирования алгоритм, в котором определяется расстояние редактирования от х[1..
т] до у[1.. и] и выводится оптимальная последовательность операций редактирования. Проанализируйте время работы этого алгоритма и требуемую для него память. Задача о расстоянии редактирования — это обобщение задачи об анализе двух ДНК (см., например, книгу Сетубала (БензЬа1) и Мейданиса (МеЫап(з) [308, раздел 3.2]). Имеется несколько методов, позволяющих оценить подобие двух ДНК путем их выравнивания. Один такой способ выравнивания двух последовательностей х и у заключается в том, чтобы вставлять пробелы в произвольных местах этих двух последовательностей (включая позиции в концах). Получившиеся в результате последовательности х' и у' должны иметь одинаковую длину, однако они не могут содержать пробелы в одинаковых позициях (т.е. не существует такого индекса 1, чтобы и х'[з], и у'[з] были пробелами).
Затем каждой позиции присваивается определенное количество баллов в соответствии со сформулированными ниже правилами: +1, если х'[)] = у'[)] и ни один из этих элементов не является пробелом; — 1, если х'[)] ~ у'[)] и ни один из этих элементов не является пробелом; — 2, если либо х'Ц, либо у'[з] является пробелом. Стоимость выравнивания определяется как сумма баллов, полученных при сравнении отдельных позиций. Например, если заданы последовательности х 6АТССССАТ и у = СААТОТОААТС, то одно из возможных выравниваний имеет следующий вид. 6 АТСб ОСАТ СААТ 6ТСААТС -в++в+*+-++* Символ + под позицией указывает на то, что ей присваивается балл +1, символ— означает балл — 1, а символ * — балл — 2.
Таким образом, полная стоимость равна 61 — 21 — 42= — 4. б. Объясните, как свести задачу о поиске оптимального выравнивания к задаче о поиске расстояния редактирования с помощью подмножества операций преобразования, состоящего из копирования, замены, удаления элемента, вставки, перестановки и удаления остатка.
15.б. Вечеринка на з[)ирме Профессор Тамада является консультантом президента корпорации по вопросам проведения вечеринок компании. Взаимоотношения между сотрудниками компании описываются иерархической структурой. Это означает, что отношение 443 )нова !5. Динамичеолое орограммирооание "начальник — подчиненный" образует дерево, во главе (в корне) которого находится президент. В отделе кадров каждому служащему присвоили рейтинг дружелюбия, представленный действительным числом. Чтобы на вечеринке все чувствовали себя раскованно, президент выдвинул требование, согласно которому ее не должны одновременно посещать сотрудник и его непосредственный начальник. Профессору Тамаде предоставили дерево, описывающее структуру корпорации в представлении с левым дочерним и правым сестринским узлами, описанном в разделе 10.4, Каждый узел дерева, кроме указателей, содержит имя сотрудника и его рейтинг дружелюбия.
Опишите алгоритм, предназначенный для составления списка гостей, юторый бы давал максимальное значение суммы рейтингов дружелюбия гостей. Проанализируйте время работы этого алгоритма. )э.7. Алгоритм Внтербн Динамическое программирование можно использовать в ориентированном графе С = (У, Е) для распознавания речи. Каждое ребро (и, и) е Е графа помечено звуком а(и, и), юторый является членом конечного множества звуков Е.
Граф с метками представляет собой формальную модель речи человека, который разговаривает на языке, состоящем из ограниченного множества звуков. Все пути в графе, которые начинаются в выделенной вершине ио е У, соответствуют возможной последовательности звуков, допустимых в данной модели. Метка направленного пути по определению является конкатенацией меток, соответствующих ребрам, из которых состоит путь. а Разработайте эффективный алгоритм, который для заданного графа С с помеченными ребрами и вьщеленной вершиной ио и для последовательности звуков в = (оы от,..., оь) из множества Е возвращал бы путь в графе С, который начинается в вершине ио и имеет метку в (если таковой существует).
В противном случае алгоритм должен возвращать строку ыо-зг) си-Рятн (нет такого пути). Проанализируйте время работы алгоритма. (Указание) могут оказаться полезными концепции, изложенные в главе 22,) Теперь предположим, что каждому ребру (и, и) е Е также сопоставляется неотрицательная вероятность р(и, и) перехода по этому ребру из вершины и. При этом издается соответствующий звук. Сумма вероятностей по всем ребрам, исходящим из произвольной вершины, равна 1. По определению вероятность пути равна произведению вероятностей составляющих его ребер. Вероятность пути, берущего начало в вершине ио, можно рассматривать как вероятность "случайного блуждания", которое начинается в этой вершине и продолжается по случайному пути. Выбор каждого ребра на этом пути в вершине и производится в соответствии с вероятностями ребер„исходящих из этой вершины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
