Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 84
Текст из файла (страница 84)
Другая возможность — заполнить всю таблицу Д [)]. В этом случае можно было бы определить, какое рабочее место предшествует рабочему месту Ят на самом быстром пути, проходящем через рабочее место Ят зэ но на это потребовалось бы больше усилий. Если Гт [)] = Гт [) — 1] + ацз, то на самом быстром пути через рабочее место Ят ему предшествует рабочее место Яку 1. В противном случае должно выполняться соотношение ~т 'у] = 5з [) — 1]ф +Фзд т + а1,зэ и рабочему месту Ят„; предшествует рабочее место Язп и В задаче о составлении расписания работы сборочного конвейера на восстановление информации о предшествующем рабочем месте необходимо время, равное О (1) (на каждое рабочее место), даже если отсутствует таблица 1; [)].
Однако в задаче о перемножении цепочки матриц в процессе воссоздания оптимального решения, благодаря таблице л [з, )] удается значительно уменьшить обьем работы. Предположим, что таблица л [з, )] не поддерживается, а заполняется толью таблица пз [з, Я, в которой содержатся оптимальные стоимости вспомогательных задач. При выборе вспомогательной задачи, использующейся в оптимальном решении задачи о расстановке скобок в произведении АеАт» з ...
А, всего имеется ) — з вариантов выбора, и это юличество не является константой. Поэтому на восстановление сведений о том, какие вспомогательные задачи выбираются в процессе решения данной задачи, потребуется время, равное ΠΠ— з) = сэ(1). Сохраняя в элементе л [а, )] индекс, где выполняется разбиение произведения А;Аз+1 ... А, данные о каждом выборе можно восстановить за время О (1). Запоминание Одна из вариаций динамического программирования часто обеспечивает ту же степень эффективности обычного подхода динамического программирования, но при соблюдении нисходящей стратегии.
Идея заключается в том, чтобы запомнить (шешо)вез) обычный неэффективный рекурсивный алгоритм. Как и при В данном случае это не опечатка, по-английски этот термин пишется именно так. Как поясняет в примечании автор книги, смысл не просто в том, чтобы запомнить информацию (шегпопае), а в том, чтобы вскоре ею воспользоваться как памяткой (шешо). — Прим. лед. Глава 15. Динамическое программирование 415 обычном динамическом программировании, поддерживается таблица, содержащая решения вспомогательных задач. Однако структура, управляющая заполнением таблицы, больше напоминает рекурсивный алгоритм.
В рекурсивном алгоритме с запоминанием поддерживается элемент таблицы лля решения каждой вспомогательной задачи. Изначально в каждом таком элементе таблицы содержится специальное значение, указывающее на то, что данный элемент еще не заполнен. Если в процессе выполнения рекурсивного алгоритма вспомогательная задача встречается впервые, ее решение вычисляется и заносится в таблицу.
Каждый раз, когда снова будет встречаться эта вспомогательная задача, в таблице находится и возвращается ее решение4. Ниже приведена версия процедуры Кбсикяуб МАтнх СНАН4 с запоминанием: Мкмогбо МАтих СнинГр) 1 гз + — 1епдй(р] — 1 2 Гог з' — 1 1о гз 3 до Гогд — з 1оп 4 Йо т[з, 7] — со 5 гетпгп Ьоокнр СНА|н[р, 1, гз) ЬООКОР СНА!Х(р, з, 7) 1 1Г т[з, 7] < оо 2 Феп ге1пгп т[з, 7] 3 1Гз=2 4 Феп т(з', з] — 0 5 е1ае 1ог Гс - з 1о3 — 1 6 Йо д ь — Ьоокнр СВА!х(р, з, lс) + Ьоокир СВАлч(р, 7с + 1, 7) + р; зрйр.
1Г д < т(з,д] Феп т[з,д] — д 7 8 9 ге1пгп т(з, Я 4 В этом подходе предполагается, что известен набор параметров всех возможных вспомогательямх задач и установлено соответствие между ячейками таблицы и вспомогательными задачами. Другой подход состоит в том, чтобы организовать запоминание с помощью хеширования, в котором в качестве ключей выступают параметры вспомогательных задач.
В процедуре Мбмоыкп МАтщх СНАпч, как и в процедуре МАтщх СВА! н Окобк, поддерживается таблица т,[1..гз,1..гз], состоящая из вычисленных значений т (з, 7], которые представляют собой минимальное количество скалярных умножений, необходимых для вычисления матрицы А; . Изначально каждый элемент таблицы содержит значение оо, указывающее на то, что данный элемент еще должен быть заполнен. если при вызове процедуры ьоокнр снА|н(р, з', т) вы- 416 Часть 1Ч. Усовершенствованные методы разработки и анализа полняется условие т [г,Я < оо (строка 1), эта процедура просто возвращает ранее вычисленную стоимость т [г', Я (строка 2). В противном случае эта сто.
имость вычисляется так же, как и в процедуре Кеспкз!не Млтк1х Снлпч, сохраняется в элементе т [г, з], после чего возвращается. (Удобство использовании значения оо для незаполненных элементов таблицы объясняется тем, что это жа значение используется для инициализации элементов т [1, з] в строке 3 процедуры КЕСиКЗГЧЕ МЛтШХ СНЛПЧ.) Таким образом, процедура 1.ООК~Л' СНЛ1Н(р,1,1) всегда возвращает значение т [1, з], но оно вычисляется лишь в том случае, если это первый вызов данной процедуры с параметрами 1 и з.
Рнс. 15.5 иллюстрирует, насколько эффективнее процедура Мемоыеп Млтих Снлпч расходует время по сравнению с процедурой Кесокяче Млтщх Снлпч. Затененные поддеревья представляют значения, которые вычисляютса только один раз. При возникновении повторной потребности в этих значениях осуществляется их поиск в хранилище. Время работы процедуры Мемо1хео Млтк1х Снлпч, как и время выполнения алгоритма Млтк~х Снлпч Окоек, построенного по принципу динамического программирования, равно О [пз). Каждая ячейка таблицы (а всего их 9 (пз)) однократно инициализируется в строке 4 процедуры Мемояео Млтк1х Снлш, Все вызовы процедуры 1.оокик Снлпч можно разбить на два типа: 1.
вызовы, в которых справедливо соотношение т [г', з] = оо и выполняются строки 3 — 9; 2. вызовы, в которых выполняется неравенство т [1, з] < оо и просто происходит возврат в строке 2. Всего вызовов первого типа насчитывается О [пз), по одному на каждый элемент таблицы. Все вызовы второго типа осуществляются как рекурсивные обращения из вызовов первого типа.
Всякий раз, когда в некотором вызове процедуры 1.оОкик Снлпч выполняются рекурсивные обращения, общее их количество равно О (п). Поэтому в общем итоге производится О (пз) вызовов второго типа, причем на каждый из них расходуется время О (1). На каждый вызов первого типа требуется время О (п) плюс время, затраченное на рекурсивные обращения в данном вызове первого типа. Поэтому общее время равно О (пз). Таким образом, запоминание преобразует алгоритм, время работы которого равно П (2"), в алгоритм со временем работы О (пз). В итоге получается, что задачу об оптимальном способе перемножения цепочки матриц можно решить либо с помощью алгоритма с запоминанием, работающего в нисходящем направлении, либо с помощью динамического программирования в восходящем направлении.
При этом в обоих случаях потребуется время, равное О (пз). Оба метода используют преимущество, возникающее благодаря перекрыванию вспомогательных задач. Всего возникает только 9 (пз) различных вспомогательных задач, и в каждом из описанных выше методов решение каждой Глава 15. Динамическое программирование 417 из них вычисляется один раз. Если не применять запоминание, то время работы обычного рекурсивного алгоритма станет экспоненциальным, поскольку уже решенные задачи придется неоднократно решать заново.
В общем случае, если все вспомогательные задачи необходимо решить хотя бы по одному разу, восходящий алгоритм, построенный по принципу динамического программирования, обычно работает быстрее, чем нисходящий алгоритм с запоминанием. Причины — отсутствие непроизводительных затрат на рекурсию и их сокращение при поддержке таблицы. Более того, в некоторых задачах после определенных исследований удается сократить время доступа к таблице или занимаемый ею обьем. Если же можно обойтись без решения некоторых вспомогательных задач, содержащихся в пространстве подзадач данной задачи, запоминание результатов решений обладает тем преимуществом, что решаются только необходимые вспомогательные задачи. Упражнения 15.3-1.
Как эффективнее определить оптимальное количество скалярных умножений в задаче о перемножении цепочки матриц: перечислить все способы расстановки скобок в произведении матриц и вычислить количество скалярных умножений в каждом из них или запустить процедуру йесикШуи Млтя1Х СНАПЧ? Обоснуйте ответ.
15.3-2. Нарисуйте рекурсивное дерево для процедуры Минов Яокт, описанной в разделе 2.3.1, работающей с массивом из 16 элементов. Объясните, почему для повышения производительности работы хорошего алгоритма разбиения, такого как Мвкои Яокт, использование запоминания не будет эффективным. 15.3-3. Рассмотрим разновидность задачи о перемножении цепочки матриц, цель которой — так расставить скобки в последовательности матриц, чтобы количество скалярных умножений стало не минимальным, а максимальным. Проявляется ли в этой задаче оптимальная подструктура? 153-4. Опишите, какие перекрывающиеся вспомогательные задачи возникают при составлении расписания работы конвейера. 15.3-5.
Согласно сделанному выше утверждению, в динамическом программировании сначала решаются вспомогательные задачи, а потом выбираются те из них, которые будут использованы в оптимальном решении задачи. Профессор утверждает, что не всегда необходимо решать все вспомогательные задачи, чтобы найти оптимальное решение.
Он выдвигает предположение, что оптимальное решение задачи о перемножении цепочки матриц можно найти, всегда выбирая матрицу Аы после которой следует разбивать произведение А,А,+1... А (индекс й выбирается Часть 1Ч. Усовершенствованные методы разработки н анализа 418 так, чтобы минимизировать величину р; 1рьр ) веред решением вспомогательных задач. Приведите пример задачи о перемножении цепочки матриц, в котором такой жадный подход приводит к решению, отличному от оптимального. 15.4 Самая длинная общая подпоследовательность В биологических приложениях часто возникает необходимость сравнить ДНК двух (или большего количества) различных организмов. Стандартная ДНК состоит из последовательности молекул, которые называются основаниями (Ьазез).
К этим молекулам относятся: аденин (ас1ешпе), гуанин (йиашпе), цитозин (суьоыпе) и тимин (ьЬуш1пе). Если обозначить каждое из перечисленных оснований его начальной буквой латинского алфавита, то стандартную ДНК можно представить в виде строки, состоящей из конечного множества элементов (А, С, С,Т). (Определение строки см.
в приложении В.) Например, ДНК одного организма может иметь вид 51 = АСС66ТССА6ТОСССС6ААССССССС6АА, а ДНК другого— Вз = СТССТТСССААТССССТТССТСТСТААА. Одна из целей сравнения двух ДНК состоит в том, чтобы выяснить степень их сходства. Это один из показателей того, насколько тесно связаны между собой два организма. Степень подобия можно определить многими различными способами. Например, можно сказать, что два кода ДНК подобны, если один из них является подстрокой другого. (Алгоритмы, с помощью которых решается эта задача, исследуются в главе 32.) В нашем примере ни Ям ни Вз не является подстрокой другой ДНК.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
