Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 90

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 90)

п, 1 .. п], состоящая из вычисленных зна- ев зтом палладе предполагаетсл, что известен набор параметров всек возможнык подзадач и установлено соответствие мюкду лчейками таблицы и подзадачами Другой подкод состоит в том, чтобы организовать юпомииание с помощью кеюированил, в котором в качестве ключей выступают параметры подзадач. Часть Гк 'зсааершеистеаеаииые методы разработки и аказиза чений т[г, Я, которые представляют собой минимальное количество скалярных умножений, необходимых для вычисления матрицы А, .

Изначально каждый элемент таблицы содержит значение оо, указывающее на то, что данный элемент еще должен быть заполнен. Если при вызове процедуры Ьоохпр-Снлпч(т,р,з, з) в строке 1 выполняется условие го[с, 1] < оо, то эта процедура в строке 2 просто возвращает ранее вычисленную стоимость т[з,7]. В противном случае эта стоимость вычисляется так же, как и в процедуре Ккспкз!Ук-Млтк!х-Снл!н, сохраняется в элементе та[а, Я, после чего возвращается. Таким образом, процедура Ьоокпр-Снл!н(го,р,г,7) всегда возвращает значение т[г,7], но оно вычисляется лишь в том случае, если это первый вызов данной процедуры с этими параметрами 1 и ап На рис.

15.7 показано, насюлько эффективнее процедура Мкмоикп-Млтк!хСнлпч расходует время по сравнению с процедурой Кеспкз!Ук-Млтк!х-Снл!н. Затененные поддеревья представляют значения, которые вычисляются толью один раз. При возникновении повторной потребности в этих значениях вместо их вычисления осуществляется поиск в хранилище. Время работы процедуры Мимо!2но-Млтк!х-Снл!н, как и время выполнения алгоритма Млтк!х-Снл!н-Ококк, построенного по принципу динамического программирования, равно 0(пз).

Строка 5 процедуры Мимо!2ко-Млтк!хСнл!н выполняется ез(п ) раз. Все вызовы процедуры Ьоокпр-Снл!н можно разбить на два типа: 1. вызовы, в которых выполняется условие пз[г, з] = оо, так что выполняются строки 3-9; 2. вызовы, в которых выполняется условие т[1,7] < оо, так что процедура Ьоок~л'-Снл!н просто выполняет возврат в строке 2. Всего вызовов первого типа насчитывается ьз(пз), по одному на каждый элемент таблицы.

Все вызовы второго типа осуществляются как рекурсивные обращения из вызовов первого типа. Всякий раз, когда в некотором вызове процедуры Ьоокпр-Снл!н выполняются рекурсивные обращения, общее их количество равно 0(п). Поэтому в общем итоге производится 0(пз) вызовов второго типа, причем на каждый из них расходуется время 0(1). На каждый вызов первого типа требуется время 0(п) плюс время, затраченное на рекурсивные обращения в данном вызове первого типа.

Поэтому общее время равно 0(пз). Таким образом, запоминание преобразует алгоритм, время работы юторого равно П(2"), в алгоритм со временем работы О(пз). В итоге получается, что задачу об оптимальном способе перемножения цепочки матриц можно решить либо с помощью алгоритма с запоминанием, работающего в нисходящем направлении, либо с помощью динамичесюго прозраммирования в восходящем направлении. При этом в обоих случаях потребуется время, равное 0(пз).

Оба метода используют преимущество, возникающее благодаря перекрытию подзадач. Всего возникает только 1з(п~) различных подзадач, и в каждом из описанных выше методов решение каждой из них вычисляется один раз. Если не применять запоминание, то время работы обычного рекур- 423 Глава 45. Динамическое нраграммирование сивного алгоритма станет экспоненциальным, поскольку уже решенные задачи придется неоднократно решать заново. В общем случае, если все подзадачи необходимо решить хотя бы по одному разу, восходящий алгоритм, построенный по принципу динамического программирования, обычно работает быстрее, чем нисходящий алгоритм с запоминанием. Причины — отсутствие непроизводительных накладных расходов на рекурсию и их сокращение при поддержке таблицы.

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

Упражнения 15.3.1 Как эффективнее определить оптимальное количество скалярных умножений в задаче о перемножении цепочки матриц: перечислить все способы расстановки скобок в произведении матриц и вычислить количество скалярных умножений в каждом из них или запустить процедуру Кеспкзгче-Млтк!х-Сняп4? Обоснуйте ответ. 15.3.2 Изобразите рекурсивное дерево для процедуры Мекпе-ЗОкт, описанной в разделе 2.3А и работающей с массивом из 16 элементов. Объясните, почему для повышения производительности работы хорошего алгоритма "разделяй и властвуй", тавго как МЕКОЕ-БОКТ, использование запоминания не даст никакого улучшения производительности.

15.3.3 Рассмотрим разновидность задачи о перемножении цепочки матриц, цель которой — так расставить скобки в последовательности матриц, чтобы количество скалярных умножений стало не минимальным, а максимальным. Проявляется ли в этой задаче оптимальная подструктура? 15.3.4 Как говорилось выше, в динамическом программировании сначала решаются подзадачи, а затем выбираются те из них, которые будут использованы в оптимальном решении задачи. Профессор утверждает, что не всегда необходимо решать все подзадачи, чтобы найти оптимальное решение. Он выдвигает предположение о том, что оптимальное решение задачи о перемножении цепочки матриц можно найти, всегда выбирая матрицу Аы после которой следует разбивать произведение А,А,4.1 А (индекс и выбирается так, чтобы минимизировать величину р, 1рьр5) перед решением подзадач. Приведите пример задачи о перемножении цепочки матриц, в котором такой жадный подход приводит к решению, отличному ог оптимального.

Части 1Г Усовертеиствоваииые методы разработки и анализа 424 15.3.5 Предположим, что в задаче о разрезании стержня из раздела 15.1 имеется предельное значение (з юличества частей длиной з' (1 = 1,2,..., и), которое можно получить при разрезании одного стержня. Покажите, что свойство оптимальной подструктуры из раздела 15.1 в этом случае не выполняется.

15.3.6 Представим, что вы хотите обменять одну валклу на другую. Вы надеетесь на то, что если вместо непосредственного обмена выполнить несколько промежуточных обменов на другие валюты, то обмен получится более выгодным. Предположим, что можно выполнять обмен и различных валют, пронумерованных 1,2,...,п, причем вы начинаете с валюты 1 и хотите закончить валютой и. Для каждой пары валют 1 и л у вас имеется обменный курс тм, означающий, что если у вас есть с( единиц валюты г, то вы можете получить за них г(ггз единиц валюты л) Последовательность обменов может вызывать комиссионные сборы, зависящие от количества произведенных обменов.

Пусть сь — комиссионный сбор, который вы должны заплатить за зс обменов. Покажите, что, если сь = О для всех к = 1,2,..., и, то задача поиска наилучшей последовательности обменов валюты 1 на валюту и демонстрирует оптимальную подструктуру. Затем покажите, что если юмиссионные сборы сь имеют произвольные значения, то эта задача поиска наилучшей последовательности обменов валюты 1 на валюту п такой оптимальной подструктурой может и не обладать. 15.4. Наядляпиейшая общая подпоследовательпость В биологических приложениях часто возникает необходимость сравнить ДНК двух (или более) различных организмов.

Стандартная ДНК состоит из последовательности молекул, которые называются основаниями ()завез). К этим молекулам относятся: аденин (аз!еп!пе), гуанин (йцашпе), цитозин (су!огйпе) и тимин (!)зупппе). Если обозначить каяглое из перечисленных оснований его начальной буквой латинского алфавита, то стандартную ДНК можно представить в виде строки, состоящей из конечного множества элементов (А, С, 6, Т).

(Определение строки см. в приложении В.) Например, ДНК одного организма может иметь вид Яг = АССОСТССАСТССЯСССААЯСССССССАА а ДНК другого— 5з = атсаттсааААТССССТТССТСТСТААА Одна из целей сравнения двух ДНК состоит в том, чтобы выяснить степень их сходства. Это один из показателей того, насколько тесно связаны между собой два организма. Степень подобия можно определить многими способами.

Например, можно сказать, что два кода ДНК подобны, если один из них является подстрокой другого. (Алгоритмы, с помощью которых решается эта задача, исследуются в главе 32.) В нашем примере ни Яп ни Яз не является подстрокой другой ДНК. В этом случае можно сказать, что две цепочки молекул подобны, если для преобразования одной из них в другую потребовались бы толью небольшие изменения. (Такой подход рассматривается 425 Глава!5. Динамическое программирование в задаче 15.5.) Еше один способ определения степени подобия последовательностей Я1 и Яз заключается в поиске третьей последовательности Яз, основания которой имеются как в Яп так и в Яз, при этом они следуют в одном и том же порядке, но не обязательно одно за другим. Чем длиннее последовательность бз, тем более схожи последовательности Я1 и Яз.

Характеристики

Список файлов книги