Алгоритмы - построение и анализ (1021735), страница 79
Текст из файла (страница 79)
Поскольку величины т [г, 7] опре- Часть !У. Усовершенствованные методы разработки и анализа 402 а,х, ~ л; А, ла Матрица Размерность Аз Аз Аз Ал Аь Аа 30 х 35 35х15 15 х 5 5 х 10 10 х 20 20 х 25 Рис. 15.3. Таблицы т и а, вычисленные процедурой Млтих Силач Оапвк для п = 6 делены только при г < у', используется только часть таблицы т„расположенная над ее главной диагональю. То же можно сказать и о таблице а На рис. ! 5.3 таблица повернута так, чтобы ее главная диагональ была расположена горизонтально.
В нижней части рисунка приведен список матриц, входящих в последовательность. На этой схеме легко найти минимальную стоимость т [г, у] перемножения частичной последовательности матриц А1А1+~ ... А . Она находится на пересечении линий, идущих от матрицы А; вправо и вверх, и от матрицы А — влево и вверх. В каждой горизонтальной строке таблицы содержатся стоимости перемножения частных последовательностей, состоящих из одинакового количества матриц. В процедуре МАтк1х Силач Оа1энк строки вычисляются снизу вверх, а элементы в каждой строке — слева направо. Величина т [1, у] вычисляется с помощью произведений р; зрьр для !а = 1, г + 1,...,у — 1 и величин внизу слева н внизу справа от т [г,у]. Из таблицы т видно, что минимальное количество скалярных умножений, необходимых для вычисления произведения шести матриц, равно т [1, б] = 15 125.
Для пояснения приведем пример. При вычислении элемента т [5,2] использовались пары элементов, идущие от матриц Аз и Аз Глава 15. Динамическое программирование 403 и имеющие одинаковый оттенок фона: т[2, 2] + т[3, 5] + рзрзрь = 0+ 2500 + 35 15 20 = 13000, гл[2, 5] = пйп т[2, 3] + т[4, 5] + р1 рзрз = 2625 + 1000+ 35 . 5 . 20 = 7125, т[2, 4] + т[5, 5] + рьрярз = 4375+ 0+ 35 ° 10 ° 20 = 11375 = 7125 .
Несложный анализ структуры вложенных циклов в процедуре МАтк(х СЕА(и Ок(эек показывает, что время ее работы составляет О (пз). Глубина вложения циклов равна трем, а индексы в каждом из них (1, г и (г) принимают не более п — 1 значений. В упражнении 15.2-4 предлагается показать, что время работы этого алгоритма фактически равно П (пз). Для хранения таблиц т и э требуется объем, равный 9 (гзз). Таким образом, процедура МАтк1х СнАпч Оквек намного эффективнее, чем метод перебора и проверки всевозможных способов расстановки скобок, время работы которого экспоненциально зависит от количества перемножаемых матриц.
Четвертый этап: конструирование оптимального решения Несмотря на то, что в процедуре МАтк(х СнАпч Ок(эек определяется оптимальное количество скалярных произведений, необходимых для вычисления произведения последовательности матриц, в нем не показано, как именно перемножаются матрицы. Оптимальное решение несложно построить с помощью информации, хранящейся в таблице а. В каждом элементе э [г, у] хранится значение индекса и, где при оптимальной расстановке скобок в последовательности А1А;ч1...А. выполняется разбиение.
Таким образом, нам известно, что опти- мальное вычисление произведения матриц Аь.п выглядит как Аь.з(1,и(А8(1,и(+ь.и. Эти частные произведения матриц можно вычислить рекурсивно, поскольку элемент э [1, э[1, т1]] определяет матричное умножение, выполняемое последним при вычислении Аь,(1 „(, а э [э[1, и] + 1, п] — последнее умножение при вычислении А,(1 „(+1 „.
Приведенная ниже рекурсивная процедура выводит оптимальный способ расстановки скобок в последовательности матриц (А;, А1+1,..., А ), по таблице а, полученной в результате работы процедуры МАтк(х СнАпч Окпек, и индексам з и 11 В результате вызова процедуры Ркпчт Огт(мль РАкехз(э, 1, п) выводится оптимальная расстановка скобок в последовательности (А1, Аз,..., А„): РК(МГ ОРТ!МАЬ РАКЕХБ(э, г, 1) 1 (Гг=у 2 Феп рпп1 "А"1 3 е(ае рпп1 "(" Часть 1Ч.
Усовершенствованные методы разработки и анализа 404 4 Ркзхт ОРт!мА$. РАкенз(8, 1, а[1, Я) Рщнт Огт~мль РАкнчз(з,а[г, з]+ 1, т) 6 рппг ")" В примере, проиллюстрированном на рис. 15.3, в результате вызова процедуры Ркичт Огт~мл~. РАккнз(в, 1,6) выводится строка ((А1 (АзАз)) ((А4 4ь) 4в)). Упражнения 15.2-1.
Определите оптимальный способ расстановки скобок в произведении последовательности матриц, размеры которых равны (5, 10, 3, 12, 5, 50, 6). 15.2-2. Разработайте рекурсивный алгоритм МАтк~х СнА1н Мн т]их(А, в,1, 1), в котором оптимальным образом вычисляется произведение заданной последовательности матриц (А|Аз,..., А„). На вход этого алгоритма также подаются индексы 1 и т', а также таблица з, вычисленная с помощью процедуры МАтюх СнАпч Окпвк. (Начальный вызов этой процедуры выглядит следующим образом: МАтнх Снлпч Мы.тпчл'(А, в, 1, и).) 15.2-3. Покажите с помощью метода подстановок, что решение рекуррентного соотношения (15.11) ведет себя как й (2").
15.2-4. Пусть Л (1, з) — количество обращений к элементу матрицы т [1, т], которые выполняются в ходе вычисления других элементов этой матрицы в процедуре МАтнх Снин Окрик. Покажите, что полное количество обращений ко всем элементам равно: (Ужвание: при решении может оказаться полезным уравнение (А.З).) 15.2-5. Покажите, что в полной расстановке скобок в п-элементном выражении используется ровно и — 1 пар скобок.
15.3 Элементы динамического программирования Несмотря на рассмотренные в предыдущем разделе два примера, в которых применялся метод динамического программирования, возможно, вам все еще не совсем понятно, когда применим этот метод. В каких случаях задачу следует решать с помощью динамического программирования? В данном разделе рассматриваются два ключевых ингредиента, которые должны быть присущи задаче Глава 15.
Динамическое программирование 405 оптимизации, чтобы к ней можно было применить метод динамического программирования: наличие оптимальной подструктуры и перекрывающиеся вспомогательные программы. Мы также рассмотрим разновидность метода, который называется заламикакием (шешо1хапол) и позволяет воспользоваться свойством перекрывающихся вспомогательных программ. Оптимальная подструктура Первый шаг решения задачи оптимизации методом динамического программирования состоит в том, чтобы охарактеризовать структуру оптимального решения.
Напомним, что оптимальная лодструклО1ла проявляется в задаче в том случае, если в ее оптимальном решении содержатся оптимальные решения вспомогательных подзадач. Если в задаче выявлено наличие оптимальной подструктуры, это служит веским аргументом в пользу того, что к ней может быть применим метод динамического программирования. (Однако наличие этого свойства может также свидетельствовать о применимости жадных алгоритмов; см. главу 16.) В динамическом программировании оптимальное решение задачи конструируется из оптимальных решений вспомогательных задач. Следовательно, необходимо убедиться в том, что в число рассматриваемых подзадач входят те, которые используются в оптимальном решении.
Оптимальная подструктура была обнаружена в обеих задачах, которые исследовались в настоящей главе. В разделе 15.1 было установлено, что самый быстрый путь до рабочего места с номером у', расположенного на одном из двух конвейеров, включает в себя самый быстрый путь до рабочего места с номером з' — 1. В разделе 15.2 было продемонстрировано, что в оптимальной расстановке скобок, в результате которой последовательность матриц А,А;+1...
А разбивается на подпоследовательности между матрицами Аь и Аьч.м содержатся оптимальные решения задач о расстановке скобок в подпоследовательностях А,А,+1... Аь и Ая+1Аь+г Ау. Можно видеть, что поиск оптимальной подструктуры происходит по общему образцу. 1. На первом этапе следует показать, что в процессе решения задачи приходится делать выбор. В рассмотренных примерах это был выбор рабочего места на конвейере или выбор индекса, при котором разбивается последовательность матриц. После выбора остается решить одну или несколько вспомогательных задач. 2. На этом этапе мы исходим из того, что для поставленной задачи делается выбор, ведущий к оптимальному решению.
Пока что не рассматривается, как именно следует делать выбор, а просто предполагается, что он найден. Часть!У. Усовершенствованные методы разработки и анализа 406 3. Исходя из предположения предыдущего этапа, определяется, какие вспомогательные задачи получаются и как лучше охарактеризовать получающееся в результате пространство подзадач. 4. Показывается, что решения вспомогательных задач, возникающих в ходе оптимального решения задачи, сами должны быть оптимальными. Это делается методом "от противного": предполагая, что решение каждой вспомогательной задачи не оптимально, приходим к противоречию. В частности, путем "вырезания" неоптимального решения вспомогательной задачи и "вставки" оптимального демонстрируется, что можно получить лучшее решение исходной задачи, а это противоречит предположению, что уже имеется оптимальное решение.
Если вспомогательных задач несколько, они обычно настолько похожи, что описанный выше способ рассуждения, примененный к одной из вспомогательных задач, легко модифицируется для остальных. Характеризуя пространство подзадач, постарайтесь придерживаться такого практического правила: попытайтесь, чтобы это пространство было как можно проще, а потом расширьте его до необходимых пределов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
