Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 83
Текст из файла (страница 83)
Рассмотрим путь д — г — 1, который является самым длинным простым путем от вершины д к вершине 1. Является ли путь д — г самым длинным путем от вершины д к вершине г? Нет, поскольку простой путь 9 — а — ~ — г длиннее. Является ли путь т — 1 самым длинным путем от вершины г к вершине г? Снова нет, поскольку простой путь т — д — а — 8 длиннее.
Этот пример демонстрирует, что в задаче о самых длинных простых путях не только отсутствует оптимальная подструктура, но и не всегда удается составить "законное" решение задачи из решений вспомогательных задач. Если сложить самые длинные простые пути 9 — а — 1 — г и г — д — а — 1, то получим путь д — а — 1 — т — д — а — ~, который не является простым.
Итак, на деле оказывается, что в задаче о поиске самого длинного невзвешенного пути не возникает никаких оптимальных подструктур. Для этой задачи до сих пор не найдено ни одного эффективного алгоритма, работающего по принципу динамического программирования. Фактически, это ХР-полная задача, что означает — как будет показано в главе 34 — что вряд ли ее можно решить в течение полиномиального времени. Что можно сказать по поводу структуры самого длинного простого пути, так отличающейся от структуры самого короткого пути? Несмотря на то, что 410 Часть 1Ч.
Усовершенствованные методы разработки и анализа в решениях задач о поиске и самого короткого, и самого длинного пути возникают две вспомогательные задачи, вспомогательные задачи при определении самого длинного пути не являются независимыми, в то время как в задаче о кратчайшем пути они независимы.
Что подразумевается под независимостью вспомогательных задач? Подразумевается, что решение одной вспомогательной задачи не влияет на решение другой вспомогательной задачи, возникающей в той же задаче. В примере, проиллюстрироваином на рис. 15.4, рассматривается задача о поиске самого длинного простого пути между вершинами д и 8, в которой возникают две вспомогательные задачи: определение самых длинных простых путей между вершинами д и г и между вершинами г и 1. Для первой из этих вспомогательных задач выбирается путь о — л — 1 — г, в котором используются вершины л и $. Во второй вспомогательной задаче мы не сможем больше использовать эти вершины, поскольку в процессе комбинирования решений этих двух вспомогательных задач получился бы путь, который не является простым.
Если во второй задаче нельзя использовать вершину 1, то ее вообще невозможно будет решить, поскольку эта вершина должна быть в найденном пути, и это не та вершина, в которой "соединяются*' решения вспомогательных задач (этой вершиной является г). Использование вершин а и 1 в решении одной вспомогательной задачи приводит к невозможности их применения в решении другой вспомогательной задачи. Однако для ее решения необходимо использовать хотя бы одну из них, а в оптимальное решение данной вспомогательной задачи входят обе эти вершины.
Поэтому эти вспомогательные задачи не являются независимыми. Другими словами, использование ресурсов в решении одной вспомогательной задачи (в качестве ресурсов выступают вершины) делают их недоступными в другой вспомогательной задаче. Почему же вспомогательные задачи остаются независимыми при поиске самого короткого пути? Ответ такой: по самой природе поставленной задачи возникающие в ней вспомогательные задачи не используют одни и те же ресурсы. Утверждается, что если вершина и находится на кратчайшем пути р от вершины ю и к вершине о, то можно соединить любой кратчайший путь и - ю с любым кратчайшим путем ю - о, получив в результате самый короткий путь от вершины и к вершине с. Мы уверены в том, что пути рз и рз не содержат ни одной общей вершины, кроме ш.
Почему? Предположим, что имеется еще некоторая вершина х ф и, принадлежащая путям р~ и рз, так что путь рг можно разложить как и - х - ш, а путь рз — как ю - х - и. В силу оптимальной подструктуры этой задачи количество ребер в пути р равно сумме количеств ребер в путях рз и рз. Предположим, что путь р содержит е ребер.
Теперь построим путь и -"-* х -*.' е от вершины и к вершине с. В этом пути содержится не более е — 2 вершин, что противоречит предположению о том, что путь р — кратчайший. Таким образом, Глава 15. Динамическое программирование мы убедились, что вспомогательные задачи, возникаюшие в задаче поиска кратчайшего пути, являются независимыми. Подзадачи„возникающие в задачах, которые рассматриваются в разделах 15.1 и 15.2, являются независимыми.
При перемножении цепочки матриц, вспомогательные задачи заключались в перемножении подцепочек АеАе+з... Аь и Аь+гАь+з... А . Это непересекающиеся подцепочки, которые не могут содержать общих матриц. При составлении расписания конвейера для определения самого быстрого пути через рабочее место о; осуществлялся поиск самого быстРого пУги чеРез Рабочие места Ягд т и Яз и ПосколькУ Решение (т.е. самый быстрый путь через рабочее место Яе ) содержит только одно из решений этих подзадач, данная подзадача автоматически независима от всех других подзадач, использующихся в этом решении. Перекрытие вспомогательных задач Вторая составляющая часть, наличие которой необходимо для применения динамического программирования, заключается в том, что пространство вспомогательных задач должно быть "небольшим" в том смысле, что в результате выполнения рекурсивного алгоритма одни и те же вспомогательные задачи решаются снова и снова, а новые вспомогательные задачи не возникают.
Обычно полное ко- личество различающихся вспомогательных задач выражается как полиномиальная функция от объема входных данных. Когда рекурсивный алгоритм снова и снова обращается к одной и той же задаче, говорят, что задача оптимизации содержит перекрывающиеся вспомогательные задачи (очег!арр1пд зпЬргоЬ1етз)з. В отличие от описанной выше ситуации, в задачах, решаемых с помощью алгоритма разбиения, на каждом шаге рекурсии обычно возникают полностью новые задачи. В алгоритмах динамического программирования обычно используется преимушество, заключающееся в наличии перекрывающихся вспомогательных задач. Это достигается путем однократного решения каждой вспомогательной задачи с последующим сохранением результатов в таблице, где при необходимости их можно будет найти за фиксированное время.
В разделе 15.1 было показано, что в рекурсивном решении задачи о составлении расписания работы конвейера осуществляется 2" 1 обращений к Г; [1] для 1 = 1,2,..., кь Путем использования таблицы, содержащей результаты решений вспомогательных задач, экспоненциальное время работы алгоритма удается свести к линейному. Может показаться странным, что вспомогательные задачи, использующиеся в динамическом программировании, являются и независимыми, и перекрывающимися.
Эти требования могут показаться противоречащими друг другу, однако зто не так, поскольку они относятся к разным понятиям. Две вспомогательные задачи одной и той же задачи независимы, если в них не используются общие ресурсы. Две вспомогательные задачи перекрынаются, если на самом деле речь идет об одной и той же вспомогательной задаче, возникающей в разных задачах. Часть 1У. Усовершенствованные методы разработки и анализа 412 Чтобы подробнее проиллюстрировать свойство перекрывания вспомогательных задач, еще раз обратимся к задаче о перемножении цепочки матриц.
Возвратимся к рис. 15.3. Обратите внимание, что процедура МАтих СнАпч Окпеа в процессе решения вспомогательных задач в более высоких строках постоянно обращается к решениям вспомогательных задач в более низких строках. Например, к элементу т [3, 4] осуществляется 4 обращения: при вычислении элементов т[2,4], т[1,4]„т[3,5) и па[3,6). Если бы элемент тп [3,4) каждый раз приходилось каждый раз вычислять заново, а не просто находить в таблице, это привело бы к значительному увеличению времени работы.
Чтобы продемонстрировать это, рассмотрим приведенную ниже (неэффективную) рекурсивную процедуру, в которой определяется величина гп [г', з], т.е. минимальное количество скалярных умножений, необходимых для вычисления произведения цепочки матриц А; = АьА,+!... Ау. Эта процедура основана непосредственно на рекуррентном соотношении (15.12): Кеснкз!че МАтих СнА!н(р,(, !) 1 1!1=7' 2 Гаев гегпгп 0 3 т[(,Я вЂ” оо 4 Гог 1в — г' Го 2 — 1 5 до д Кес!!кз!че МАтих СнАпч(р,(,й) + Кеснкз!че МАтк!х СнА!н(р, !в+ 1,2) + Р!-!Рьру 6 Ы д ( т[г, 7] 7 1пеп гни, у] — д 8 геапгп т[1, з] На рис. 15.5 показано рекурсивное дерево, полученное в результате вызова процедуры кесикз!че мАтих снА!н(р, 1, 4). каждый его узел обозначен величинами параметров 1 и з1 Вычисления, которые производятся в части дерева, выделенной серым фоном, заменяются в процедуре Мемо!ее!э МАтих СнА!н(р, 1, 4).
Обратите внимание, что некоторые пары значений встречаются много раз. Можно показать, что время вычисления величины т [1, и) в этой рекурсивной процедуре, как минимум, экспоненциально по и. Обозначим через Т(п) время, которое потребуется процедуре Кесокз!че МАтих СнА!н для вычисления оптимального способа расстановки скобок в цепочке, состоящей из и матриц. Если считать, что выполнение каждой из строк 1-2 и б-7 требует как минимум единичного интервала времени, то мы получим такое рекуррентное соотношение: Т(1) > 1, и-1 Т (и) > 1 + ~ (Т (1в) + Т (и — lс) + 1) при и > 1. Глава 15. Динамическое программирование 413 ) ! 4 э;.4;,„: Л / З .' 3 ! . '3:Флз '1 Г~ '2,; ': "":;ъ.'-':'";:.*'4:.'4''::.1,.,"., З.Г. '!:;" '.3 : к~ 3 з д,л,.'1" '.А:,з'-, 9" ' ' '" ". з Рис.
15.5. Рекурсивное дерево, соответствующее вызову процедуры Кксиа- Яче МАтазх СнАлч(р, 1,4) л-1 Т(п) > 2 ,'> Т(1) + и. ~=1 (15.13) Докажем с помощью метода подстановок, что Т(п) = П (2"). В частности, покажем, что для всех и > 1 справедливо соотношение Т (п) > 2" '. Очевидно, что базисное соотношение индукции выполняется, поскольку Т(1) > 1 = 2". Далее, по методу математической индукции для и > 2 имеем Т(п) > 2~2' ~+и= 2 ~> 2'+и = 2(2" ~ — 1) +и = (2" — 2)+и > 2" =о На этом доказательство завершено. Таким образом, полное количество вычислений, которые выполняются при вызове процедуры Кнсикячн Млтих СнАнч(р, 1, п), как минимум, экспоненциально зависит от п.
Сравним этот нисходящий рекурсивный алгоритм с восходящим алгоритмом, построенным по принципу динамического программирования. Последний работает эффективнее, поскольку в нем используется свойство перекрывающихся вспомогательных задач. Всего возникает 6 (п~) различных вспомогательных задач, и в алгоритме, основанном на принципах динамического программирования, каждая нз них решается ровно по одному разу. В рекурсивном же алгоритме каждую вспомогательную задачу необходимо решать всякий раз, когда она возникает в рекурсивном дереве.
Каждый раз, когда рекурсивное дерево для обычного рекурсивного решения задачи несколько раз включает в себя одну и ту же вспомогательную Если заметить, что при 4 = 1, 2,..., п — 1 каждое слагаемое Т (1) один раз появ- ляется как Т (к) и один раз как Т (и — к), и просуммировать п — 1 единиц с той, которая стоит слева от суммы, то рекуррентное соотношение можно переписать в виде Часть!Ч. Усовершенствованные методы разработки и анализа 414 задачу, полезно проверить, нельзя ли воспользоваться динамическим программи- рованием. Построение оптимального решения На практике зачастую мы сохраняем сведения о том, какой выбор делается в каждой вспомогательной программе, так что впоследствии нам не надо дополнительно решать задачу восстановления этой информации. В задаче о составлении расписания работы сборочного конвейера в элементе 1т [т] сохранялся номер рабочего места, предшествующего рабочему месту Яг; на самом быстром пути через это рабочее место.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
