Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 82
Текст из файла (страница 82)
Можно видеть, что поиск оптимальной подструктуры происходит по общему образцу. 1. На первом этапе следует показать, что в процессе решения задачи приходится делать выбор. В рассмотренных примерах это был выбор рабочего места на конвейере или выбор индекса, при котором разбивается последовательность матриц. После выбора остается решить одну или несколько вспомогательных задач. 2.
На этом этапе мы исходим из того, что для поставленной задачи делается выбор, ведущий к оптимальному решению. Пока что не рассматривается, как именно следует делать выбор, а просто предполагается, что он найден. Часть!У. Усовершенствованные методы разработки и анализа 406 3. Исходя из предположения предыдущего этапа, определяется, какие вспомогательные задачи получаются и как лучше охарактеризовать получающееся в результате пространство подзадач. 4.
Показывается, что решения вспомогательных задач, возникающих в ходе оптимального решения задачи, сами должны быть оптимальными. Это делается методом "от противного": предполагая, что решение каждой вспомогательной задачи не оптимально, приходим к противоречию. В частности, путем "вырезания" неоптимального решения вспомогательной задачи и "вставки" оптимального демонстрируется, что можно получить лучшее решение исходной задачи, а это противоречит предположению, что уже имеется оптимальное решение. Если вспомогательных задач несколько, они обычно настолько похожи, что описанный выше способ рассуждения, примененный к одной из вспомогательных задач, легко модифицируется для остальных.
Характеризуя пространство подзадач, постарайтесь придерживаться такого практического правила: попытайтесь, чтобы это пространство было как можно проще, а потом расширьте его до необходимых пределов. Например, пространство в подзадачах, возникающих в задаче о составлении расписания работы конвейера, было образовано самым быстрым путем прохождения шасси от начала конвейера до рабочего места Я~ или Яэ .
Это подпространство оказалось вполне подходящим, н не возникло необходимости его расширять. Теперь предположим, что в задаче о перемножении цепочки матриц производится попытка ограничить пространство подзадач произведением вида А~Аз... А . Как и раньше, оптимальная расстановка скобок должна разбивать произведение между матрицами Аь и Аяез для некоторого индекса 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
