Алгоритмы - построение и анализ (1021735), страница 80
Текст из файла (страница 80)
Например, пространство в подзадачах, возникающих в задаче о составлении расписания работы конвейера, было образовано самым быстрым путем прохождения шасси от начала конвейера до рабочего места Я~ или Яэ . Это подпространство оказалось вполне подходящим, н не возникло необходимости его расширять. Теперь предположим, что в задаче о перемножении цепочки матриц производится попытка ограничить пространство подзадач произведением вида А~Аз... А .
Как и раньше, оптимальная расстановка скобок должна разбивать произведение между матрицами Аь и Аяез для некоторого индекса 1 < )с < т1 Если й не всегда равно з — 1, мы обнаружим„что возникают вспомогательные задачи в виде А~Аз... Аь и Аь~ ~Ая+э... Ау и что последняя подзадача не является подзадачей вида А~Аз... А . В этой задаче необходима возможность изменения обоих концов последовательности, т.е. чтобы во вспомогательной задаче А;А; ~з... А могли меняться оба индекса, — и г, и з1 Оптимальная подструктура изменяется в области определения задачи в двух аспектах: 1. количество вспомогательных задач, которые используются при оптимальном решении исходной задачи; 2, количество выборов, возникающих при определении того, какая вспомогательная задача (задачи) используется в оптимальном решении.
В задаче о составлении расписания работы конвейера в оптимальном решении используется только одна вспомогательная задача, и для поиска оптимального решения необходимо рассмотрение двух вариантов. Чтобы найти самый быстрый Глава 15. Динамическое программирование 407 путь через рабочее место Я;д, мы используем либо самый быстрый путь через рабочее место 5~ и либо самый быстрый путь через рабочее место Яз Каждый из вариантов представляет одну вспомогательную задачу, для которой необходимо найти оптимальное решение.
Перемножение вспомогательной цепочки матриц А;А;» з...А. — пример, в котором возникают две вспомогательные задачи и 7' — г вариантов выбора. Если задана матрица Аы у которой происходит разбиение произведения, то возникают две вспомогательные задачи — расстановка скобок в подпоследовательностях А;А;» з... Аь и Аь» зАь» з... А, причем для калсдой из них необходимо найти оптимальное решение. Как только оптимальные решения вспомогательных задач найдены, выбирается один из у — г вариантов индекса Й.
Если говорить неформально, время работы алгоритма динамического программирования зависит от произведения двух множителей: общего количества вспомогательных задач и количества вариантов выбора, возникающих в каждой вспомогательной задаче. При составлении расписания работы сборочного конвейера у нас всего возникало Й (и) вспомогательных задач и лишь два варианта выбора, которые нужно было проверить. В результате получается, что время работы алгоритма ведет себя как О (и).
При перемножении матриц всего возникало 6 (пз) вспомогательных задач, и в каждой из них — не более п — 1 вариантов выбора, поэтому время работы алгоритма ведет себя как О (пз). Оптимальная подструктура используется в динамическом программировании в восходящем направлении. Другими словами, сначала находятся оптимальные решения вспомогательных задач, после чего определяется оптимальное решение поставленной задачи. Поиск оптимального решения задачи влечет за собой необходимость выбора одной из вспомогательных задач, которые будут использоваться в решении полной задачи.
Стоимость решения задачи обычно определяется как сумма стоимостей решений вспомогательных задач и стоимости, которая затрачивается на определение правильного выбора. Например, при составлении расписания работы сборочного конвейера сначала решались вспомогательные задачи по определению самого быстрого пути через рабочие места Я~ г и Яз и а потом одна нз них выбиралась в качестве предыдущей для рабочего места Яз . Стоимость, которая относится к самому выбору, зависит от того, происходит ли переход от одного конвейера к другому между рабочими местами у' — 1 и ~.
Если шасси остается на одном и том же конвейере, то эта стоимость равна а;, а если осуществляется переход от одного конвейера к другому — она равна Ф;; г + а;оч где з' ф г'. В задаче о перемножении цепочки матриц сначала был определен оптимальный способ расстановки скобок во вспомогательной цепочке А;А;+~...
А, а потом была выбрана матрица Аь, у которой выполняется разбиение произведения. Стоимость, которая относится к самому выбору, выражается членом р; ~рьр . В главе 16 рассматриваются жадные алгоритмы, имеющие много общего с динамическим программированием. В частности, задачи, к которым применимы Часть 1Ч.
Усовершенствованные методы разработки и анализа 408 жадные алгоритмы, обладают оптимальной подструкгурой. Одно из характерных различий между жадными алгоритмами и динамическим программированием заключается в том, что в жадных алгоритмах оптимальная подструктура используется в нисходящем направлении. Вместо того чтобы находить оптимальные решения вспомогательных задач с последующим выбором одного из возможных вариантов, в жадных алгоритмах сначала делается выбор, который выглядит наилучшим на текущий момент, а потом решается возникшая в результате вспомогательная задача. Некоторые тонкости Следует быть особенно внимательным в отношении вопроса о применимости оптимальной подструктуры, когда она отсутствует в задаче.
Рассмотрим такие две задачи, в которых имеется ориентированный граф ся = ()г, Е) и вершины и, и Е Г Задача о кратчайшем невзвешенном пути'. Нужно найти путь от вершины и к вершине и, состоящий из минимального количества ребер. Этот путь обязан быть простым, поскольку в результате удаления из него цикла получается путь, состоящий из меньшего количества ребер. Задача о самом длинном невзвешенном пути. Определите простой путь от вершины и к вершине и, состоящий из максимального количества ребер.
Требование простоты весьма важно, поскольку в противном случае можно проходить по одному и тому же циклу сколько угодно раз, получая в результате путь, состоящий нз произвольного количества ребер. В задаче о кратчайшем пути возникает оптимальная подструктура. Это можно показать с помощью таких рассузклений. Предположим, что и ф и и задача является нетривиальной. В этом случае любой путь р от и к и должен содержать промежуточную вершину, скажем, зл.
(Заметим, что вершина зн может совпадать с вершиной и или и.) Поэтому путь и - и можно разложить на вспомогательные Р1 Рз пути и - зн - ш Очевидно, что количество ребер, входящих в путь р, равно сумме числа ребер в путях рз и рз. Утверждается, что если путь р от вершины и к вершине н оптимальный (т.е. кратчайший), то р1 должен быть кратчайшим путем от вершины и к вершине зл. Почему? Аргумент такой: если бы существовал другой путь, соединяющий вершины и и о и состоящий из меньшего количества ребер, чем рь скажем, р',, можно было бы вырезать путь р1 и вставить путь / Р1 рз р,, в результате чего получился бы путь и - ю - и, состоящий из меньшего количества ребер, чем путь р.
А это противоречит предположению об оптимальности пути р. Аналогично, рз должен быть кратчайшим путем от вершины ш ' Гсрмш1 "псвзвсшснный" испол ьзустся, чтобы отличать эту задачу от той, при которой находится кратчайший путь на взвсшснных рсбрах, с которой мы ознакомимся в главах 24 и 25. Для решения задачи о нсвзвсшснном пути можно использовать метод поиска в ширину, описанный в главе 26 Глава 15. Динамическое программирование 409 ~ ф~„~,У Рис. 15.4.
Пример, демонстрирующий отсутствие оптимальной подструктуры в задаче о поиске самого длинного простого пути к вершине ш Таким образом, кратчайший путь от вершины и к вершине о можно найти, рассмотрев все промежуточные вершины ш, отыскав кратчайший путь от вершины и к вершине ю и кратчайший путь от вершины ш к вершине с, н выбрав промежуточную вершину ш, через которую весь путь окажется кратчайшим. В разделе 25.2 один из вариантов этой оптимальной подструктуры используется для поиска кратчайшего пути между всеми парами вершин во взвешенном ориентированном графе.
Напрашивается предположение, что в задаче поиска самого длинного простого невзвешенного пути тоже проявляется оптимальная подструктура. В конце концов, если разложить самый длинный простой путь и - с на вспомогательные пути и - ю - с, то разве не должен путь р~ быть самым длинным простым ну~ем от Р1 Рз вершины и к вершине ш, а путь рз — самым длинным простым путем от вершины ш к вершине с? Оказывается, нет! Пример такой ситуации приведен на рнс. 15.4.
Рассмотрим путь д — г — 1, который является самым длинным простым путем от вершины д к вершине 1. Является ли путь д — г самым длинным путем от вершины д к вершине г? Нет, поскольку простой путь 9 — а — ~ — г длиннее. Является ли путь т — 1 самым длинным путем от вершины г к вершине г? Снова нет, поскольку простой путь т — д — а — 8 длиннее.
Этот пример демонстрирует, что в задаче о самых длинных простых путях не только отсутствует оптимальная подструктура, но и не всегда удается составить "законное" решение задачи из решений вспомогательных задач. Если сложить самые длинные простые пути 9 — а — 1 — г и г — д — а — 1, то получим путь д — а — 1 — т — д — а — ~, который не является простым. Итак, на деле оказывается, что в задаче о поиске самого длинного невзвешенного пути не возникает никаких оптимальных подструктур.
Для этой задачи до сих пор не найдено ни одного эффективного алгоритма, работающего по принципу динамического программирования. Фактически, это ХР-полная задача, что означает — как будет показано в главе 34 — что вряд ли ее можно решить в течение полиномиального времени. Что можно сказать по поводу структуры самого длинного простого пути, так отличающейся от структуры самого короткого пути? Несмотря на то, что 410 Часть 1Ч. Усовершенствованные методы разработки и анализа в решениях задач о поиске и самого короткого, и самого длинного пути возникают две вспомогательные задачи, вспомогательные задачи при определении самого длинного пути не являются независимыми, в то время как в задаче о кратчайшем пути они независимы.
Что подразумевается под независимостью вспомогательных задач? Подразумевается, что решение одной вспомогательной задачи не влияет на решение другой вспомогательной задачи, возникающей в той же задаче. В примере, проиллюстрироваином на рис. 15.4, рассматривается задача о поиске самого длинного простого пути между вершинами д и 8, в которой возникают две вспомогательные задачи: определение самых длинных простых путей между вершинами д и г и между вершинами г и 1. Для первой из этих вспомогательных задач выбирается путь о — л — 1 — г, в котором используются вершины л и $.