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

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

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

Первоначальный вызов процедуры Рщнт-ОРт1МАе-РАкемз(в,1, п) выводит оптимальную расстановку сюбок в последовательности (А1, Аз,..., А„). Рк!мт-ОРт!мА1.-РАкехз(в,1, !) В!==1 2 рппг "А"; 3 е1зе рпп1 "('* 4 РК1НТ-ОРТ1МАь-РАКЕНЯ(в, г, в[!,5]) 5 РК!ХТ-ОРТ!МАЕ-РАКЕНЯ(в, в[1,5] + 1, 1) 6 рппг ")" В примере, проиллюстрированном на рис. 15.5, вызов процедуры РкпчтОрт!МА~.-РАкенз(в, 1,6) дает строку ((А1(АзАз))((А4Аь)Ае)). Упражнения 15.2.1 Найдите оптимальную расстановку скобок в произведении последовательности матриц, размерности которых равны (5, 10, 3, 12, 5, 50, 6). 15.2.2 Разработайте рекурсивный алгоритм млтк1х-снА1н-мтл.т1Реу(А, в,1,5), в котором оптимальным образом вычисляется произведение заданной последовательности матриц (А1, Аз,..., А„).

На вход этого алгоритма, кроме того, поступают индексы 1 и 1, а также таблица в, вычисленная с помощью процедуры МАтк1хСнА1м-Окпек. (Начальный вызов этой процедуры выглядит следующим образом; МАтк!х-СНА!н-М~л.т1Р1л'(А, в, 1, п).) 15.2З Покажите с помощью метода подстановок, что решением рекуррентного соотношения (15.6) является П(2"). 15.2.4 Опишите граф подзадач для перемножения цепочки матриц для входной цепочки длиной и. Сколью вершин в этом графе? Сюлью в нем ребер, и что они собой представляют? 15.2.5 Пусть 11(1,5) — количество обращений к элементу матрицы го[1,5], которые выполняются в ходе вычисления других элементов этой матрицы в процедуре МАТК!х-СнА1м-Окпек.

Покажите, что полное количество обращений ко всем 4з'з Часть |И усовершенстеованные методы разработки и анази т элементам равно (Укаэаниез для решения может оказаться полезным уравнение 1А.З).) 15.2. б Покажите, что в полной расстановке скобок в и-элементном выражении используется ровно и — 1 пар скобок. 15.3.

Элементы динамического программирования Несмотря на рассмотренные в предыдущем разделе два примера, в которых применялся метод динамического программирования, возможно, вам все еще не совсем понятно, когда применим этот метод. В каких случаях задачу можно решать с помощью динамического программирования? В данном разделе рассматриваются два ключевых ингредиента, которые должны быть присущи задаче оптимизации, чтобы к ней можно было применить метод динамического программирования: наличие оптимальной подструктуры и перекрывающихся подзадач. Мы также более полно рассмотрим метод запоминания (шешо1га11оп) и изучим, каким образом он позволяет воспользоваться преимуществами перекрывающихся подзадач при нисходящем рекурсивном подходе.

Оптимальная подструктура Первый шаг решения задачи оптимизации методом динамического программирования состоит в том, чтобы охарактеризовать структуру оптимального решения. Напомним, что оптимальная падслзруклзуря проявляется в задаче в том случае, если в ее оптимальном решении содержатся оптимальные решения подзадач. Если в задаче выявлена оптимальная подструктура, это служит веским аргументом в пользу того, что к ней может быть применим метод динамического программирования. (Однако наличие этого свойства может также свидетельствовать о применимости жадных алгоритмов; см.

главу 16.) В динамическом программировании оптимальное решение задачи строится из оптимальньгх решений подзадач. Следовательно, необходимо убедиться в том, что в число рассматриваемых подзадач входят те, которые используются в оптимальном решении. Оптимальная подструктура была обнаружена в обеих задачах, которые до этого были исследованы в настоящей главе.

В разделе 15.1 было установлено, что оптимальное разрезание стержня длиной и 1если разрезание вообще имеет место) включает оптимальные разрезания частей, появившихся в результате первого разреза. В разделе 15.2 было продемонстрировано, что в оптимальную расстановку скобок, в результате которой последовательность матриц А,А,11 А разбивается на подпоследовательности между матрицами Аь и А1, „1, входят оптималь- Глава 15.

Динамическое нрограммирование иые решения задач о расстановке скобок в подпоследовательностях А,Аиь5 . Ан я А~~-1 Аьв.г . Аэ. Можно видеть, что поиск оптимальной подструктуры происходит по общему образцу. 1. На этапе 1 следует показать, что в процессе решения задачи приходится делать выбор. В рассмотренных примерах это был выбор начального разреза стержня или выбор индекса, при котором разбивается последовательность матриц.

После выбора остается решить одну или несколько подзадач. 2. На этом этапе мы исходим из того, что для поставленной задачи делается выбор, ведущий к оптимальному решению. Пока что не рассматривается, как именно следует делать выбор, а просто предполагается, что он найден. 3. Исходя из заданного выбора определяется, какие подзадачи получаются и как лучше охарактеризовать получающееся в результате пространство подзадач.

4. Показывается, что решения подзадач, возникающих в ходе оптимального решения задачи, сами должны быть оптимальными. Это делается методом "от противного": предполагая, что решение каждой подзадачи не оптимально, приходим к противоречию. В частности, путем "вырезания" неоптимального решения подзадачи и "вставки" оптимального демонстрируется, что можно получить лучшее решение исходной задачи, а это противоречит предположению о том, что уже имеется оптимальное решение. Если подзадач несколько, оии обычно настолько похожи, что описанный выше способ рассуждения, примененный к одной из подзадач, легко модифицируется для остальных.

Характеризуя пространство подзадач, постарайтесь придерживаться такого практического правила: попытайтесь сделать так, чтобы это пространство было как можно проще, а затем расширьте его до необходимых пределов. Например, пространство в подзадачах„возникающих в задаче о разрезании стержня, было образовано задачами оптимального разрезания стержня длиной в для каждого размера 1. Это подпространство оказалось вполне подходящим, и не возникло необходимости его расширять. Теперь предположим, что в задаче о перемножении цепочки матриц предпринимается попытка ограничить пространство подзадач произведениями вида А~ Аз .

А . Как и ранее, оптимальная расстановка скобок должна разбивать произведение междУ матРицами Ан и Аьн.~ Лла некотоРого индекса 1 ( й < 51 Если lс не всегда равно 5 — 1, мы обнаружим, что возникают подзадачи вида АзАэ . Аь и Анв.лАв+з А и что последняя подзадача не является подзадачей вида АзАз .. А .. В этой задаче необходима возможность изменения обоих концов последовательности, те. чтобы в подзадаче А,А, кв А могли меняться оба индекса — и в, и 51 Оптимальная подструктура изменяется в области определения задачи в двух аспектах.

!. Количество подзадач, которые используются при оптимальном решении исходной задачи. 4!4 Часть |У. 'зсовершенствованные методы разработки и аназшо 2. Количество выборов, возникающих при определении того, какая подзадача (подзадачи) используется в оптимальном решении.

В оптимальном решении задачи о разрезании стержня длиной п используется только одна подзадача размером п — з, но для поиска оптимального решения необходимо рассмотрение и вариантов значения з'. Перемножение подцепочкн матриц АеА;ьз Аз служит примером с двумя подзадачами и з — з вариантами выбора. Если задана матрица Аы у которой происходит разбиение произведения, то возникают две подзадачи — расстановка скобок в подпоследовательностях А,Аз~з Аь и Аь~1Аь >з А, причем для каждой из них необходимо найти оптимальное решение.

Как только оптимальные решения подзадач найдены, выбирается один нз з — з вариантов индекса к. Если говорить неформально, время работы алгоритма динамического программирования зависит от произведения двух множителей: общего количества подзадач и количества вариантов выбора, возникающих в каждой подзадаче. При разрезании стержня всего у нас возникало ез(п) подзадач и не более и вариантов выбора, что дает время работы 0(пз).

При перемножении матриц всего возникало кр(пз) подзадач, и в каждой из них — не более и — 1 вариантов выбора, поэтому время работы в этом случае равно 0(ззз) (на самом деле — 9(ззз) согласно упр. 15.2.5). Обычно граф подзадач представляет собой альтернативный путь выполнения этого анализа. Каждая вершина соответствует подзадаче, а варианты выбора для каждой подзадачи представлены ребрами, входящими в соответствующую вершину. Вспомним, что в задаче о разрезании стержня граф имел п вершин и не более и ребер на одну вершину, что дает время работы О(тР). Если изобразить граф подзадач для перемножения цепочки матриц, то он будет иметь 9(пз) вершин, а каждая вершина — степень не выше и — 1, что всего дает О(п ) вершин и ребер.

Оптимальная подструктура часто используется в динамическом программировании в восходяшем направлении. Другими словами, сначала находятся оптимальные решения подзадач, после чего определяется оптимальное решение поставленной задачи. Поиск оптимального решения задачи влечет за собой необходимость выбора одной из подзадач, которые будут использоваться в решении полной задачи. Стоимость решения задачи обычно определяется как сумма стоимостей решений подзадач и стоимости, которая затрачивается на определение правильного выбора.

Например, в задаче о разрезании стержня мы сначала решали подзадачи оптимальных способов разрезания стержней длиной з для з = О, 1,..., зз — 1, а затем определяли, какая подзадача дает оптимальное решение для стержня длиной о„используя уравнение (15.2). Стоимость, которая относится к самому выбору, представляет собой член р, в уравнении (15.2).

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

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